基于關聯度與引力的復雜網絡社區發現方法

龍 浩，趙 瑛

(江西師范大學 軟件學院，江西 南昌 330029)

0 引 言

現實世界中很多內部單元間存在豐富關聯的復雜系統都可表示為網絡，如人際關系網、科研合作網等社會系統，電力網、交通網等技術系統，神經網、蛋白質作業網等生物系統，論壇、博客、社交網絡等互聯網應用系統。研究結果表明[1]，復雜網絡除了普遍具有小世界、無尺度等統計特征，還有極為重要的社區結構特征[2]。同一社區中的節點，有著較高的連邊密度，而社區之間的節點，只有少量節點存在連邊。社區結構是復雜網絡的中觀結構，把微觀個體和宏觀整體銜接起來，對于揭示復雜網絡中的社區構成和社區彼此間關聯有著重要意義，有利于加深人們理解復雜系統內部的層次結構和功能特征。近年來社區發現已成為系統科學、社會分析、信息搜索等領域的研究熱點。

目前的復雜網絡社區發現方法大致可分為3大類：

(1)優化方法。通過定義社區劃分的全局目標函數，以達到或接近目標函數最大值作為社區劃分結果。淦文燕等[3]引入拓撲勢場來描述網絡節點之間的聯系，聯系密切的節點處于勢場高處，可以通過查找勢值較高的節點可以找出社區；Rodrigo等[4]將社區劃分結果與社區內部期望進行比較，提出用Surprise函數來評價社區劃分結果；冷作福[5]基于局部貪婪優化技術，提出了求解這類函數定義的社區劃分問題的算法。模塊度Q函數[6]是目前使用最廣泛的社區劃分評價，以社區內部連接與隨機連接的差異最大化來評價社區，文獻[7-9]探討了用群體智能算法來求解模塊度Q函數，實現網絡的社區劃分。優化方法的難點在于定義合適的目標函數，且容易陷入局部極值，多數情況下最優社區劃分方案未必取得最優的目標函數值。

(2)人工智能方法，主要包括和聚類方法模型匹配方法。聚類方法通過定義網絡節點間、連邊間的相似函數，采用聚類算法對節點或連邊歸類，將相似程度比較大的節點劃分到同一社區[10]。邊圖劃分[11]將社區視為關系密切邊的集合，通過定義邊的相似度函數來對邊集進行聚類，再將邊劃分結果轉化為相應的節點社區；文獻[12]通過二階段聚類實現重疊社區的發現。模型匹配算法使用混合模型[13]、隨機塊模型[14]來擬合真實網絡，并用最大期望算法、改進的最大期望算法或Gibbs采樣算法來求解社區參數。聚類方法的缺陷在于容易出現社區冗余，相似性指標的設計也是困擾研究者的一個問題。模型匹配方法能夠適應不同類型的網絡，但算法復雜性極大限制了它在大型網絡上的應用。

(3)啟發式方法，主要包括裂解方法或局部擴充方法類發現社區。裂解方法通過找到并刪除社區間的連邊來發現社區，GN算法[15]認為邊介數大的連邊往往是社區之間的連邊，通過逐步找出并刪除最大邊介數的連邊來分割網絡；文獻[16]用連邊相似度來衡量連邊隸屬社區的程度，通過迭代刪除社區之間的連邊來獲得網絡社區劃分結果；局部擴展方法從網絡特點節點或結構出發，不斷向外擴充形成社區；LFM算法[17]隨機選擇一個節點開始擴張，直至局部適應度函數最優為止，迭代這一過程直到沒有剩余節點；文獻[18]從子結構出發來擴充社區，并用局部適應度函數對擴充過程進行調整；Raghavan等[19]提出標簽傳播思想來識別社區；文獻[20]通過發現網絡環路并計算緊密值，以此作為網絡社區的依據；文獻[21]根據力導向模型的原理，通過計算社區與節點之間的作用力來決定節點的社區歸屬；其它的方法包括矩陣分解方法、特征向量分析的譜方法等等。

復雜網絡的社區發現本質上是一個NP-hard問題。對于這類大規模復雜問題，啟發式方法能夠獲得較好的性能，因此目前大部分關于復雜網絡社區挖掘的成果和論文都基于這類方法。本文提出了一種網絡社區發現算法，通過分析連邊特征，定義關聯度作為評價連邊兩端節點關聯程度和連邊在網絡中重要程度的度量，將互連的高關聯度節點構成社區骨架；對邊緣節點，將它與社區骨架的關聯度體現為引力，將它們逐步分級并歸入引力最大的社區。并通過實驗驗證了算法對網絡社區挖掘問題的有效性和高效性。

