一種優化共同鄰居影響的動態距離社區發現算法

萬甲鑫

摘 要：在眾多社區發現算法中，Attractor算法是一種快速的社區發現算法，具有社區檢測準確率高的優點。為解決Attractor算法在距離更新過程中節點對度值相差太大，影響小度節點所屬社區判斷問題，提出一種優化共同鄰居影響的Attractor社區發現算法。該算法在Attractor算法提出的動態距離節點交互模型基礎上，考慮節點對兩者度值差異，通過在節點對與共同鄰居交互模式中增加一個大度節點不利系數，以增加小度節點對鄰居的吸引作用。采用LFR基準網絡，在不同結構網絡上驗證改進算法的有效性。實驗結果表明，改進算法與Attractor算法相比社區發現準確度更高。

關鍵詞：社區發現;復雜網絡;動態演化;動態距離

DOI：10. 11907/rjdk. 201350

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）010-0142-04

Abstract： Among many community discovery algorithms， the attractor algorithm is a fast community discovery algorithm， and has the advantages of high community detection accuracy. In order to solve the problem that the difference of degree value between nodes in the process of distance update affects the community judgment of small degree nodes， a community discovery algorithm of attractor which optimizes the influence of common neighbors is proposed. Based on the dynamic distance node interaction model proposed by the attractor algorithm， this algorithm takes into account the difference of the degree values between the two nodes. By adding a negative coefficient of large nodes in the interaction mode between the node pair and the common neighbor， the attraction of the small node to the neighbor is increased， and the LFR benchmark network is used to verify the effectiveness of the improved algorithm on different networks.

Key Words： community detection; complex network; dynamic evolution; distance dynamics

0 引言

近年來，復雜網絡理論與研究方法越來越多地應用于真實世界的復雜系統中，如蛋白質網絡研究、計算機網絡路由分析、交通網絡路徑規劃以及新聞傳播學等領域[1-3]。許多復雜系統可以用圖表示，通過定義規則，將一個組件或實體抽象為一個節點，而組件或實體之間的連接描述為節點之間的連邊[4]。

為更進一步探索復雜系統內部潛在的結構特征，復雜網絡的社區發現方向成為研究熱點[5-8]。受到網絡動力學啟發，邵俊明等[9]提出基于節點間的距離動力學劃分社區Attractor算法，通過模擬節點間距離的動態演化，最終發現網絡的潛在社區結構。Attractor算法可直接根據網絡拓撲結構得到社區劃分結果，劃分結果準確，并且可以發現不同規模大小社區，且時間復雜度較低，適用于大規模網絡;文獻[10]將動態距離模型擴展到兩部分圖中，驗證了動態距離在多屬性圖中的有效性;文獻[11]研究先驗知識對Attractor算法的影響，提出的半監督Attracotor算法在有先驗知識情況下可獲得非常高的準確度;文獻[12]利用網絡三角結構壓縮原始網絡，并通過計算社區相似度將Attracotor用于重疊社區檢測，獲得較好結果。

以上方法都對Attracotor算法的高準確度和可擴展性作了深入研究，但是對Attractor算法的交互模式研究還比較少。本文在研究度值相差較大的節點對距離變化影響情況后，通過引入大度節點不利系數[13]，改進共同鄰居交互模式對節點距離的影響。在帶有真實社區標注網絡上進行實驗，驗證改進算法可提升社區劃分準確度。

1 基于動態距離的Attractor算法

Attractor算法中的動態距離交互模型將網絡看作一個節點間距離不斷變化的動態系統。系統初始時刻，每對節點都有一個初始距離，隨著系統逐漸演化，節點會和周圍的鄰居節點產生交互，而這些交互行為會造成節點間距離改變。節點鄰居分為3種類型，節點與不同類型的鄰居交互會對節點間距離產生不同影響。3種類型鄰居分別為兩個節點自身、節點對的共同鄰居以及節點對各自的獨有鄰居。節點在3種鄰居影響下距離會逐漸變化，一些節點對之間的距離逐漸減小，最終減小到最小值0，則該對節點屬于同一個社區。相反，另一些節點距離會慢慢增加，最終增加到最大值1，則該對節點屬于不同社區。

1.1 相關定義

1.2 動態距離交互模型

節點[u]和節點[v]會與周圍3種不同類型的鄰居產生交互，這些交互會對距離[d（u，v）]產生影響，3種交互模式如下：

（1）直接連接影響。節點[u]和節點[v]直接連接的交互模式會吸引兩者互相靠近，造成距離[d（u，v）]減小，使用函數DI表示如下：

（2）共同鄰居影響。節點[u]和節點[v]與共同鄰居[CN=Γu∩Γ（v）]的交互也會吸引兩者互相靠近，造成距離[d（u，v）]減小，使用函數CI表示如下：

