0 引言

    近年來,，隨著信息交互和數(shù)據(jù)共享的不斷增加,，社交網(wǎng)絡(luò)的數(shù)量顯著提高。在分析此類網(wǎng)絡(luò)時,，圖論提供了一個重要的建模模型,。當節(jié)點代表用戶，邊表示互聯(lián)時,，可以將此類網(wǎng)絡(luò)定義為一張圖^[1-3],，該圖中的節(jié)點可以是直接或間接相連的。在分析社交網(wǎng)絡(luò)數(shù)據(jù)時,，定義和計算社區(qū)是最關(guān)鍵的步驟,。同時,社區(qū)可以被看作是對整個網(wǎng)絡(luò)的概要表示(Summarization)，因此,在社區(qū)檢測中需要使用這種概要設(shè)計理念^[4],。

    當前對于社區(qū)網(wǎng)絡(luò)劃分研究已取得了很多研究成果,，特別是社會網(wǎng)絡(luò)分析，但其仍然是一項具有挑戰(zhàn)性和吸引力的研究,。因為在給定的圖中進行社區(qū)檢測,，可以用于搜索潛在的合作者，用于優(yōu)化社會關(guān)系,，或在不同的社區(qū)中搜索一個關(guān)鍵人物等^[5],。

    基于圖論的原理，已經(jīng)提出了不少方法用來解決社區(qū)檢測的問題,，如譜分析方法^[6],，其代表了一種非常特殊的社區(qū)檢測技術(shù)。這種方法的特殊性表現(xiàn)在其分類性能上,，并以拉普拉斯矩陣的特征向量為基礎(chǔ),。使用這樣一個矩陣在時間和內(nèi)存方面需要付出很高的代價。此外,，在時間復雜度上,，k個特征向量的計算復雜度為O(n³)。雖然,，很容易計算出給定矩陣的特征向量，但是不方便計算大型拉普拉斯矩陣,。這個方法的第二個缺點是假設(shè)社區(qū)的數(shù)量必須是已知的,，但是在實際的大型社交網(wǎng)絡(luò)中很難獲得這一信息。文獻[7]提出了一種基于聚類概念的社區(qū)檢測方法,。這種技術(shù)的優(yōu)點是它能夠提供豐富的結(jié)果,，使用這種方法發(fā)現(xiàn)的社區(qū)節(jié)點之間相互連接非常緊密,。然而，在時間和內(nèi)存方面代價很高,，而且非常復雜,。BASUCHOWDHURI P等人^[8]提出了一種基于最大生成樹的并發(fā)方法。該方法使用共同鄰居的相似性作為邊的權(quán)重,。將每個節(jié)點都與鄰居相連接,，共享了大量的共同鄰居，從而建造了最大生成樹,。與文獻[7]的方法相比較,，這種方法在占用內(nèi)存方面效果較好，但是其時間運行成本還是較高,。文獻[9]提出了一種基于節(jié)點和邊的檢測社區(qū)方法,，可廣泛用于查找網(wǎng)橋和服務(wù)供應(yīng)商。但是,，對于大型的社交網(wǎng)絡(luò)而言,，這些方法的適用性均較差。

    在以上文獻提出的方法中,，運行時間的復雜度和內(nèi)存的使用成本問題仍然存在,。因此，它們的適用性具有一定的局限,。為了解決這些問題,，本文提出了一種有效的社區(qū)檢測算法方法，該方法基于聚類系數(shù)和共同鄰居指標,。實驗結(jié)果表明,，在大規(guī)模社會網(wǎng)絡(luò)數(shù)據(jù)集中提出的方法提供了較高質(zhì)量的社區(qū)劃分結(jié)果，并具備線性運行時間的復雜度特性,。

1 模型和指標定義

