基于規(guī)則等價性的社區(qū)發(fā)現(xiàn)

荊笑鵬，劉京菊

(電子工程學院 網(wǎng)絡系，安徽 合肥 230037)

?

基于規(guī)則等價性的社區(qū)發(fā)現(xiàn)

荊笑鵬，劉京菊

(電子工程學院 網(wǎng)絡系，安徽 合肥 230037)

為實現(xiàn)可應用于大規(guī)模社會網(wǎng)絡的社區(qū)發(fā)現(xiàn)算法，提出一種基于規(guī)則等價性和局部模塊度的靜態(tài)非重疊社區(qū)發(fā)現(xiàn)算法。通過計算網(wǎng)絡中節(jié)點與節(jié)點之間的規(guī)則等價性，得到相似程度最高的節(jié)點并以此作為初步社區(qū)劃分的依據(jù)。將初步劃分的社區(qū)作為新的節(jié)點，應用規(guī)則等價性和局部模塊度，逐輪將社會網(wǎng)絡劃分為最終的社區(qū)結(jié)構(gòu)。使用規(guī)則等價性作為相似度的衡量，提高了算法的準確度。避免使用全局信息，提高了算法的運行效率。實驗結(jié)果表明，該算法具有一定的實際應用價值。

規(guī)則等價性；相似度；社區(qū)發(fā)現(xiàn)；模塊度

復雜網(wǎng)絡是用于分析社會網(wǎng)絡、信息網(wǎng)絡、交通網(wǎng)絡和生物網(wǎng)絡等現(xiàn)實世界網(wǎng)絡的理論[1]?，F(xiàn)實世界的網(wǎng)絡不是隨機網(wǎng)絡，其中大部分服從冪律分布[2]。冪律分布意味著網(wǎng)絡中大部分節(jié)點擁有較小的度數(shù)。社區(qū)發(fā)現(xiàn)是復雜網(wǎng)絡分析中一個重要的研究方向。社區(qū)是網(wǎng)絡中的一個子圖，這個子圖中的節(jié)點與其他集合中的節(jié)點相比具有更高的相似性[3]。社區(qū)發(fā)現(xiàn)可以分為3類：(1)基于圖論的社區(qū)發(fā)現(xiàn)：這類算法使用社會網(wǎng)絡的拓撲特征，忽略了有關內(nèi)容的信息，通過優(yōu)化反映聚類質(zhì)量模塊度函數(shù)分析社區(qū)結(jié)構(gòu);(2)基于數(shù)據(jù)挖掘技術的社區(qū)發(fā)現(xiàn)：數(shù)據(jù)挖掘技術為從不同的社會網(wǎng)絡數(shù)據(jù)中發(fā)現(xiàn)和挖掘有價值的社區(qū)結(jié)構(gòu)和特征提供了手段，主要包括基于信息論的方法和基于機器學習的方法;(3)基于統(tǒng)計模型的社區(qū)發(fā)現(xiàn)：統(tǒng)計模型是對社會網(wǎng)絡隨機性質(zhì)的一種定量分析，主要包括貝葉斯網(wǎng)絡模型和馬爾科夫鏈模型。

為克服每次聚合都需計算模塊度的缺點，提高算法的時間效率，使其能夠更好地應用于大規(guī)模數(shù)據(jù)集，本文提出一種社區(qū)發(fā)現(xiàn)算法，首先計算每個節(jié)點的規(guī)則相似度，通過將最相似節(jié)點對合并的方式對網(wǎng)絡進行初步的處理，簡化網(wǎng)絡結(jié)構(gòu)。再以經(jīng)過初步處理的網(wǎng)絡為基礎，根據(jù)節(jié)點的規(guī)則相似度進一步聚合社區(qū)。

1 相關工作

前文提到社區(qū)發(fā)現(xiàn)算法可分為3大類：基于圖論的方法，基于數(shù)據(jù)挖掘技術的方法和基于概率模型的方法。

1.1 基于圖論的社區(qū)發(fā)現(xiàn)

一種典型的基于圖論的算法是CNM算法[4]。CNM算法使用層次聚類的思想，通過將節(jié)點在不同的社區(qū)間移動，使網(wǎng)絡的模塊度函數(shù)最大化實現(xiàn)社區(qū)發(fā)現(xiàn)。CNM算法的復雜度為O((m+n)n)，n是網(wǎng)絡中的節(jié)點數(shù)，m是網(wǎng)絡中的邊數(shù)。另一種類似的層次聚類算法是Louvain算法[5]。

