王 林,張一帆

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

基于節(jié)點(diǎn)相似度的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法

王 林,張一帆

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

針對(duì)現(xiàn)有的社團(tuán)檢測(cè)算法存在準(zhǔn)確度低、沒(méi)有充分考慮到有向網(wǎng)絡(luò)的方向特性等問(wèn)題，提出一種改進(jìn)的能夠適用于有向網(wǎng)絡(luò)的CNM(Newman 貪婪算法)社團(tuán)檢測(cè)算法。在算法設(shè)計(jì)中引入基于拓?fù)浣Y(jié)構(gòu)信息的有向網(wǎng)絡(luò)節(jié)點(diǎn)相似度算法，并重新定義模塊度增量函數(shù)ΔQs。使用一個(gè)計(jì)算機(jī)生成網(wǎng)絡(luò)和兩個(gè)實(shí)際網(wǎng)絡(luò)對(duì)算法進(jìn)行了測(cè)試并與已有算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，文章提出的算法能夠有效地檢測(cè)出有向網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。

社團(tuán)檢測(cè)；有向網(wǎng)絡(luò)；CNM算法；節(jié)點(diǎn)相似度

0 引言

社團(tuán)檢測(cè)是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和功能屬性的一項(xiàng)最基本工作。社團(tuán)可以看作是在網(wǎng)絡(luò)中具有相似屬性或者擔(dān)任類(lèi)似角色的節(jié)點(diǎn)的集合，這些社團(tuán)內(nèi)部的節(jié)點(diǎn)通常連接緊密，而社團(tuán)之間的節(jié)點(diǎn)連接較為稀疏。為了發(fā)現(xiàn)網(wǎng)絡(luò)中隱含的社團(tuán)結(jié)構(gòu)，傳統(tǒng)的社團(tuán)檢測(cè)算法主要基于模塊度指標(biāo)，將社團(tuán)檢測(cè)問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題，然后搜索目標(biāo)函數(shù)最優(yōu)的社團(tuán)結(jié)構(gòu)，如經(jīng)典的GN算法[1]和Newman快速算法[2]。然而，這類(lèi)算法本身存在局限性[3]，而且上述算法并沒(méi)有考慮到復(fù)雜網(wǎng)絡(luò)存在有向性和節(jié)點(diǎn)的相似度屬性。一方面，在現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)中，連接關(guān)系并不總是無(wú)向的，如社交網(wǎng)絡(luò)中的關(guān)注關(guān)系等；另一方面復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)之間具有不同的相似度，相似度的大小體現(xiàn)出節(jié)點(diǎn)之間關(guān)聯(lián)的緊密程度。

當(dāng)前的社團(tuán)檢測(cè)算法除了傳統(tǒng)基于模塊度優(yōu)化的方法[1-2,4]外，還包括考慮節(jié)點(diǎn)相似度、網(wǎng)絡(luò)的有向性特征的算法。文獻(xiàn)[5]在基于模塊度指標(biāo)的基礎(chǔ)上，同時(shí)考慮節(jié)點(diǎn)相似度，提出一種Similarity-CNM算法，并指出CNM算法中模塊度增量值的增加方向傾向于規(guī)模大的社團(tuán)而忽略小規(guī)模社團(tuán)，然而，該算法僅僅針對(duì)無(wú)向網(wǎng)絡(luò)社團(tuán)檢測(cè)，并不能處理有向網(wǎng)絡(luò)?？紤]到有向網(wǎng)絡(luò)這種更具有現(xiàn)實(shí)意義的網(wǎng)絡(luò)，文獻(xiàn)[6]利用基于局部信息的相似度計(jì)算方法將有向網(wǎng)絡(luò)對(duì)稱(chēng)化為無(wú)向網(wǎng)絡(luò)，再利用傳統(tǒng)的無(wú)向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法劃分出社團(tuán)，然而該無(wú)向化方法破壞了有向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[7]根據(jù)一個(gè)實(shí)際的有向網(wǎng)絡(luò)——微博社交網(wǎng)絡(luò)，提出一種基于共同關(guān)注和共同粉絲的微博用戶(hù)相似度，在此基礎(chǔ)上定義了新的模塊度函數(shù)，采用Newman快速算法的思想進(jìn)行社團(tuán)檢測(cè)。文獻(xiàn)[8]提出了k-Path共社團(tuán)鄰近相似性概念及計(jì)算方法，將有向網(wǎng)絡(luò)社團(tuán)檢測(cè)問(wèn)題轉(zhuǎn)化為無(wú)向加權(quán)網(wǎng)絡(luò)的社團(tuán)檢測(cè)問(wèn)題。

