基于節點相似度的有向網絡社團檢測算法

王 林,張一帆

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

基于節點相似度的有向網絡社團檢測算法

王 林,張一帆

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

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

社團檢測；有向網絡；CNM算法；節點相似度

0 引言

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

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

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

1 相關理論與算法

1.1 SimRank算法

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

(1)

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

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

(2)

1.2 CNM算法

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

1.3 有向網絡模塊度

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

(3)

2 基于相似度的有向網絡社團檢測算法

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

重新定義變量eij和ai為：

(4)

(5)

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

(6)

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

算法步驟如下：

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

輸出：社團的劃分結果。

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

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

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

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

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

3 實驗結果與分析

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

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

表1 LFR計算機生成網絡主要參數

3.1 計算機生成網絡上的實驗結果

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

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

圖1 LFR計算機生成的有向初始網絡

圖2 LFR計算機生成網絡社團劃分標準結構

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

表2 本文算法的劃分結果

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

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

3.2 算法中參數的選取

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

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

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

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

3.3 對比實驗

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

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

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

4 結束語

本文基于CNM算法提出了基于相似度的有向網絡社團檢測算法，與文獻[10]提出的有向網絡社團檢測算法相比，不僅能夠處理有向網絡，而且檢測出的社團規模也更加合理。實驗結果表明，本文提出的算法不僅能夠充分考慮到有向網絡的拓撲結構信息，而且避免了模塊度本身的局限性，使得劃分出的社團規模更加均勻。

[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] 孫怡帆, 李賽. 基于相似度的微博社交網絡的社區發現方法[J]. 計算機研究與發展, 2014, 51(12):2797-2807.

[8] 張海燕, 梁循, 周小平. 針對有向圖的局部擴展的重疊社區發現算法[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

王林,張一帆.基于節點相似度的有向網絡社團檢測算法[J].微型機與應用，2017,36(3)：19-22.

2016-10-07)

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

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