標簽傳播算法LPA[6]是一種基于圖的社區(qū)發(fā)現(xiàn)算法。首先，該算法將網(wǎng)絡中的所有節(jié)點注定一個唯一標簽。其次，逐輪更新所有節(jié)點的標簽，直到收斂。在每輪迭代中，對于某一個節(jié)點將其標簽賦值為其所有鄰居節(jié)點中出現(xiàn)次數(shù)最多的標簽，當個數(shù)最多的標簽不唯一時，隨機選擇一個標簽[7]。該算法的時間復雜度較低，為O(m)。

1.2 基于數(shù)據(jù)挖掘技術的社區(qū)發(fā)現(xiàn)

何東曉等[8]提出使用遺傳算法進行社區(qū)發(fā)現(xiàn)，該算法無需先驗知識，將聚類融合引入到交叉算子中，利用父個體的聚類信息和網(wǎng)絡拓撲結(jié)構(gòu)的局部信息產(chǎn)生新個體，縮小搜索空間, 加快了算法收斂速度。

Rosvall等[9]提出基于信息論社區(qū)發(fā)現(xiàn)算法(InfoMap算法) 。該算法在非重疊社區(qū)發(fā)現(xiàn)算法中具有較高的準確度，這種準確度是以犧牲運算時間作為代價，其時間復雜度為O(m+n)n。

1.3 基于統(tǒng)計模型的社區(qū)發(fā)現(xiàn)

Nguyen等[10]使用LDA模型(一種3層分級的貝葉斯模型)獲取博客內(nèi)容的主題，然后比較不同的基于情感的社區(qū)劃分方案，使用一種非參數(shù)聚類，自動發(fā)現(xiàn)隱藏的社區(qū)。

2 基于規(guī)則等價性靜態(tài)社區(qū)發(fā)現(xiàn)算法

2.1 節(jié)點相似度

節(jié)點的相似度用來量化節(jié)點對的連接強度。節(jié)點相似度可通過計算結(jié)構(gòu)等價性或者規(guī)則等價性來獲得。結(jié)構(gòu)等價性是利用節(jié)點的共有鄰接節(jié)點計算相似度。

(1)共有鄰接節(jié)點[11]。考慮兩個節(jié)點間共有鄰接節(jié)點的數(shù)量定義了兩個節(jié)點之間的相似程度。若兩個節(jié)點有較多的共有鄰接節(jié)點，則這兩個節(jié)點有可能是相互連接的，設N(vi)和N(vi)分別表示節(jié)點vi和vj的鄰接節(jié)點，則節(jié)點相似度可表示為

σ(vi,vj)=|N(vi)∩N(vj)|

(1)

(2)Jaccard相似度[12]。在節(jié)點較多的網(wǎng)絡中，節(jié)點之間可能會有諸多的共有鄰接節(jié)點，導致上述相似度的值過大，而通常，相似度被認為是一個有界的值，通常在[0,1]范圍之內(nèi)。因此，可使用歸一化方法

(2)

式(2)表示兩個節(jié)點的相似度由其共有鄰接節(jié)點數(shù)量在其的所有鄰接節(jié)點中所占的比例決定。一般，節(jié)點vi的鄰接節(jié)點N(vi)不包括vi本身，這就造成兩個相互連接但沒有共有鄰接節(jié)點的節(jié)點相似度為0。這可通過將節(jié)點自身加入其鄰接節(jié)點來糾正。若節(jié)點之間未連接，就在一定程度上減小了兩個節(jié)點的相似度，則應在上述公式的基礎上進行修正

(3)

其中，Δ是vi和vj不相連時的懲罰項。

規(guī)則等價性[13]并不像結(jié)構(gòu)等價性注重個體之間共有的鄰接節(jié)點，而是關注這些鄰接節(jié)點的相似程度。例如：兩個演員之間可能并不相互了解，但其之間是相似的，這是因其知道相似的人，比如導演、其他演員等。本文通過計算節(jié)點的規(guī)則等價性來獲得節(jié)點間的相似度，計算公式為

σn=(I-αA)-1

(4)