綜上所述，由于社團(tuán)檢測(cè)的基本思想是將屬性或角色相似的節(jié)點(diǎn)劃分到同一個(gè)集合中，考慮到基于模塊度優(yōu)化算法的局限性以及網(wǎng)絡(luò)的有向交互性，本文基于CNM算法提出一種有向網(wǎng)絡(luò)的社團(tuán)檢測(cè)算法。采用基于有向網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相似度算法計(jì)算出節(jié)點(diǎn)相似度，接著利用相似度改進(jìn)模塊度增量函數(shù)，有效地克服了CNM算法本身貪婪思想以及模塊度算法的局限性帶來(lái)的社團(tuán)劃分不準(zhǔn)確的缺點(diǎn)。

1 相關(guān)理論與算法

1.1 SimRank算法

SimRank[9]是一種有向圖上基于圖的拓?fù)浣Y(jié)構(gòu)信息來(lái)衡量任意兩個(gè)對(duì)象間相似程度的模型，該模型的核心思想為：如果兩個(gè)對(duì)象被其相似的對(duì)象所引用，那么這兩個(gè)對(duì)象也相似。SimRank的基本公式:

(1)

其中，|I(v)|表示節(jié)點(diǎn)v的入度，Ii(v)表示v的第i個(gè)入鄰居節(jié)點(diǎn)，c為衰減因子，且c∈(0,1)。

對(duì)于SimRank的迭代方程(1)能夠最終迭代趨近于一個(gè)固定的值，采用如下迭代方式來(lái)進(jìn)行SimRank的計(jì)算：

(2)

1.2 CNM算法

CNM算法首先構(gòu)造一個(gè)模塊度增量矩陣ΔQi,j，然后通過(guò)對(duì)它的元素進(jìn)行更新來(lái)得到模塊度最大時(shí)的一種社團(tuán)結(jié)構(gòu)。算法的流程如下：(1)初始化網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)為一個(gè)社團(tuán)；(2)計(jì)算網(wǎng)絡(luò)中任意兩個(gè)社團(tuán)合并后的模塊度增量ΔQi,j；(3)貪婪地選擇ΔQi,j最大時(shí)的兩個(gè)社團(tuán)進(jìn)行合并，更新與新社團(tuán)相連接的所有社團(tuán)的數(shù)據(jù)結(jié)構(gòu)，再重復(fù)上一步過(guò)程；(4)當(dāng)ΔQi,j<0時(shí)，算法終止。

1.3 有向網(wǎng)絡(luò)模塊度

為了衡量社團(tuán)檢測(cè)的質(zhì)量，Newman和Girvan定義了模塊度函數(shù)，定量地描述網(wǎng)絡(luò)中的社團(tuán)，衡量網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分?？紤]到有向網(wǎng)絡(luò)的方向特性，在此基礎(chǔ)上Leicht和Newman[10]提出適用于有向網(wǎng)絡(luò)的模塊度函數(shù)Qd，定義如下：

(3)

2 基于相似度的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法

本文算法的基本思想是利用節(jié)點(diǎn)之間相似度的變化來(lái)替代模塊度的增量，合并規(guī)則仍然采用CNM算法的合并規(guī)則，最后得到若干個(gè)基于相似度的社團(tuán)。

重新定義變量eij和ai為：

(4)

(5)

使用SimRank相似度替代模塊度增量后的增量矩陣，定義如下：