1.1 問題描述

    在一個網(wǎng)絡(luò)模型中,，一張圖G由有限集合(V，E)構(gòu)成,，其中V表示節(jié)點集合(網(wǎng)絡(luò)的用戶),，E表示邊或節(jié)點之間相互聯(lián)系的集合，V={v_i|i=1,，…,，n}，E={e_ij|v_i,，v_j∈V},，n=|V|為節(jié)點總數(shù)，m=|E|為邊的總數(shù),。此外,，當圖G′中節(jié)點的集合E′和邊的集合V′都是圖G中V和E的子集時,，G′表示G的子圖。社交網(wǎng)絡(luò)可以建模為一個有向圖或一個無向圖,，其中節(jié)點表示個體,，邊表示節(jié)點之間的關(guān)系。本文重點是在社交網(wǎng)絡(luò)中進行社區(qū)檢測,，它可以用一個無向圖來表示,。這個社區(qū)可以被定義為節(jié)點的一個子集，與網(wǎng)絡(luò)的其他節(jié)點相比較,，這些節(jié)點更有可能連接在一起,。圖1顯示了一張具有3個社區(qū)的信息圖。

1.2 采用的度量標準

    本文采用共同鄰居的相似性來衡量兩個節(jié)點的相似度,，這意味著,，當此度量指標較高時，節(jié)點更有可能是在同一個社區(qū)內(nèi),。相比應(yīng)用平均聚類系數(shù)來衡量集群的方法,，本文提出的結(jié)果準確性更高。本文采用了兩種度量標準：

    (1)共同鄰居的相似性：在參考文獻[8]和[10]中使用共同的鄰居來定義節(jié)點之間的相似性,。如果兩個節(jié)點有大量的共同鄰居,，那么它們更相似。這個指標由以下公式進行計算,。

式中,，A表示鄰居相似性。

    (2)聚類系數(shù)：采用此類度量標準的目的是評估節(jié)點在一個集群中的集群化趨勢,。其中最受歡迎的一個測量標準是模塊性最大化,，但是它存在兩個問題：①它合并小型子圖，當分辨率較低時,，它占主導地位,；②它分裂大型子圖，當分辨率較高時,，它占主導地位,。另一種被廣泛使用的度量稱為聚類系數(shù)^[10-11]，在一個社區(qū)內(nèi)提供了一個強大的鄰居結(jié)構(gòu),。這項標準被廣泛應(yīng)用于社會網(wǎng)絡(luò)分析中,，它被定義為封閉的三聯(lián)體(三角形)數(shù)量和給定圖的三聯(lián)體數(shù)量之間的比率，式(2)給出了其定義^[2]：

式中,，C表示聚類系數(shù),。

2 提出的權(quán)重系數(shù)

    本研究的目的是研究社區(qū)之間的邊所存在的一些性質(zhì)，最后提取新的社區(qū),。

    引理1：假設(shè)G是一張無向非加權(quán)圖,，E表示G的邊集合，V表示G的節(jié)點集合,，得到如下公式：