（3）獨有鄰居影響。節點[u]和節點[v]與各自獨有鄰居[ENu]、[ENv]的交互也會對距離[d（u，v）]產生影響。但由于節點的獨有鄰居和另一端節點沒有連接，無法直接判斷節點[u]的獨有鄰居會造成距離[d（u，v）]增加還是減小。Attractor算法使用一個凝聚參數[λ]決定獨有鄰居對[d（u，v）]的影響，如式（6）所示。

其中，[ρ（x，y）]表示節點[u]的獨有鄰居[x]對[d（u，v）]是正影響還是負影響。[d（x，v）]表示獨有鄰居[x]和節點[v]之間的距離，[1-d（x，v）]表示獨有鄰居[x]和節點[v]之間的相似性。當相似性大于閾值[λ]時，[ρ（x，y）]為正值，則獨有鄰居[x]和節點[u]交互會引起[d（u，v）]減小;當相似性小于閾值[λ]時，[ρ（x，y）]為負值，會引起[d（u，v）]增加。獨有鄰居影響可用函數EI表示。

通過以上3種交互模式作用，可得到節點間在[t+1]時刻的距離更新值[d（u，v;t+1）]，如式（8）所示。

2 改進Attractor算法

2.1 改進方法

Attractor算法在計算初始距離時，大度節點與其周圍鄰居距離都非常接近于1。如果大度節點的鄰居度值較小，且兩者共同鄰居數很少，則根據式（8）計算的距離更新量一直都在增加，小度節點在距離演化過程中會逐漸遠離周圍大度鄰居，最終與所有的大度鄰居距離都為1，單獨位于一個社區。為降低大度節點對周圍鄰居距離更新的影響，考慮給共同鄰居交互模式CI增加一個大度節點不利系數，以此消弱小度節點和大度節點的度值差異。改進后的CI如式（9）所示。

如果兩者度值比較接近，則改進后的CI對原有CI影響不大;如果兩者度值相差較大，則改進后的CI可有效消除大度節點對距離更新的影響。

2.2 算法流程

（1）初始狀態下，使用Jaccard距離計算[t=0]時網絡中所有節點對間距離。

（2）根據式（4）、式（7）、式（9）分別計算DI、改進后的CI、EI，然后根據式（8）得到每個節點對下一時刻的距離更新量[d（u，v;t+1）]。

（3）判斷當前距離更新量[d（u，v;t+1）]是否大于0或小于1。如果小于0，則認為距離達到最小值0，同時不再更新該節點對距離;如果大于1，則認為距離達到最大值1并不再更新該節點對距離。

（4）重復步驟（2）、步驟（3），直到所有距離都收斂到0或1。

（5）刪除距離等于1的邊，最終得到網絡中的社區結構。

3 實驗分析

對比改進算法和Attractor算法在不同結構人工合成網絡上的結果。在同一組參數下，人工合成網絡生成20個網絡，然后取這20個網絡評價指標的平均值作為該組參數最終實驗結果。

3.1 評價指標

標準化互信息[14]（Normalized Mutual Information，NMI）用于評價實際社區和算法劃分出來的社區相似程度。NMI取值范圍在0和1之間，如式（12）所示。

其中，[X]表示算法劃分的社區結構，[Y]表示真實社區結構，[I（X，Y）]表示[X，Y]的互信息，[H（X），H（Y）]分別表示[X，Y]的信息熵。NMI值越高，表示[X，Y]越相似。

模塊度[15]（Modularity）是另一種衡量社區劃分質量評價指標。計算模塊度不需要知道真實社區結構，而是與網絡相應的零模型作比較，度量算法劃分結果質量。模塊度取值范圍在0和1之間，表示如下：

其中[，m]是網絡邊數，[A]是網絡鄰接矩陣，[Aij]表示邊[e=（i，j）]的權值，無權網絡中為1，[ki]表示節點[i]的度值，[ci]表示節點[i]的社區，[δ（?）]是克羅內克函數，如果節點[i]、[j]位于同一個社區，[δ（ci，cj）]等于1，否則等于0。

3.2 實驗結果

為評估改進算法與原算法在社區檢測準確度上的差異，采用LFR[16]人工合成網絡作為評測網絡，以NMI和模塊度值作為準確度評價指標。

首先控制網絡平均度從5變化到20，對比改進算法和Attractor的實驗結果。網絡其它參數為：網絡節點數[N=2 000]，混合參數[μ=0.5]，最大度值[kmax=50]，度分布參數[γ]=2，社區大小分布參數[β=1]，最小社區大小[Cmin=10]，最大社區大小[Cmax=50]。