(6)

其中，n為網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)，s(i,j)是節(jié)點(diǎn)i與j之間的SimRank相似度值，Ds(i)是節(jié)點(diǎn)i與其他節(jié)點(diǎn)之間相似度的總和，M是所有節(jié)點(diǎn)相似度的總和。

算法步驟如下：

輸入：有向網(wǎng)絡(luò)G(V,E)；

輸出：社團(tuán)的劃分結(jié)果。

(1)使用SimRank算法對(duì)有向網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行相似度計(jì)算，得到節(jié)點(diǎn)之間的相似度矩陣S。

(2)對(duì)改進(jìn)后的模塊度增量矩陣ΔQs進(jìn)行初始化。

(3)對(duì)算法中的最大堆結(jié)構(gòu)H進(jìn)行初始化，堆結(jié)構(gòu)中存放的是ΔQs中每行的最大值。

(4)選擇最大堆結(jié)構(gòu)H中的堆頂元素，根據(jù)CNM算法的模塊度增量更新規(guī)則對(duì)增量矩陣對(duì)應(yīng)的行與列進(jìn)行合并，并且對(duì)增量矩陣以及最大堆結(jié)構(gòu)進(jìn)行更新。

(5)所有的節(jié)點(diǎn)歸于一個(gè)社團(tuán)內(nèi)，算法結(jié)束，否則繼續(xù)進(jìn)行步驟(4)。

3 實(shí)驗(yàn)結(jié)果與分析

為了測(cè)試算法的有效性，本文使用一個(gè)計(jì)算機(jī)生成網(wǎng)絡(luò)和兩個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行驗(yàn)證。其中計(jì)算機(jī)生成網(wǎng)絡(luò)采用LFR(Lancichinetti-Fortunato-Radicchi)基準(zhǔn)網(wǎng)絡(luò)[11-12]生成有向網(wǎng)絡(luò)dirnet，真實(shí)網(wǎng)絡(luò)采用poblogs[13]政治博客圈網(wǎng)絡(luò)和wiki-vote[14]維基百科投票網(wǎng)絡(luò)。

LFR基準(zhǔn)網(wǎng)絡(luò)是近年來(lái)社團(tuán)檢測(cè)中普遍應(yīng)用的計(jì)算機(jī)生成模擬網(wǎng)絡(luò)，通過(guò)設(shè)置不同的網(wǎng)絡(luò)參數(shù)和社團(tuán)參數(shù)來(lái)生成帶有劃分標(biāo)準(zhǔn)的復(fù)雜網(wǎng)絡(luò)。該算法提供的社團(tuán)劃分標(biāo)準(zhǔn)即同時(shí)生成原始社團(tuán)，解決了驗(yàn)證算法正確性的問(wèn)題。使用LFR計(jì)算機(jī)生成網(wǎng)絡(luò)時(shí)需要設(shè)置的主要參數(shù)如表1所示。

表1 LFR計(jì)算機(jī)生成網(wǎng)絡(luò)主要參數(shù)

3.1 計(jì)算機(jī)生成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，LFR計(jì)算機(jī)生成網(wǎng)絡(luò)中的具體參數(shù)設(shè)置為：節(jié)點(diǎn)數(shù)N=62，平均入度數(shù)k=10，最大入度數(shù)kmax=16，混合參數(shù)mu=0.2，最小社團(tuán)節(jié)點(diǎn)數(shù)cmin=9，最大社團(tuán)節(jié)點(diǎn)數(shù)cmax=27。

LFR計(jì)算機(jī)生成的初始有向網(wǎng)絡(luò)如圖1所示，其標(biāo)準(zhǔn)劃分社團(tuán)結(jié)構(gòu)如圖2所示。

圖1 LFR計(jì)算機(jī)生成的有向初始網(wǎng)絡(luò)

圖2 LFR計(jì)算機(jī)生成網(wǎng)絡(luò)社團(tuán)劃分標(biāo)準(zhǔn)結(jié)構(gòu)