1 基于關聯度和引力社區挖掘算法

1.1 基本思想

復雜網絡中的節點在社區中所起的作用是不同的，既有邊緣節點，也有核心節點。核心節點與同一社區的其它核心節點聯系密切，這是社區得以形成和維持的基礎，也是網絡中多個社區呈現的原因。邊緣節點對核心節點有較高的依賴性，通過社區中的核心節點參與到社區中。

1.2 基本概念

復雜網絡可以抽象為圖模型，并用二元組G=表示,其中V={vi|1≤i≤|V|}是網絡中的節點集，E={eij|eij=,1≤i,j≤|V|,i≠j} 表示網絡的連邊集，通常|V|=n,|E|=m。 令矩陣A=(aij)n×n表示圖G中節點的鄰接矩陣，如果eij∈E， 則aij=1， 否則aij=0。 本文主要研究無權無向的無環圖。

定義1 鏈接關聯度是連邊兩端互聯節點關系程度及連邊在網絡中重要程度的一種度量。是兩個節點之間直接和間接連接數與兩節點中較小度的比值

(1)

關聯度反映了連邊兩端網絡節點通過第三方加強彼此關聯的程度。aij是它們之間的鄰接項，ki,kj是它們的度；顯然0≤βij≤1。當βij=0時，兩節點之間的最短路徑≥3。

定義2 核心節點。對于給定的節點vi，如果滿足條件

(2)

其中，threshhold是一個給定的常數，則vi為社區核心節點。同一社區內的核心節點通過較高關聯度的連接互連起來，構成社區骨架；不同的社區骨架或者沒有直接的連接、或者連邊的關聯度很低。

定義3 定級系數。節點vi的定級系數定義為它與社區骨架節點和已定級節點的連邊占自身度的比例

(3)

{centero,center1,center2,…,centerq} 是已定級節點集合，其中center0表示節點vi的鄰居節點中設置為社區骨架節點的節點集合。如果δvi≥δ0(δ0是定級系數閥值)，則稱vi是q+1級社區節點，即vi∈centerq+1。

定義4 引力。反映未歸類節點對社區的依賴程度

(4)

對于q級的未歸類節點vi∈V,g1(vi)=maxjγ(vi,uj)→vi∈ul。 即vi被歸入對其引力最大的社區中。

1.3 社區發現算法

基于關聯度和引力的社區發現算法分兩個階段：首先通過計算連邊關聯度找出所有核心節點，把互聯的核心節點組合在一起構成社區骨架；根據定級閥值δ0對未歸類的邊緣節點進行定級，并根據給定的距離系數dvi,ujw和引力參數t1,t2,…,tQ，計算不同社區uj對q級的邊緣節點vi的引力γ(vi,uj)，將節點歸入對其引力最大的社區。繼續定級q+1級邊緣節點并進行引力計算,直到所有邊緣節點全部歸類。

算法1：社區骨架的生成

輸入：圖G連邊數組L，社區數K，關聯度閾值t;

輸出：社區骨架S,關聯度數組RL；

(1)根據連邊數組L構建網絡的節點鄰居數組鏈表LL；

(2)計算網絡中各個節點的度；

(3)計算每條連邊的關聯度，與L一起構成關聯度數組RL；

(4)篩選所有大于關聯度閾值t的連邊;

(5)對于篩選的每條連邊，如果兩節點均不屬于任何社區， |S|=|S|+1， 建立一個新社區并將兩個節點歸入該社區；如果一個節點已歸屬某一已有社區，將另一節點也歸入該社區；如果兩節點分屬不同社區，合并這兩個社區， |S|=|S|-1；

算法2：邊緣節點的社區歸屬

輸入：社區骨架S,關聯度數組RL，定級系數閥值δ0，引力參數t1,…,tm；

輸出：社區劃分結果S；

(1)i=1,根據社區骨架找出邊緣節點集V1；

(2)計算各邊緣節點的定級系數，如果定級系數超過閥值，將節點保留在Vi中，否則將其放入Vi+1；