其中，I為單位矩陣；A為鄰接矩陣；α是常數(shù)，需要選取合適的α值使其收斂。通用的方法是選擇一個α滿足α<1/λ，λ是A的最大特征值。

2.2 社區(qū)發(fā)現(xiàn)算法存在的問題

基于相似度的社區(qū)發(fā)現(xiàn)的主要問題在于如何判斷與某一節(jié)點相似的節(jié)點?，F(xiàn)有諸多計算節(jié)點相似度的方法，但沒有一種方法能確定不同網(wǎng)絡的相似度閾值，閾值設置的過高或過低，均難以得到社區(qū)結(jié)構(gòu)明顯、社區(qū)內(nèi)部聚合度高的社區(qū)劃分結(jié)果。本文使用規(guī)則等價性計算節(jié)點的相似度，用局部模塊度的增加作為每一次合并節(jié)點的條件，這樣做在保證了準確度的同時降低了時間復雜度。

2.3 基于規(guī)則等價性的靜態(tài)社區(qū)發(fā)現(xiàn)算法

2.3.1 相關概念

圖G表示為一個二元組G=(V,E)，其中V表示節(jié)點的集合;E表示邊的集合。

社區(qū)沒有準確的定義，一個被廣泛接受和使用的是：社區(qū)是包含一些節(jié)點的子圖，同一社區(qū)的節(jié)點和節(jié)點之間的連接緊密，而社區(qū)與社區(qū)之間的連接比較稀疏。

在無向圖中，模塊度是一種定量手段，定義了發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)是隨機產(chǎn)生的可能性，其定義為

(5)

其中，ai=∑jeij,eij表示連接社區(qū)Ci和社區(qū)Cj的邊的數(shù)量占所有邊數(shù)的比例。

由于真實的社區(qū)不是隨機的，且結(jié)構(gòu)相對復雜，所以其與隨機生成的社區(qū)差距較大，這一差距使用模塊度Q來表示。Q值越大，說明社區(qū)內(nèi)的聚合度越高，社區(qū)結(jié)構(gòu)越明顯。因此，眾多社區(qū)發(fā)現(xiàn)算法以模塊度作為目標函數(shù)，使用貪心的思想對其進行優(yōu)化。根據(jù)模塊度的定義，當網(wǎng)絡中的節(jié)點數(shù)量較大時，此類算法具有較高的時間復雜度，難以適應大規(guī)模的社會網(wǎng)絡。劉微等[14]提出了局部模塊度Ql，在網(wǎng)絡中節(jié)點數(shù)量較多的條件下，大幅降低了模塊度的計算量，其定義為

(6)

其中，Lin表示2個節(jié)點均在社區(qū)內(nèi)部的邊的數(shù)；Lout表示只有一個節(jié)點在社區(qū)內(nèi)部的邊的數(shù)量。

式中：rand為幅值為1的隨機函數(shù)；Min、 Max的取值根據(jù)文獻[16]實際測量數(shù)據(jù)來決定，根據(jù)文獻[16]中圖5.1、圖5.4、圖5.5的測量結(jié)果，Max和Min的取值如表1所示。

2.3.2 算法策略和步驟

對網(wǎng)絡進行社區(qū)發(fā)現(xiàn)，是為了將具有相似屬性的節(jié)點聚合在一起，從而讓人們更進一步研究網(wǎng)絡子結(jié)構(gòu)屬性。由此可推論出相似度越大的2個節(jié)點，越有可能屬于同一個社區(qū)。

對于網(wǎng)絡G=(V,E)，計算出節(jié)點相似度矩陣 ，首先不斷合并具有最大相似度的節(jié)點對，完成社區(qū)初步劃分。再根據(jù)局部模塊度的增量進一步合并社區(qū)，直到獲取最大的模塊度。

算法步驟如下：

輸入 無向網(wǎng)絡G=(V,E)

輸出 社區(qū)劃分結(jié)果

步驟1 根據(jù)式(3)獲取節(jié)點的相似度矩陣Sn，n為G的節(jié)點數(shù)；

步驟2 隨機選取V中的一個節(jié)點vi，根據(jù)Sn，選取集合P，使 中的元素才滿足P與vi的相似度最大，從V中刪除節(jié)點vi；

步驟4 當V不為空，轉(zhuǎn)到步驟2；

步驟5 設局部模塊度Ql=0；