利用本文提出的算法對(duì)LFR計(jì)算機(jī)生成網(wǎng)絡(luò)進(jìn)行社團(tuán)檢測(cè)，得出社團(tuán)劃分結(jié)果如表2所示。

表2 本文算法的劃分結(jié)果

表3 本文算法與文獻(xiàn)[10]算法對(duì)比

可見(jiàn)本文算法的社團(tuán)檢測(cè)結(jié)果與圖2中的標(biāo)準(zhǔn)社團(tuán)劃分結(jié)果相一致。利用式(3)計(jì)算出當(dāng)前社團(tuán)檢測(cè)結(jié)果的模塊度值為0.433，符合模塊度取值范圍，表明本文算法具有良好的準(zhǔn)確性。

3.2 算法中參數(shù)的選取

本文算法中，相似度的計(jì)算決定著最后的社團(tuán)檢測(cè)結(jié)果，對(duì)于SimRank算法，其中衰減因子參照文獻(xiàn)[9]中的取值為c=0.8。SimRank的準(zhǔn)確度是隨著迭代次數(shù)k的增加而增加的，理論上當(dāng)k趨于無(wú)窮大時(shí)準(zhǔn)確度最高。鑒于真實(shí)網(wǎng)絡(luò)大多為稀疏的[15]，在有限的迭代次數(shù)內(nèi)能夠及時(shí)收斂，因此可以通過(guò)實(shí)驗(yàn)選取最佳的k值。

選取poblogs和wiki-vote作為測(cè)試網(wǎng)絡(luò)，對(duì)于不同的k值運(yùn)行10次算法，分別計(jì)算迭代次數(shù)k取不同值時(shí)對(duì)應(yīng)的模塊度平均值。

如圖3所示，模塊度隨著迭代次數(shù)的增加呈增長(zhǎng)趨勢(shì)，表明迭代使得社團(tuán)結(jié)構(gòu)更加明顯。對(duì)于poblogs，k=5時(shí)，模塊度有最大值Q=0.427，表現(xiàn)為兩個(gè)明顯的社團(tuán)結(jié)構(gòu)；對(duì)于wiki-vote，k=7時(shí)，模塊度最大值Q=0.416。

圖3 模塊度Q值隨迭代次數(shù)的變化趨勢(shì)

3.3 對(duì)比實(shí)驗(yàn)

在文獻(xiàn)[4]中，Newman使用CNM算法分析了Amazon.com網(wǎng)上書(shū)店中頁(yè)面的鏈接關(guān)系網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含高達(dá)40萬(wàn)個(gè)節(jié)點(diǎn)和200多萬(wàn)條邊，最終劃分出10個(gè)社團(tuán)。其中，最大社團(tuán)包含114 538個(gè)節(jié)點(diǎn)，第二大的社團(tuán)規(guī)模同樣也不小，包含92 276個(gè)節(jié)點(diǎn)，而最小的社團(tuán)只有947個(gè)節(jié)點(diǎn)。這樣過(guò)大或者過(guò)小的社團(tuán)規(guī)模有可能并不利于社團(tuán)的發(fā)展。

利用本文算法與文獻(xiàn)[10]中提出的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法在3個(gè)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。

由表3數(shù)據(jù)可知，在LFR模型生成的dirnet網(wǎng)絡(luò)中，由于在計(jì)算中充分考慮到有向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，本文算法比文獻(xiàn)[10]中算法社團(tuán)檢測(cè)結(jié)果更好，而文獻(xiàn)[10]中的算法是通過(guò)譜分析對(duì)有向模塊度求解最大值，本身是一種模塊度優(yōu)化算法，并不能充分考慮到網(wǎng)絡(luò)的結(jié)構(gòu)。同樣，在ploblogs數(shù)據(jù)集中，本文算法的社團(tuán)檢測(cè)結(jié)果也顯示為兩個(gè)社團(tuán)，其中有15個(gè)節(jié)點(diǎn)沒(méi)有被正確地劃分，但模塊度最優(yōu)值為0.427，社團(tuán)檢測(cè)結(jié)果仍然表現(xiàn)出較好的社團(tuán)結(jié)構(gòu)。在wiki-vote數(shù)據(jù)集的實(shí)驗(yàn)中，使用本文算法雖然在模塊度上比不上文獻(xiàn)[10]的算法，但是檢測(cè)出的社團(tuán)規(guī)模均勻程度卻比較好，在大規(guī)模的網(wǎng)絡(luò)中，有時(shí)社團(tuán)規(guī)模更加均勻。