其中,，L表示節(jié)點vi鄰居之間的關(guān)聯(lián)數(shù)量。

    論證：假設(shè)G為一張圖,，僅僅包含一個三角形T,，本文假設(shè)它由3個節(jié)點組成(v₁，v₂,，v₃),。

    如果計算L(v₁)，則發(fā)現(xiàn)一對關(guān)聯(lián)(v₂和v₃),；如果計算v₂的這一度量,，則發(fā)現(xiàn)v₁和v₃之間的關(guān)聯(lián)；最后計算v₃,，得到了v₁和v₂之間的關(guān)聯(lián),。之后，如果計算總和L(v₁)+L(v₂)+L(v₃),，那么得到的結(jié)果是3對關(guān)聯(lián),。總之,，當本文計算一張圖中每個節(jié)點與其鄰居之間的關(guān)聯(lián)數(shù)量時,，對同一個三角形計算了3次。

    圖2闡釋了一張無向圖,，由7個節(jié)點和10條邊構(gòu)成,。該圖由3個三角形組成。當本文計算這7個節(jié)點鄰居之間的關(guān)聯(lián)數(shù)量總和時,，得到表1所示結(jié)果,。

    根據(jù)這些結(jié)果，3個三角形共計算了3次,，這意味著3×(在G₁中的三角形數(shù)量)等于在G₁中每個節(jié)點鄰居之間的關(guān)聯(lián)數(shù)量總和,。

    性質(zhì)1：運用式(1)，本文可以得出結(jié)論：兩個社區(qū)之間的一條邊的節(jié)點是不同的,。它們沒有或僅有少數(shù)幾個共同的鄰居,。

    性質(zhì)2：本文研究的重點在于在社區(qū)內(nèi)最大化聚類系數(shù)(式(2))。為了達到這一目標,，三角形的數(shù)量以及式(4)中的度量必須盡可能地最大化,。實際上，在一個社區(qū)中每個節(jié)點鄰居之間的關(guān)聯(lián)數(shù)量必須最大化,。這意味著對于具有較高聚類系數(shù)(大量三角形)的兩個社區(qū)之間的節(jié)點,，其鄰居之間的關(guān)聯(lián)數(shù)量較大,。

    引理2：假設(shè)G是一張無向非加權(quán)的圖。在兩個社區(qū)之間一條邊e(v_i,，v_j)的節(jié)點沒有或有幾個共同鄰居,，節(jié)點v_i和v_j具有較高的度量L。

    論據(jù)：通過使用性質(zhì)1和性質(zhì)2獲得引理2,。

    本文將節(jié)點鄰居之間的關(guān)聯(lián)數(shù)量標準化,。由以下方程來定義標準化：

式中，B表示的是節(jié)點鄰居關(guān)聯(lián)數(shù)據(jù)標準,。

    通過式(1)可知節(jié)點之間共同鄰居的數(shù)量,。從引理2可以得知，本文的目標是找到這些邊e(v_i,，v_j),，它們在鄰居i和j之間的關(guān)聯(lián)數(shù)量較大(見式(5))，而在i和j之間的共同鄰居數(shù)量較少(見式(1)),。因此,，以這些邊為基礎(chǔ)，所提方法的目標是找到度量W,，W可以由如下公式定義：

3 本文提出的方法

    在過去的幾年中,，在社交網(wǎng)絡(luò)中進行社區(qū)檢測已經(jīng)吸引了很多研究人員，但它仍是一項具有挑戰(zhàn)性的任務(wù),。事實上,，大多數(shù)現(xiàn)有方法的適用性受限于它們的計算成本。本文提出的方法通過刪除在未加權(quán)圖中的社區(qū)之間的邊,，從社交網(wǎng)絡(luò)中找到社區(qū),。本文假設(shè)一個社區(qū)必須至少有4個節(jié)點，如參考文獻[2]所使用的社區(qū),。刪除邊是為了最小化每條邊節(jié)點之間的共同鄰居數(shù)量(少于共同鄰居的20%),，并且提高社區(qū)劃分的質(zhì)量。下面介紹算法步驟和實例分析,。

3.1 算法描述

    本文提出的方法使用了以下步驟：

    輸入：無向非加權(quán)的網(wǎng)絡(luò)G(V,，E)

    輸出：n個社區(qū)，G_s={G_s1,，G_s2,，…，G_sn}

    (1)首先,，本文計算在圖G中每個節(jié)點鄰居之間的關(guān)聯(lián)數(shù)量L(v_i),。然后，本文計算每條邊e共同聚類數(shù)量C，以及這條邊的節(jié)點之間鄰居U的結(jié)合情況,。之后,，設(shè)L=L(v_i)+L(v_j)和S=|鄰居(v_i)+鄰居(v_j)|，其中v_i,、v_j表示由邊e相連的兩個節(jié)點,。

    (2)本文使用W在表格T中以遞減順序?qū)呥M行分類。一旦這個操作完成,，就按照在T中的順序找到第一條邊e(v_i，v_j),。如果在刪除這條邊之后,，v_i鄰居的數(shù)量和v_j鄰居的數(shù)量均會超過0，那么將這條邊從G中刪除,，否則不刪除,。本文需要對T中的其他邊重復測試，直到表格T是空為止,。

    (3)本文應(yīng)用了一個社區(qū)必須至少包含4個節(jié)點的假設(shè),。為了確保該假設(shè)成立，需要把每張少于4個節(jié)點的子圖G′加入到在步驟(2)中已經(jīng)被分離的最后一張子圖中,。

