一種優(yōu)化共同鄰居影響的動(dòng)態(tài)距離社區(qū)發(fā)現(xiàn)算法

萬甲鑫

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

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

DOI：10. 11907/rjdk. 201350

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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)用于真實(shí)世界的復(fù)雜系統(tǒng)中，如蛋白質(zhì)網(wǎng)絡(luò)研究、計(jì)算機(jī)網(wǎng)絡(luò)路由分析、交通網(wǎng)絡(luò)路徑規(guī)劃以及新聞傳播學(xué)等領(lǐng)域[1-3]。許多復(fù)雜系統(tǒng)可以用圖表示，通過定義規(guī)則，將一個(gè)組件或?qū)嶓w抽象為一個(gè)節(jié)點(diǎn)，而組件或?qū)嶓w之間的連接描述為節(jié)點(diǎn)之間的連邊[4]。

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

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

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

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

1.1 相關(guān)定義

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

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

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

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

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

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

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

2 改進(jìn)Attractor算法

2.1 改進(jìn)方法

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

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

2.2 算法流程

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

3.1 評(píng)價(jià)指標(biāo)

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

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

模塊度[15]（Modularity）是另一種衡量社區(qū)劃分質(zhì)量評(píng)價(jià)指標(biāo)。計(jì)算模塊度不需要知道真實(shí)社區(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é)點(diǎn)[i]的度值，[ci]表示節(jié)點(diǎn)[i]的社區(qū)，[δ（?）]是克羅內(nèi)克函數(shù)，如果節(jié)點(diǎn)[i]、[j]位于同一個(gè)社區(qū)，[δ（ci，cj）]等于1，否則等于0。

3.2 實(shí)驗(yàn)結(jié)果

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

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

實(shí)驗(yàn)結(jié)果如圖1所示，可以看出改進(jìn)算法在平均度較大的網(wǎng)絡(luò)上準(zhǔn)確度明顯提升。當(dāng)平均度較小時(shí)（[k]=5），改進(jìn)算法和Attractor的NMI值與模塊度值幾乎一樣。但隨著[k]增加到10和15時(shí)，改進(jìn)算法準(zhǔn)確度提升最大。當(dāng)[k]增加到20和25時(shí)，準(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é)點(diǎn)數(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時(shí)，兩種算法都能準(zhǔn)確檢測(cè)出社區(qū)，此時(shí)NMI值為1。當(dāng)混合參數(shù)在0.3～0.6之間時(shí)，改進(jìn)算法帶來的提升逐漸顯現(xiàn)出來。當(dāng)混合參數(shù)大于0.6的時(shí)候，由于網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變得復(fù)雜，即多數(shù)節(jié)點(diǎn)度值相差不多，改進(jìn)算法和Attractor算法幾乎一樣。

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

4 結(jié)語(yǔ)

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

參考文獻(xià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ò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J].? 國(guó)防科技大學(xué)學(xué)報(bào)， 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]. 計(jì)算機(jī)系統(tǒng)應(yīng)用，2016，25（9）：212-215.

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

[8] 王莉，程學(xué)旗. 在線社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)及演化[J]. 計(jì)算機(jī)學(xué)報(bào)，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ù)測(cè)[J]. 電子科技大學(xué)學(xué)報(bào)，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é)任編輯：杜能鋼）