步驟6 將以劃分的社區(qū)作為集合C，設模塊度Qm=Ql；

步驟7 根據(jù)式(3)獲取以初步劃分的社區(qū)為節(jié)點的相似度矩陣Sc；

步驟8 隨機選取C中的一個社區(qū)Cx，根據(jù)Sc，選取集合Pc，使Pc中的元素Pc滿足Pc與Cx的相似度最大，從C中刪除Cx；

步驟10 當集合C≠?時，轉(zhuǎn)到步驟8；當集合C≠?時，若Qm>Ql，Ql=Qm，轉(zhuǎn)到步驟6；

步驟11 輸出結(jié)果。

2.3.3 算法分析

首先，進行時間復雜度分析。本文算法分為兩部分：第一部分是通過計算節(jié)點的規(guī)則等價性得到相似度，并將網(wǎng)絡初始化。第二部分是使用局部模塊度和初步劃分的網(wǎng)絡進一步劃分社區(qū)。在第一部分中，由于需要計算相似度矩陣，并要找到每個節(jié)點的最相似節(jié)點的集合，所以第一部分的時間復雜度為O(n)。第二部分中，由于需要計算局部模塊度和相似度矩陣，至多需要合并O(lgm)輪，m是網(wǎng)絡中邊的數(shù)目，在每輪合并中，與第一部分的計算過程類似，時間復雜度為O(m)，故第二部分的時間復雜度為O(nlgm)。所以，算法中時間復雜度較高的部分是第二部分對初步劃分的網(wǎng)絡進行進一步聚合的過程，此次算法的時間復雜度為O(nlgm)。

其次，本文算法使用層次聚類的思想，在劃分開始時無需指定所需劃分的社區(qū)的數(shù)目，通過節(jié)點的規(guī)則等價性和社區(qū)的局部模塊度進行優(yōu)化。若不滿足局部模塊度增加的條件，則算法停止。此時獲得最終的劃分結(jié)果。通過局部模塊度來控制社區(qū)聚類的程度，相比于需要計算全局的各類指標，降低了時間復雜度，增加了算法的適用范圍。

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

為驗證本文提出算法的有效性，在兩個實際網(wǎng)絡：Dolphin網(wǎng)絡和Football網(wǎng)絡上運行此算法。實驗在配置為Intel Core i7-4770的處理器和8 GB內(nèi)存的臺式計算機上運行。

3.1 Dolphin網(wǎng)絡

Dolphin網(wǎng)絡[15]是Lusseau通過對新西蘭峽灣地區(qū)Doubtful Sound的海豚超過7年的觀察，總結(jié)的62只海豚的社區(qū)網(wǎng)絡，這個數(shù)據(jù)集是在社區(qū)發(fā)現(xiàn)領域廣泛使用的數(shù)據(jù)集。

本文算法與其他算法的實驗結(jié)果對比如表1所示，本文算法的NMI值略高于InfoMap算法、CNM算法和LPA算法。由于數(shù)據(jù)量較小，本文算法運行時間較低，可近似忽略不計，且低于InfoMap算法和LPA算法。

表1 Dolphin網(wǎng)絡社區(qū)發(fā)現(xiàn)算法對比表

3.2 Football網(wǎng)絡

Football網(wǎng)絡[16]的數(shù)據(jù)是美國大學足球隊2000年賽季的比賽情況。整個比賽有115個足球隊參賽，因而網(wǎng)絡中有115個節(jié)點。這115個隊伍被分為12個小組，與社會網(wǎng)絡的社區(qū)結(jié)構(gòu)類似，小組內(nèi)足球隊之間的比賽比較頻繁，而小組之間的足球隊之間的比賽較少，一個小組可看作一個社區(qū)。本文算法與其他算法的實驗結(jié)果對比如表2所示。本文算法NMI值低于InfoMap，高于LAP算法和CNM算法。在運行時間方面，本文算法的運行時間最少。

表2 足球隊網(wǎng)絡社區(qū)發(fā)現(xiàn)算法對比表

由以上實驗結(jié)果可知，本文提出的社區(qū)發(fā)現(xiàn)算法的準確率略低于InfoMap算法，同時在運行時間上又略低于LPA。因此，本文算法與其他社區(qū)發(fā)現(xiàn)算法相比，具有一定的實用價值。

4 結(jié)束語