(3)任取Vi中的節點vi，計算各個社區對其引力γ(vi,uj)；將節點vi歸入引力最大的社區；

(4)如果Vi不為空，轉步驟(3)；

(5)i=i+1，如果Vi不為空，轉步驟(2)，否則結束。

1.4 算法復雜性分析

在算法1中，以數組存儲各個節點的度、連接和關聯度。步驟(1)、步驟(2)、步驟(4)、步驟(5)的時間復雜度為O(m)，步驟(3)的時間復雜度為O(d2m)(d是節點平均度)，所以算法1的時間復雜度為O(d2m)。在算法2中，步驟(1)的時間復雜度為O(m)，步驟(2)～步驟(5)的時間復雜度為O(n)。所以社區劃分算法的總時間復雜度是O(d2m+n)。

2 實驗與結果分析

本文算法在win7平臺上采用MATLAB R2012a進行開發。運行環境為Intel 2.1 GHz Processor，4 GB RAM。為簡化起見，本文規定在所有網絡上，引力參數t1=t2=,…=tQ=1。對于真實網絡社區劃分，用劃分精確度(Precision=nright/n， 其中nright是正確分類的節點數目)進行結果評價；對于人工網絡，采用NMI(normalized mutual information)進行結果評價，NMI定義參照文獻[22]。

2.1 真實基準網絡

為驗證基于關聯度與引力的復雜網絡社區發現方法的有效性，采用兩個社區成員明確的真實復雜網絡數據集Zachary、Dolphins[23]進行檢驗。

2.1.1 Zachary網絡

Zachary是一個描述空手道俱樂部成員的網絡數據集，廣泛用于復雜網絡社區劃分結果的驗證。網絡節點表示俱樂部成員，連邊表示他們之間的朋友關系，網絡共有34個成員。

圖1是Zachary網絡在參數P=2,threshhold=0.7,δ0=0.5下的最終社區劃分結果。加粗連線是社區核心節點的連接，小圓和方框分別表示兩個不同社區的節點，實心表示社區核心節點，空心表示社區邊緣節點。從圖中可以看到，左邊社區中除節點{20}是邊緣節點外，其它節點均為核心節點；右邊社區中節點{10,25,26,28,29,32}是邊緣節點，且{10,26,28,29,32}是一級邊緣節點，{25}是二級邊緣節點，其余節點是核心節點。從圖中可以看到，節點{32}雖然具有較高的度(度為6)，但由于它所有連邊的關聯度值均低于閾值，因此并不是社區核心節點。實驗結果表明，本算法的社區劃分結果夠很好地符合實際情況，社區劃分正確率為100%。

圖1 Zachary的社區劃分(P=2,threshhold=0.7,δ0=0.5)

2.1.2 Dolphins網絡

Dolphins網絡也是研究復雜網絡社區發現問題的常用真實網絡。該網絡包含兩個海豚家族共62個成員，兩個家族分別包括42、20個成員。

圖2是Dolphins網絡在參數P=2,threshhold=0.5,δ0=0.5的本文算法社區劃分結果。加粗連線是社區核心節點的連接，小圓和方框分別表示兩個不同社區的節點，實心表示社區核心節點，空心表示社區邊緣節點。從圖中可以看到，左邊社區有{3,37,40,45,47,50,54,56,62}是邊緣節點，且它們均為一級邊緣節點；右邊社區僅有節點{57}是一級邊緣節點。邊緣節點{37}雖然有較高的度(度為7)，但由于它所有連邊的關聯度值均低于閾值，因此并不是社區核心節點。實驗結果表明，算法劃分結果很好地符合實際情況，社區劃分的正確率為100%。

圖2 Dolphins的社區劃分結果(P=2，threshhold=0.5,δ0=0.5)

兩個真實網絡的實驗結果表明了算法的有效性，且劃分結果能夠清晰辨識出核心節點、不同分級的邊緣節點，能夠方便地明確節點在社區中的作用和地位。

2.2 人工合成網絡