3.2 實例分析

    設(shè)一個網(wǎng)絡(luò)N1結(jié)構(gòu)如圖3所示,，圖4體現(xiàn)了提出的方法應(yīng)用于網(wǎng)絡(luò)N₁的結(jié)果。首先,，運用步驟(1)在未加權(quán)的圖中計算每條邊的W值,。然后，本文選擇符合以下條件的邊e(v_i,，v_j)：在節(jié)點v_i和v_j之間共同鄰居的數(shù)量較低(少于20%),。

    本文運用W值對這些邊進行分類，按照遞減順序?qū)⑦@些邊儲存在表格T中,。重復步驟(2)中邊的刪除操作,，直到為空白為止。注意,，大小小于2的群組不可以被分為獨立的群組,。

    最后，本文將少于4個節(jié)點的每張子圖G′加入到已經(jīng)被分離的最后一張子圖中,。

4 實驗結(jié)果與分析

    為了驗證本算法的有效性,，采用真實的較大規(guī)模社會網(wǎng)絡(luò)數(shù)據(jù)集進行實驗分析，并與生成樹算法^[8],、CBCD算法^[12]進行比較分析,。

    實驗環(huán)境中服務(wù)器設(shè)備參數(shù)為：Xeon E7-4820雙核處理器，2.5 GHz CPU頻率，16 GB內(nèi)存,，Windows Server 2012系統(tǒng),。本文在核心圖社區(qū)檢測時采用GN算法(Girvan-Newman)。

    本文采用模塊性Q函數(shù)^[13]來評價劃分出的模塊性,，采用NMI^[13]來評價劃分結(jié)果的相似性,，兩個評價指標的數(shù)值越接近1，說明算法劃分的效果和質(zhì)量越高,。實驗采用的4個較大社會網(wǎng)絡(luò)數(shù)據(jù)集的具體參數(shù)如表2所示,。

4.1 結(jié)果分析

    采用生成樹算法、CBCD算法和本文提出算法在以上4個社會網(wǎng)絡(luò)數(shù)據(jù)集上分別進行了100次運行測試,，實驗結(jié)果的平均指標數(shù)據(jù)如表3所示,。

    通過表3可以看出，在Q函數(shù)指標結(jié)果上,，本文提出算法比其他兩種算法都表現(xiàn)更好,，即社會發(fā)現(xiàn)更有效，更好地體現(xiàn)了社區(qū)結(jié)構(gòu)的劃分,。在NMI指標結(jié)果上,，相比其他兩種算法，本文算法的數(shù)值更接近于1,，即劃分結(jié)果和真實的劃分更相似,。

    從表4中可以看出，本文算法在4個社會網(wǎng)絡(luò)數(shù)據(jù)集上的運行時間均比其他兩種算法少,，即相比其他兩種算法,，本算法具有更高的效率。

4.2 復雜度分析

    該方法不是對所有的邊進行分類,，而僅僅對共同鄰居少于20%的邊進行分類,。例如，在Ca-CondMat網(wǎng)絡(luò)中,，包含186 936條邊,，本文僅僅對其中的67 297條邊進行分類。同樣,，本文在Cit-HepTh網(wǎng)絡(luò)中僅僅對352 807條邊中的176 403條邊進行分類,。

    在步驟(2)中，本文對一部分共同鄰居少于20%的邊進行分類,。如果本文假設(shè)這些邊的數(shù)量為k,，那么復雜度為O(k·log(k))，即具有線性復雜度,。在本算法的實施過程中,，運用了python 3.3分類算法,。如果假設(shè)在步驟(3)的操作之后發(fā)現(xiàn)子圖的數(shù)量為c，由少于4個節(jié)點構(gòu)成的子圖數(shù)量為c₁,，那么復雜度為O(c₁·log²(c)),。因為O(c₁·log²(c))<<O(N)，根據(jù)所選擇的網(wǎng)絡(luò),，本文得到出算法的復雜度取決于O(k·log(k)),。因此，本文提出的算法具有線性復雜度,，即使在運行時間最壞的情況下,，復雜度為O(k·log(k))。