4 結(jié)束語(yǔ)

本文基于CNM算法提出了基于相似度的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法，與文獻(xiàn)[10]提出的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法相比，不僅能夠處理有向網(wǎng)絡(luò)，而且檢測(cè)出的社團(tuán)規(guī)模也更加合理。實(shí)驗(yàn)結(jié)果表明，本文提出的算法不僅能夠充分考慮到有向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，而且避免了模塊度本身的局限性，使得劃分出的社團(tuán)規(guī)模更加均勻。

[1] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.

[2] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J]. Physica Review E, 2004, 69(6): 066133.

[3] FORTUNATO S, BARTHéLEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1):36-41.

[4] CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks.[J]. Physical Review E, 2010, 70(6):264-277.

[5] ALFALAHI K, ATIF Y, HAROUS S. Community detection in social networks through similarity virtual networks[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2013:1116-1123.

[6] ZHANG F, WU B, WANG B, et al. Community detection in directed graphs via node similarity computation[C]. IET International Conference on Wireless, Mobile and Multimedia Networks, 2013:258-261.

[7] 孫怡帆, 李賽. 基于相似度的微博社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(12):2797-2807.

[8] 張海燕, 梁循, 周小平. 針對(duì)有向圖的局部擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法[J]. 數(shù)據(jù)采集與處理, 2015,30(3):683-693.

[9] JEH G, WIDOM J. SimRank: a measure of structural-context similarity[C]. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2002:538-543.

[10] LEICHT E A, NEWMAN M E. Community structure in directed networks.[J]. Physical Review Letters, 2007, 100(11):2339-2340.

[11] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(2):561-570.

[12] LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 80(2):145-148.

[13] ADAMIC L A, GLANCE N. The political blogosphere and the 2004 U.S. election: divided they blog[C]. International Workshop on Link Discovery, ACM, 2005:36-43.

[14] LESKOVEC J, HUTTENLOCHER D, KLEIBERG J. Predicting positive and negative links in online social networks[J]. Computer Science, 2010,36(7):641-650.

[15] Chen Jie, SAAD Y. Dense subgraph extraction with application to community detection[J].IEEE Transactions on Knowledge & Data Engineering, 2012, 24(7): 1216-1230.

Community detection in directed networks based on vertex similarities

Wang Lin, Zhang Yifan

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

Through the study of the existing community detection algorithm, problems of low accuracy rate, ignore the direction of the edge are found, and an improved CNM algorithm based on similarity in directed networks is presented. The new algorithm introduces a similarity algorithm based on topological information to calculate similarity between the pairs of nodes in the given direct networks and defines a newΔQsfunctionforCNMalgorithm.Theperformanceoftheproposedalgorithmistestedandcomparedwithotheralgorithmsononecomputer-generatednetworkandtworealnetworks.Experimentalresultsshowthatthealgorithmpresentedinthispaperisratherefficienttodetectcommunitiesofdirectednetworks.

community detection; directed networks; CNM algorithm; node similarity

TP

ADOI： 10.19358/j.issn.1674- 7720.2017.03.006

王林,張一帆.基于節(jié)點(diǎn)相似度的有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法[J].微型機(jī)與應(yīng)用，2017,36(3)：19-22.

2016-10-07)

王林(1963-)，男，博士，教授，主要研究方向:復(fù)雜系統(tǒng)及控制理論。

張一帆(1991-)，男，碩士研究生，主要研究方向:復(fù)雜網(wǎng)絡(luò)，大數(shù)據(jù)與云計(jì)算。