本文提出的基于規(guī)則等價性的社區(qū)發(fā)現(xiàn)算法，在現(xiàn)實網(wǎng)絡中具有一定有效性，能應用于節(jié)點數(shù)量較多的社會網(wǎng)絡。該算法首先將最相似的節(jié)點組成簡單的社區(qū)結(jié)構(gòu)，然后將初始化分的社區(qū)作為節(jié)點，以局部模塊度作為優(yōu)化目標，逐步實現(xiàn)社區(qū)的進一步聚合。在每一輪聚合中，只計算關于社區(qū)的局部信息，提高了算法的運行效率和準確率。通過對比實驗的結(jié)果也可證明，本文基于規(guī)則等價性和局部模塊度的社區(qū)發(fā)現(xiàn)算法在實際社會網(wǎng)絡中的有效性。本文算法目前只局限于單機運行，如何將此算法在多臺主機上并行運行是接下來的研究工作。

[1] Newman M E J.The structure and function of complex Networks[J].SIAM Review,2003,45(2): 167-256.

[2] 徐恪,張賽,陳昊,等.在線社會網(wǎng)絡的測量與分析[J].計算機學報,2014,37(1):165-188.

[3] 汪小帆,李翔,陳關榮.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社,2006.

[4] Newman M E. Fast algorithm for detecting community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,69(6):066133-066138.

[5] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics Theory & Experiment,2008,30(2):155-168.

[6] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):1-12.

[7] 董瑩瑩.融入影響力的重疊社區(qū)發(fā)現(xiàn)算法研究[D].杭州:浙江大學,2013.

[8] 何東曉,周栩,王佐,等.復雜網(wǎng)絡社區(qū)挖掘—基于聚類融合的遺傳算法[J].自動化學報,2010, 36(8):1160-1170.

[9] Rosvall M,Bergstrom C T.Maps of random walks on complex networks reveal community structure[J]. Pnas,2008,105(4):1118-1123.

[10] Nguyen T, Phung D, Adams B, et al. Hyper-community detection in the blogosphere[C].Sandiago:Proceedings of Second ACM SIGMM Workshop on Social Media,2010.

[11] Lorrain F, White H C. Structural equivalence of individuals in networks[J]. Journal of Mathematical Sociology,1971,1(1):49-80.

[12] Jaccard P. Etude de la distribution florale dans une portion des alpes et du Jura[J]. Bulletin De La Societe Vaudoise Des Sciences Naturelles,1901,37(142):547-579.

[13] Borgatti S P,Everett M G.Two algorithms for computing regular equivalence[J].Social Networks,1993,15(4):361-376.

[14] 劉微,張大為,嵇敏,等.基于共享鄰居數(shù)的社團結(jié)構(gòu)發(fā)現(xiàn)算法[J].計算機工程,2011,37(6):172-174.

[15] Lusseau D.The emergent properties of a dolphin social network[J].Proceedings of the Royal Society B Biological Sciences, 2003,270(s2):186-188.

[16] Sun P G,Gao L,Han S S.Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks[J].Information Sciences,2011,181(6):1060-1071.

Community Detection Based on Regular Equivalence

JING Xiaopeng，LIU Jingju

(Department of Network System，Electronic Engineering Institute, Hefei 230037, China)

To achieve the target of community detection, which can be applied to large-scale social network, this paper proposes a algorithm of static non-overlapping community detection based on regular equivalence and local modularity. The algorithm calculates the regular equivalence between nodes of the network and obtains nodes of the highest degree of similarity. These nodes are initial community detection basis. The algorithm takes The preliminary divided communities as new nodes, applies to regular equivalence and local modularity and divides the social network into the final structure of the community round by round. It uses regular equivalence as the measure of similarity, improve the accuracy of the algorithm. And it is free to use global information to improve the operating efficiency. Experimental results show that the algorithm has some practical value.

regular equivalence; similarity; community detection; modularity

10.16180/j.cnki.issn1007-7820.2016.12.026

2016- 02- 17

荊笑鵬(1990-)，男，碩士研究生。研究方向：數(shù)據(jù)挖掘，網(wǎng)絡安全。劉京菊(1974-)，男，副教授。研究方向：數(shù)據(jù)挖掘，網(wǎng)絡安全。

TP393

A

1007-7820(2016)12-093-04