為評估算法的有效性，本文利用基準網絡模型[24]作為數據生成器，并用NMI對算法挖掘社區的精度進行評估。實驗生成3組無權無向圖數據。第1組數據主要用于測試不同的邊緣節點定級系數閾值(分別為0.2,0.3,0.4,0.5,0.6)對最終社區劃分精度的影響；第2組數據用于比較本文算法(δ=0.4)(與LTA算法[20](a=3)、FDCD算法[21]的社區劃分精度；第3組數據用于比較本文算法(δ=0.4)與LTA算法(a=3)、FDCD算法的運算效率。

(1)第1組數據設置結點個數為128，網絡結點最大度為30，社區最小最大規模分別為20,50，社區間重疊結點比例為0.05，網絡結點度分布指數為2，網絡社區規模分布指數為1。網絡結點平均度分別為5，10，15，重復生成10個網絡，最終社區劃分精度是是10個網絡上的平均值。

(2)第2組數據網絡結點平均度分別為{5,7,9,11,13,15}，其它參數與第1組數據的設置完全相同。每種配置生成10個網絡，最終幾種算法的社區劃分精度是10個網絡上的平均值。

(3)第3組數據節點為{500,1000,2000,3000,4000,5000}，節點平均度為10，其它參數與第1組相同。每種配置運行10次，得到10個網絡，最終幾種不同算法的運算時間是10個網絡上的平均值。

從圖3可以看到，定級系數閾值對網絡的社區劃分精度有很大影響?？傮w而言，在不同節點平均度的網絡中，都是隨著定級系數的閾值增大而降低。這是因為定級系數閥值越高，更多的邊緣節點可能因為與骨架節點和已定級邊緣節點的連接的比例過低，導致無法定級并歸類。

圖3 不同定級系數下網絡的社區劃分精度

圖4是第2組數據下，本文算法與LTA算法、FDCD算法的社區劃分精度比較。從圖中可以看到：①本文算法受人工網絡的節點平均度的影響很小，始終保持在較高的劃分精度水平。LTA算法和FDCD算法的精度都隨網絡結點平均度的增大而快速降低；②在不同結點平均度情況下，本文算法劃分精度最高，LTA算法次之，FDCD算法最低。這是因為本文算法以連接的關聯度來評價節點是否是核心節點，LTA算法以環路個數評價節點是否核心，FDCD算法以節點的鄰居數為引力計算的基礎，網絡結點平均度越大，社區之間出現大度節點的可能性越大，LTA算法和FDCD算法都很可能將這種節點視為社區核心節點，因此對精度有很大影響。

圖4 3種算法最終社區劃分精度比較

圖5是第3組數據下，3種算法的運算效率比較。從結果可以看到，本文算法與LTA算法效率相近，遠高于FDCD算法。LTA算法和本文算法的運算時間都隨網絡節點數近似線性增長；而FDCD算法的運行時間隨節點數快速增長。

圖5 3種算法效率比較

3 結束語

針對復雜網絡的社區挖掘問題，根據連邊的局部網絡信息，研究了網絡中互連節點之間的關系，并用關聯度進行衡量；關聯度同時能夠用于度量連邊在網絡中的重要程度。提出一種復雜網絡社區發現算法：算法選擇具有高關聯度的連邊兩端節點作為核心節點，互連的核心節點構成社區骨架，再根據引力確定邊緣節點的分類。由于社區骨架穩定，保證最終社區劃分結果穩定。實驗結果表明，算法具有很高的劃分精度和近似線性的計算復雜度。實際網絡的社區劃分結果也顯示本文算法避免了其它局部擴展方法可能將大度的邊緣節點視為社區核心節點的問題。今后工作將圍繞兩方面展開，一是定義基于關聯度的社區劃分評價標準，二是將關聯度用于復雜網絡重疊社區挖掘。

[1]Newman MEJ.Communities,modules and large-scale structure in networks[J].Nature Physics,2012,8(1):25-31.

[2]LIU Dayou,JIN Di,HE Dongxiao,et al.Community mining in complex network[J].Journal of Computer Research and Development,2013,50(10):2140-2154(in Chinese).[劉大有,金弟,何東曉,等.復雜網絡社區挖掘綜述[J].計算機研究與發展,2013,50(10):2140-2154.]

[3]GAN Wenyan,HE Nan,LI Deyi,et al.Community disco-very method in networks based on topological potential[J].Journal of Software,2009,20(8):2241-2254(in Chinese).[淦文燕,赫南,李德毅,等.一種基于拓撲勢的網絡社區發現方法[J].軟件學報,2009,20(8):2241-2254.]

[4]Rodrigo A,Ignacio M.Surprise maximization reveals the community structure of complex networks[J].Scientific Reports,2013,3(1):1060.

[5]LENG Zuofu.Community detection in complex networks based on greedy optimization[J].Acta Electronica Sinica,2014,42(4):723-728(in Chinese).[冷作福.基于貪婪優化技術的網絡社區發現算法研究[J].電子學報,2014,42(4):723-728.]

[6]Newman MEJ.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.

[7]Shang R,Bai J,Jiao L,et al.Community detection based on modularity and an improved genetic algorithm[J].Physica A,2013,392(5):1215-1231.

[8]Parsa MG,Mozayani N,Esmaeili A.An EDA-based community detection in complex networks[C]//7th International Symposium on Telecommunications,2014:476-480.

[9]Ma L,Gong M,Liu J,et al.Multi-level learning based memetic algorithm for community detection[J].Applied Soft Computing,2014,19(2):121-133.

[10]YANG Bo,LIU Dayou,LIU Jiming,et al.Complex network clustering algorithms[J].Journal of Software,2009,20(1):54-66(in Chinese).[楊博,劉大有,LIU Jiming,等.復雜網絡聚類方法[J].軟件學報,2009,20(1):54-66.]

[11]ZHU Mu,MENG Fanrong,ZHOU Yong.Density-based link clustering algorithm for overlapping community detection[J].Journal of Computer Research and Development,2013,50(12):2520-2530(in Chinese).[朱牧,孟凡榮,周勇.基于鏈接密度聚類的重疊社區發現[J].計算機研究與發展,2013,50(12):2520-2530.]

[12]JIANG Shengyi,YANG Bohong,LI Minmin,et al.Overlapping community detection algorithm based on two-stage clustering[J].Pattern Recognition and Artificial Intelligence,2015,28(11):983-991(in Chinese).[蔣盛益,楊博泓,李敏敏,等.基于二階段聚類的重疊社區發現算法[J].模式識別與人工智能,2015,28(11):983-991.]

[13]Ren W,Yan G,Liao X,et al.Simple probabilistic algorithm for detecting community structure[J].Physical Review E,2009,79(2):036111.

[14]Abbe E,Bandeira AS,Hall G.Exact recovery in the stoc-hastic block model[J].IEEE Transactions on Information Theory,2016,62(1):471-487.

[15]Girvan M,Newman MEJ.Community structure in social and biological networks[J].Proc of National Academy of Science,2002,9(12):7821-7826.

[16]JIN Di,LIU Jie,JIA Zhengxue,et al.K-Nearest-neighbor network based data clustering algorithm[J].Pattern Recognition and Artificial Intelligence,2010,23(4):546-551(in Chinese).[金弟,劉杰,賈正雪,等.基于K最近鄰網絡的數據聚類算法[J].模式識別與人工智能,2010,23(4):546-551.]

[17]Chen D,Shang M,Lv Z,et al.Detecting overlapping communities of weighted networks via a local algorithm[J].Physica A:Statistical Mechanics and its Applications,2010,389(19):4177-4187.

[18]Lee C,Reid F,McDaid A,et al.Detecting highly overlapping community structure by greedy clique expansion[C]//Proc of the 4th Int Workshop on Social Network Mining and Analysis.New York:ACM,2010:33-42.

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

[20]LIU Dayou,YANG Jianning,YANG Bo,et al.Community mining from complex networks based on loop tightness[J].Journal of Jilin University:Eng and Technol Ed,2013,43(1):98-105(in Chinese).[劉大有,楊建寧,楊博,等.基于環路緊密度的復雜網絡社區挖掘方法[J].吉林大學學報(工學版),2013,43(1):98-105.]

[21]SHUI Chao,CHEN Honghui,CHEN Tao,et al.A community detect algorithm on force-directed model[J].Journal of National University of Defense Technology,2014,36(4):163-168(in Chinese).[水超,陳洪輝,陳濤,等.力導向模型的復雜網絡社區挖掘算法[J].國防科技大學學報,2014,36(4):163-168.]

[22]Danon L,Diaz-Guilera A,Duch J,et al.Comparing community structure identification[J].Journal of Statistical Mecha-nics:Theory and Experiment,2005(9):P09008.

[23]Newman MEJ.Network data[EB/OL].[2013-04-19].http://www-personal.umich.edu/～mejn/netdata/.

[24]Lancichinetti A,Fortunato S.Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J].Physical Review E,2009,80(1):016118.