實驗結果如圖1所示，可以看出改進算法在平均度較大的網絡上準確度明顯提升。當平均度較小時（[k]=5），改進算法和Attractor的NMI值與模塊度值幾乎一樣。但隨著[k]增加到10和15時，改進算法準確度提升最大。當[k]增加到20和25時，準確度提升不是很明顯。

生成兩種不同社區大小的LFR基準網絡，控制網絡最小社區大小和最大網絡社區大小分別為[Cmin=10]、[Cmax=50]以及[Cmin=20]、[Cmax=100]，并且控制混合參數[μ]從0.1變化到0.8。網絡其它參數分別固定為：網絡節點數[N=1 000]，平均度[k=20]，最大度值[kmax=50]，度分布參數[γ]=2，社區大小分布參數[β=1]。混合參數[μ]可用來控制網絡的社區結構復雜度，[μ]越大表示社區結構越復雜，社區劃分也越困難。

圖2顯示兩種算法在社區大小位于10～50之間網絡上的比較結果。由圖2可知，當混合參數小于0.2時，兩種算法都能準確檢測出社區，此時NMI值為1。當混合參數在0.3～0.6之間時，改進算法帶來的提升逐漸顯現出來。當混合參數大于0.6的時候，由于網絡社區結構變得復雜，即多數節點度值相差不多，改進算法和Attractor算法幾乎一樣。

如圖3所示，當社區大小位于20～100之間時，改進算法獲得明顯提升。當混合參數μ小于0.4時，改進算法在NMI值上明顯高于Attractor算法。隨著混合參數的逐漸增大，改進算法提升效果逐漸減小，不過仍好于Attractor算法，能更好地檢測出網絡中的社區結構。

4 結語

本文提出一種改進的Attractor社區發現算法。在Attractor算法動態距離交互模型中，針對大度節點影響周圍節點距離更新問題，引入大度節點不利系數，改進共同鄰居交互影響公式，提高了社區發現準確度。實驗結果表明，改進算法可在多個網絡上獲得更高的NMI值和模塊度值，準確度更高，且在社區規模較大的網絡中效果更明顯。后續將研究節點對度值差異對另外兩種交互模式的影響，以期獲得更高的社區發現準確度。

參考文獻：

[1] FORTUNATO S. Community detection in graphs[J].? Physics reports， 2010， 486（3-5）： 75-174.

[2] FORTUNATO S， HRIC D. Community detection in networks： a user guide[J].? Physics reports， 2016， 659（9）： 1-44.

[3] 駱志剛， 丁凡， 蔣曉舟，等.? 復雜網絡社團發現算法研究新進展[J].? 國防科技大學學報， 2011， 33（1）：47-52.

[4] 汪小帆， 李翔， 陳關榮.? 網絡科學導論[M].? 北京：高等教育出版社， 2012.

[5] HRIC D， DARST R K， FORTUNATO S. Community detection in networks： structural communities versus ground truth[J].? Physical Review E， 2014， 90（6）： 62-80.

[6] 李磊，倪林. 基于模塊度優化的標簽傳播社區發現算法[J]. 計算機系統應用，2016，25（9）：212-215.

[7] 劉苗苗，郭景峰，馬曉陽，等. 基于共鄰節點相似度的加權網絡社區發現方法[J]. 四川大學學報（自然科學版），2018，55（1）：89-98.

[8] 王莉，程學旗. 在線社會網絡的動態社區發現及演化[J]. 計算機學報，2015，38（2）：219-237.

[9] SHAO J， HAN Z， YANG Q， et al. Community detection based on distance dynamics[C]. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2015： 1075-1084.

[10] SUN H， CHNG E， YONG X， et al. A fast community detection method in bipartite networks by distance dynamics[J].? Physica A： Statistical Mechanics and its Applications，2018， 496（15）：108-120.

[11] FAN L， XU S， LIU D， et al. Semi-supervised community detection based on distance dynamics[J].? IEEE Access， 2018， 6（9）： 37261-37271.

[12] XIANG B， GUO K， LIU Z， et al. An overlapping community detection algorithm based on triangle coarsening and dynamic distance[C]. CCF Conference on Computer Supported Cooperative Work and Social Computing，Springer， Singapore， 2018： 285-300.

[13] 呂琳媛. 復雜網絡鏈路預測[J]. 電子科技大學學報，2010，39（5）： 651-661.

[14] STREHL A， GHOSH J. Cluster ensembles——a knowledge reuse framework for combining multiple partitions[J].? Journal of machine learning research， 2002， 3（12）： 583-617.

[15] NEWMAN M E J. Modularity and community structure in networks[J].? Proceedings of the national academy of sciences， 2006， 103（23）： 8577-8582.

[16] LANCICHINETTI A， FORTUNATO S， RADICCHI F. Benchmark graphs for testing community detection algorithms[J].? Physical review E， 2008， 78（4）： 46-110.

（責任編輯：杜能鋼）