王 林,張一帆

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

基于節(jié)點相似度的有向網(wǎng)絡社團檢測算法

王 林,張一帆

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

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

社團檢測；有向網(wǎng)絡；CNM算法；節(jié)點相似度

0 引言

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

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

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

1 相關理論與算法

1.1 SimRank算法

SimRank[9]是一種有向圖上基于圖的拓撲結構信息來衡量任意兩個對象間相似程度的模型，該模型的核心思想為：如果兩個對象被其相似的對象所引用，那么這兩個對象也相似。SimRank的基本公式:

(1)

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

對于SimRank的迭代方程(1)能夠最終迭代趨近于一個固定的值，采用如下迭代方式來進行SimRank的計算：

(2)

1.2 CNM算法

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

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

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

(3)

2 基于相似度的有向網(wǎng)絡社團檢測算法

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

重新定義變量eij和ai為：

(4)

(5)

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

(6)

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

算法步驟如下：

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

輸出：社團的劃分結果。

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

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

(3)對算法中的最大堆結構H進行初始化，堆結構中存放的是ΔQs中每行的最大值。

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

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

3 實驗結果與分析

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

LFR基準網(wǎng)絡是近年來社團檢測中普遍應用的計算機生成模擬網(wǎng)絡，通過設置不同的網(wǎng)絡參數(shù)和社團參數(shù)來生成帶有劃分標準的復雜網(wǎng)絡。該算法提供的社團劃分標準即同時生成原始社團，解決了驗證算法正確性的問題。使用LFR計算機生成網(wǎng)絡時需要設置的主要參數(shù)如表1所示。

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

3.1 計算機生成網(wǎng)絡上的實驗結果

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

LFR計算機生成的初始有向網(wǎng)絡如圖1所示，其標準劃分社團結構如圖2所示。

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

圖2 LFR計算機生成網(wǎng)絡社團劃分標準結構

利用本文提出的算法對LFR計算機生成網(wǎng)絡進行社團檢測，得出社團劃分結果如表2所示。

表2 本文算法的劃分結果

表3 本文算法與文獻[10]算法對比

可見本文算法的社團檢測結果與圖2中的標準社團劃分結果相一致。利用式(3)計算出當前社團檢測結果的模塊度值為0.433，符合模塊度取值范圍，表明本文算法具有良好的準確性。

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

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

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

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

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

3.3 對比實驗

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

利用本文算法與文獻[10]中提出的有向網(wǎng)絡社團檢測算法在3個數(shù)據(jù)集上進行對比實驗。

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

4 結束語

本文基于CNM算法提出了基于相似度的有向網(wǎng)絡社團檢測算法，與文獻[10]提出的有向網(wǎng)絡社團檢測算法相比，不僅能夠處理有向網(wǎng)絡，而且檢測出的社團規(guī)模也更加合理。實驗結果表明，本文提出的算法不僅能夠充分考慮到有向網(wǎng)絡的拓撲結構信息，而且避免了模塊度本身的局限性，使得劃分出的社團規(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)絡的社區(qū)發(fā)現(xiàn)方法[J]. 計算機研究與發(fā)展, 2014, 51(12):2797-2807.

[8] 張海燕, 梁循, 周小平. 針對有向圖的局部擴展的重疊社區(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é)點相似度的有向網(wǎng)絡社團檢測算法[J].微型機與應用，2017,36(3)：19-22.

2016-10-07)

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

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