5 結(jié)束語

    本文提出了一種適用于社交網(wǎng)絡(luò)的新型社區(qū)檢測新方法,。該方法使用了兩個最重要的度量來定義社區(qū)：(1)聚類系數(shù),，用于定義社區(qū)的質(zhì)量；(2)屬于同一條邊的兩個節(jié)點共同鄰居的數(shù)量,。實際上，與在不同社區(qū)中的兩個節(jié)點相比,，在同一個社區(qū)中的兩個節(jié)點具有的共同鄰居數(shù)量較高,。基于這些度量,，本文推導出一個公式,，允許在社區(qū)之間查找邊。在這個迭代的算法中,，運用一些查找社區(qū)的標準來刪除邊,。最后，實驗結(jié)果表明,，與傳統(tǒng)的算法相比,，本文提出的方法提供的網(wǎng)絡(luò)數(shù)據(jù)集合劃分不但模塊性高，NMI指標和運行效率也非常高,。此外,，該方法的運行時間具有線性復雜度，由此可以應(yīng)用于大型的社交網(wǎng)絡(luò)中,。

參考文獻

[1] JIN J.Fast community detection by SCORE[J].Annals of Statistics,，2014，43(2)：672-674.

[2] LI Z,，ZHANG S,，ZHANG X.Mathematical model and algorithm for link community detection in bipartite networks[J].American Journal of Operations Research，2015,，5(5)：421-434.

[3] SONG X,，GENG Y.Distributed community detection optimization algorithm for complex networks[J].Journal of Networks，2014，9(10)：2758-2765.

[4] 張華健,，王有權(quán),，伍之昂，等.基于局部緊耦合結(jié)構(gòu)的模塊性優(yōu)化社區(qū)檢測方法[J].東南大學學報(自然科學版),，2014,，44(3)：504-509.

[5] 吳大鵬，向小華,，王汝言,，等.節(jié)點歸屬性動態(tài)估計的機會網(wǎng)絡(luò)社區(qū)檢測策略[J].計算機工程與設(shè)計，2012,，33(10)：3673-3677.

[6] 安晶,，徐森.基于譜聚類的動態(tài)網(wǎng)絡(luò)社區(qū)演化分析算法[J].信息與控制，2015,，44(2)：197-202.

[7] 龔尚福,，陳婉璐，賈澎濤.層次聚類社區(qū)發(fā)現(xiàn)算法的研究[J].計算機應(yīng)用研究,，2013,，30(11)：3216-3220.

[8] BASUCHOWDHURI P，ROY R,，ANAND S,，et al.Spanning tree-based fast community detection methods in social networks[J].Innovations in Systems and Software Engineering，2015,，11(3)：177-186.

[9] SANLI C,，LAMBIOTTE R.Local variation of hashtag spike trains and popularity in Twitter[J].Plos One，2015,，10(7)：3-14.

[10] AGGARWAL C C,，XIE Y，YU P S.A framework for dynamic link prediction in heterogeneous networks[J].Statistical Analysis & Data Mining the Asa Data Science Journal,，2014,，7(1)：14-33.

[11] 許鵬遠，黨延忠.基于聚類系數(shù)的推薦算法[J].計算機應(yīng)用研究,，2016,，33(3)：654-656.

[12] 張新猛，蔣盛益.基于核心圖增量聚類的復雜網(wǎng)絡(luò)劃分算法[J].自動化學報,，2013,，39(7)：1117-1125.

[13] 林友芳，王天宇,，唐銳,，等.一種有效的社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型和算法[J].計算機研究與發(fā)展,，2012，49(2)：337-345.