萬甲鑫

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

關(guān)鍵詞：社區(qū)發(fā)現(xiàn);復(fù)雜網(wǎng)絡(luò);動態(tài)演化;動態(tài)距離

DOI：10. 11907/rjdk. 201350

中圖分類號：TP312文獻標(biāo)識碼：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 引言

近年來，復(fù)雜網(wǎng)絡(luò)理論與研究方法越來越多地應(yīng)用于真實世界的復(fù)雜系統(tǒng)中，如蛋白質(zhì)網(wǎng)絡(luò)研究、計算機網(wǎng)絡(luò)路由分析、交通網(wǎng)絡(luò)路徑規(guī)劃以及新聞傳播學(xué)等領(lǐng)域[1-3]。許多復(fù)雜系統(tǒng)可以用圖表示，通過定義規(guī)則，將一個組件或?qū)嶓w抽象為一個節(jié)點，而組件或?qū)嶓w之間的連接描述為節(jié)點之間的連邊[4]。

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

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

1 基于動態(tài)距離的Attractor算法

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

1.1 相關(guān)定義

1.2 動態(tài)距離交互模型

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

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

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

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

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

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

2 改進Attractor算法

2.1 改進方法

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

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

2.2 算法流程

（1）初始狀態(tài)下，使用Jaccard距離計算[t=0]時網(wǎng)絡(luò)中所有節(jié)點對間距離。

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

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

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

（5）刪除距離等于1的邊，最終得到網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

3 實驗分析

對比改進算法和Attractor算法在不同結(jié)構(gòu)人工合成網(wǎng)絡(luò)上的結(jié)果。在同一組參數(shù)下，人工合成網(wǎng)絡(luò)生成20個網(wǎng)絡(luò)，然后取這20個網(wǎng)絡(luò)評價指標(biāo)的平均值作為該組參數(shù)最終實驗結(jié)果。

3.1 評價指標(biāo)

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

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

模塊度[15]（Modularity）是另一種衡量社區(qū)劃分質(zhì)量評價指標(biāo)。計算模塊度不需要知道真實社區(qū)結(jié)構(gòu)，而是與網(wǎng)絡(luò)相應(yīng)的零模型作比較，度量算法劃分結(jié)果質(zhì)量。模塊度取值范圍在0和1之間，表示如下：

其中[，m]是網(wǎng)絡(luò)邊數(shù)，[A]是網(wǎng)絡(luò)鄰接矩陣，[Aij]表示邊[e=（i，j）]的權(quán)值，無權(quán)網(wǎng)絡(luò)中為1，[ki]表示節(jié)點[i]的度值，[ci]表示節(jié)點[i]的社區(qū)，[δ（?）]是克羅內(nèi)克函數(shù)，如果節(jié)點[i]、[j]位于同一個社區(qū)，[δ（ci，cj）]等于1，否則等于0。

3.2 實驗結(jié)果

為評估改進算法與原算法在社區(qū)檢測準(zhǔn)確度上的差異，采用LFR[16]人工合成網(wǎng)絡(luò)作為評測網(wǎng)絡(luò)，以NMI和模塊度值作為準(zhǔn)確度評價指標(biāo)。

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

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

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

圖2顯示兩種算法在社區(qū)大小位于10～50之間網(wǎng)絡(luò)上的比較結(jié)果。由圖2可知，當(dāng)混合參數(shù)小于0.2時，兩種算法都能準(zhǔn)確檢測出社區(qū)，此時NMI值為1。當(dāng)混合參數(shù)在0.3～0.6之間時，改進算法帶來的提升逐漸顯現(xiàn)出來。當(dāng)混合參數(shù)大于0.6的時候，由于網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變得復(fù)雜，即多數(shù)節(jié)點度值相差不多，改進算法和Attractor算法幾乎一樣。

如圖3所示，當(dāng)社區(qū)大小位于20～100之間時，改進算法獲得明顯提升。當(dāng)混合參數(shù)μ小于0.4時，改進算法在NMI值上明顯高于Attractor算法。隨著混合參數(shù)的逐漸增大，改進算法提升效果逐漸減小，不過仍好于Attractor算法，能更好地檢測出網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

4 結(jié)語

本文提出一種改進的Attractor社區(qū)發(fā)現(xiàn)算法。在Attractor算法動態(tài)距離交互模型中，針對大度節(jié)點影響周圍節(jié)點距離更新問題，引入大度節(jié)點不利系數(shù)，改進共同鄰居交互影響公式，提高了社區(qū)發(fā)現(xiàn)準(zhǔn)確度。實驗結(jié)果表明，改進算法可在多個網(wǎng)絡(luò)上獲得更高的NMI值和模塊度值，準(zhǔn)確度更高，且在社區(qū)規(guī)模較大的網(wǎng)絡(luò)中效果更明顯。后續(xù)將研究節(jié)點對度值差異對另外兩種交互模式的影響，以期獲得更高的社區(qū)發(fā)現(xiàn)準(zhǔn)確度。

參考文獻：

[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] 駱志剛， 丁凡， 蔣曉舟，等.? 復(fù)雜網(wǎng)絡(luò)社團發(fā)現(xiàn)算法研究新進展[J].? 國防科技大學(xué)學(xué)報， 2011， 33（1）：47-52.

[4] 汪小帆， 李翔， 陳關(guān)榮.? 網(wǎng)絡(luò)科學(xué)導(dǎo)論[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] 李磊，倪林. 基于模塊度優(yōu)化的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J]. 計算機系統(tǒng)應(yīng)用，2016，25（9）：212-215.

[7] 劉苗苗，郭景峰，馬曉陽，等. 基于共鄰節(jié)點相似度的加權(quán)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J]. 四川大學(xué)學(xué)報（自然科學(xué)版），2018，55（1）：89-98.

[8] 王莉，程學(xué)旗. 在線社會網(wǎng)絡(luò)的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J]. 計算機學(xué)報，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] 呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J]. 電子科技大學(xué)學(xué)報，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.

（責(zé)任編輯：杜能鋼）