改進的基于局部模塊度的社團劃分算法

王天宏 武星 蘭旺森

摘要：針對大多復(fù)雜網(wǎng)絡(luò)社團劃分算法不能快速發(fā)現(xiàn)最優(yōu)節(jié)點加入社團的問題，提出一種利用節(jié)點親密度的局部社團劃分算法。引入節(jié)點親密度的概念量化社團與鄰居節(jié)點的關(guān)系，按照節(jié)點親密度由大到小選擇節(jié)點加入社團，最后以局部模塊度為指標終止局部社團擴展。在真實網(wǎng)絡(luò)和人工仿真網(wǎng)絡(luò)進行實驗，并與基于信息壓縮的隨機游走算法等4種典型社團劃分算法相比較，所提算法劃分結(jié)果的綜合評價指標（F1score）和標準化互信息（NMI）均好于比較算法。實驗研究表明，所提算法具有較好的時間效率和準確度，適用于大規(guī)模網(wǎng)絡(luò)社團劃分。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；社團劃分；節(jié)點親密度；模塊度；人工合成網(wǎng)絡(luò)

中圖分類號：TP393.02 文獻標志碼：A

Abstract：Focusing on the problem that the best neighbor nodes of the communities can not accurately be found in most local community detection algorithms， an improved local community detection algorithm was proposed based on local modularity. The concept of node intimacy was introduced to quantify the relationship between the community and the neighbor nodes by the algorithm， and the nodes were selected into the communities according to the node intimacy in descending order. In the end，the extension of the local community was terminated by the local modularity index. Compared with the four kinds of typical community detection algorithms such as the random walk algorithm based on information compression， the algorithm was applied in the real networks and the artificial simulation network. The comprehensive evaluation indexs （F1score） and Normalized Mutual Informations （NMI） of the results are better than comparison algorithms. The experiments show that the algorithm has better efficiency and accuracy， and is very suitable for community detection in a large scale network.

Key words：complex network； community detection； node intimacy； modularity； synthetic network

0 引言

許多自然界和人類社會中的復(fù)雜系統(tǒng)可以用網(wǎng)絡(luò)或圖來描述。網(wǎng)絡(luò)的研究關(guān)鍵是要了解網(wǎng)絡(luò)結(jié)構(gòu)和這些復(fù)雜系統(tǒng)的功能。一個常見的復(fù)雜網(wǎng)絡(luò)的特點是社團結(jié)構(gòu)，即社團內(nèi)節(jié)點彼此連接要比社團外的節(jié)點更緊密。社團結(jié)構(gòu)的識別方法在各科學(xué)研究領(lǐng)域備受關(guān)注[1-5]。

大多數(shù)社團檢測方法主要是基于整個網(wǎng)絡(luò)結(jié)構(gòu)，不能用于某些類型的網(wǎng)絡(luò)，如社會網(wǎng)絡(luò)、萬維網(wǎng)，因其規(guī)模較大而且是動態(tài)變化的網(wǎng)絡(luò)，對網(wǎng)絡(luò)結(jié)構(gòu)不能充分了解。于是學(xué)者們提出一些局部社團劃分方法，可通過網(wǎng)絡(luò)的局部知識檢測網(wǎng)絡(luò)社團結(jié)構(gòu)[6-11]。這些算法在發(fā)現(xiàn)精確完整的社團上已經(jīng)取得了很大進步。但是，這些現(xiàn)存方法或多或少都存在一些限制，比如，文獻[6]方法因數(shù)據(jù)存儲方法的局限性，無法應(yīng)用于大規(guī)模網(wǎng)絡(luò)； 文獻[7]方法過于依賴事先定義的參數(shù)，而這些參數(shù)往往難于獲得； 文獻[8]方法凝聚新頂點的條件過于嚴格，完整的社團很難獲得；

文獻[9]方法的效率對于源節(jié)點選擇很敏感，結(jié)果也存在過多的特例。受Clauset算法[7]啟發(fā)，本文提出了一個局部社團劃分新算法，以局部度最大節(jié)點作為開始節(jié)點，以特定順序的搜索潛力頂點，通過計算局部社團模塊度確定最終的社區(qū)結(jié)構(gòu)。本文算法并不同于Clauset算法對每個鄰居節(jié)點計算其局部模塊度，而依據(jù)頂點和社團之間的親密度，以親密度大小排序，選擇最優(yōu)節(jié)點加入社團，此舉提高了算法效率和精度。

1 相關(guān)定義

局部度最大節(jié)點通常有這樣的屬性，如果兩個局部度最大節(jié)點的度不相等，那么它們不相鄰[13]。因此局部度最大節(jié)點往往分散分布在網(wǎng)絡(luò)中。僅當局部度最大節(jié)點度值相同時才相鄰。LFR基準網(wǎng)絡(luò)（LancichinettiFortunatoRadicchi benchmark graph）是當前社團劃分研究中應(yīng)用最為廣泛的數(shù)據(jù)集。本文以LFR基準網(wǎng)絡(luò)實驗驗證了局部度最大節(jié)點比全局度最大節(jié)點更適合作為網(wǎng)絡(luò)社團的初始節(jié)點。LFR基準網(wǎng)絡(luò)主要包括以下參數(shù)：n為網(wǎng)絡(luò)節(jié)點個數(shù)；k是在網(wǎng)絡(luò)中的節(jié)點的平均度；maxk是網(wǎng)絡(luò)中節(jié)點度的最大值；minc表示最小社團所含節(jié)點數(shù)目；maxc 最大社團所含節(jié)點數(shù)目；mu是混合參數(shù)，是節(jié)點與外部社會的節(jié)點連接的概率，mu越大，社團結(jié)構(gòu)越模糊。為便于控制規(guī)模，本文設(shè)定網(wǎng)絡(luò)參數(shù)如表1所示。

如表2所示，度值最大的14個全局度最大節(jié)點的分布并不均衡， 9號社團中分布了4個節(jié)點，而3、5、7、8、10、11、13號社團卻無全局度最大節(jié)點； 反之，局部度最大節(jié)點的分布較為均衡，16個局部度最大節(jié)點均勻分布于12個社團中。進一步講，對未知社團節(jié)點和數(shù)目的網(wǎng)絡(luò)，通常無法確定應(yīng)當選取多少個全局度最大節(jié)點作為種子節(jié)點。故局部度最大節(jié)點更適合作為網(wǎng)絡(luò)社團劃分的種子節(jié)點。

2 本文算法

2.1 算法描述

本文算法第一階段為尋找網(wǎng)絡(luò)局部度最大節(jié)點集合。第二階段選取局部度最大點集中任意節(jié)點作為社團種子節(jié)點，開始社團擴展。首先選種子節(jié)點最大度值鄰居節(jié)點組成初始社團，計算初始社團與鄰居節(jié)點的親密度值；然后選取親密度大于0.5的鄰居節(jié)點加入社團，若無符合此條件節(jié)點，選擇親密度最大節(jié)點，計算其加入社團后局部模塊度的增加值是否為正，若為正則加入，否則判斷下一親密度次大節(jié)點，直至無鄰居節(jié)點可使得模塊度增長，局部社團劃分結(jié)束，重復(fù)此過程，直至完成所有社團劃分。第三階段為社團合并。算法第二階段運行完成后，會產(chǎn)生一些與其他社團高度重疊社團，此時執(zhí)行社團合并。算法首先利用式（6）計算社團之間相似度，若存在兩個社團的相似度Sim（ci，cj）>ε= 0.5，表示較小社團的大部分節(jié)點也存在于較大社團中，算法執(zhí)行社團合并。若該條件未滿足，ci和cj共有節(jié)點為社團重疊節(jié)點。

通過全局模塊度劃分社團結(jié)構(gòu)會存在分辨率限制問題，不僅一些小規(guī)模的社團無法發(fā)現(xiàn)，而且可能錯誤劃分大規(guī)模社團，原因在于全局模塊度定義依賴于網(wǎng)絡(luò)全局屬性，本文算法以網(wǎng)絡(luò)局部指標局部模塊度確定社團結(jié)構(gòu)從而避免了分辨率限制的問題。

2.2 時間復(fù)雜度

假定網(wǎng)絡(luò)中節(jié)點個數(shù)為N，邊為M，網(wǎng)絡(luò)節(jié)點平均度D，T為平均社團規(guī)模，V為平均社團數(shù)量。在算法的第一階段，計算所有局部度最大節(jié)點的時間復(fù)雜度為O（D×N）；在算法第二個階段，從已知的局部度最大節(jié)點中任選一個作為起始節(jié)點發(fā)展社團，尋找社團每個節(jié)點鄰居節(jié)點時間復(fù)雜度為O（T×D），然后通過集合運算的社團的鄰居集合時間復(fù)雜度為O（T×1），計算社團與鄰居節(jié)點親密度并選擇社團最優(yōu)節(jié)點的時間復(fù)雜度為O（V×T×D），計算社團的局部模塊度的時間復(fù)雜度為O（V×T）；在算法第三階段，計算社團之間的相似度并執(zhí)行社團合并，所花費時間復(fù)雜度O（V）。本文算法總的時間復(fù)雜度為O（D×N+T×D+T×1+ V×T×D +V×T+V），因D=2M/N，T=N/V，T

2.3 算法示例

本文以新西蘭海豚網(wǎng)絡(luò)作為算法演示數(shù)據(jù)集，依據(jù)式（1）尋找局部度最大節(jié)點，形成節(jié)點集P，表3第一列所示為新西蘭海豚網(wǎng)絡(luò)的局部度最大節(jié)點。

為分析種子節(jié)點選取順序?qū)τ谒惴ㄐ阅艿挠绊?，我們對算法進行二次測試。不同于上述任意選取種子節(jié)點為起始節(jié)點，以種子節(jié)點度值大小為優(yōu)先選取依據(jù)。海豚網(wǎng)絡(luò)的局部度最大節(jié)點集P中節(jié)點度從小到大為{18，21，58，46，15}，運行本文算法時選取的種子節(jié)點順序為{18，21，58}，算法最終得到與上述任意選取種子為起始節(jié)點相同的劃分結(jié)果，而節(jié)點46和15分別成為以節(jié)點58和21為種子的社團成員，可見本文算法有較好的穩(wěn)定性，種子節(jié)點的選取順序?qū)λ惴ńY(jié)果無影響。

3 大規(guī)模真實網(wǎng)絡(luò)實驗

3.1 實驗設(shè)定

為充分測試算法性能，將本文算法應(yīng)用于斯坦福大學(xué)SNAP（Standford Network Analysis Project）項目中的大規(guī)模社團標準數(shù)據(jù)集。如表5所示，這些大規(guī)模的數(shù)據(jù)集的節(jié)點數(shù)目最多達到三百萬，社團數(shù)表示網(wǎng)絡(luò)的真實社團數(shù)目。數(shù)據(jù)集中一個頂點可以屬于多個社團。

Amazon 該網(wǎng)絡(luò)為亞馬遜產(chǎn)品網(wǎng)絡(luò)，其中頂點表示產(chǎn)品，若兩款產(chǎn)品常被共同購買，它們之間會生成一條邊。亞馬遜提供產(chǎn)品類別定義表示網(wǎng)絡(luò)的真實社團。

DBLP 該網(wǎng)絡(luò)為計算機科學(xué)文獻網(wǎng)絡(luò)，提供了一個全面的計算機科學(xué)的研究論文列表，以此構(gòu)建了一個論文合著關(guān)系網(wǎng)絡(luò)。其中每個頂點表示一位作家，若兩個作者共同寫了一篇論文，則兩個作者有邊相連。作者所發(fā)表論文的期刊或會議表示網(wǎng)絡(luò)的真實社團。

Ploblogs 該網(wǎng)絡(luò)為美國政治博客網(wǎng)絡(luò)。由Adamic和Glance在2005年記錄的一個關(guān)于美國政治的博客網(wǎng)站的超鏈接組成的有向博客網(wǎng)絡(luò)。由博客目錄的說明或自我評價表明個體所屬的真實社團，自由派或保守派。

Orkut 該網(wǎng)絡(luò)為類似Youtube網(wǎng)絡(luò)的社交網(wǎng)絡(luò)，頂點表示社交網(wǎng)絡(luò)用戶，邊表示用戶之間的友誼關(guān)系。用戶創(chuàng)建的群組表示網(wǎng)絡(luò)的真實社團。

以上所有網(wǎng)絡(luò)都轉(zhuǎn)換為無向無權(quán)網(wǎng)絡(luò)，各網(wǎng)絡(luò)的詳細情況如表5所示。

3.2 實驗結(jié)果

圖3和圖4分別為測試的算法的F1Score指標和NMI指標。圖中缺少的列表示該算法在對應(yīng)數(shù)據(jù)集上的運行時間多于7天。因為算法復(fù)雜度之間的主要差別是在數(shù)量級上，單線程和多線程并不影響此點，故所有算法皆被設(shè)置為單線程運行狀態(tài)。

在最大規(guī)模的3個數(shù)據(jù)集Amazon、DBLP和Orkut中，由于Amazon數(shù)據(jù)集擁有較高的社團內(nèi)嵌度，5種算法在Amazon數(shù)據(jù)集社團劃分效果都很好，而其余兩個數(shù)據(jù)集的內(nèi)嵌度都較低，相應(yīng)的，5種算法F1Score指標和NMI指標都略低。

從圖3、4可以看出，雖然存在偏差，F(xiàn)1Score指標和NMI指標總體是相關(guān)的。大體上來看，本文算法在兩種指標衡量中表現(xiàn)最好，除了Orkut以外的3個測試數(shù)據(jù)集中性能最為穩(wěn)定，在最大規(guī)模網(wǎng)絡(luò)Orkut數(shù)據(jù)集中，本文算法運行效果也最為接近表現(xiàn)最好的Oslom算法。

圖5顯示了各種算法的執(zhí)行時間，可以看出本文算法和Bgll算法明顯優(yōu)于其他算法，運行時間上相差至少一個數(shù)量級。由于Bigclam和Infomap算法分析Orkut數(shù)據(jù)集運行時間超過七天，故沒有顯示在圖5中。本文算法和Infomap算法在較小規(guī)模網(wǎng)絡(luò)Polblogs 中的運行時間一樣少至幾秒鐘，而在其余三個網(wǎng)絡(luò)中本文算法為最快，其次為Bgll算法。

圖6和圖7顯示了在兩組LFR數(shù)據(jù)集中運行各種算法的NMI指標。從圖6中看出本文算法在mu<0.2時發(fā)現(xiàn)的社團數(shù)目較多，NMI指標明顯高于其他三種算法。隨著社團重疊節(jié)點數(shù)目增多，當mu>0.3時，本文算法的NMI指標緩慢下降。圖7中LFR仿真網(wǎng)絡(luò)R2規(guī)模為R1的10倍，四種算法在R2中性能表現(xiàn)普遍低于R1中。在兩組仿真網(wǎng)絡(luò)數(shù)據(jù)中Bigclam算法穩(wěn)定性最弱，本文算法在社團結(jié)構(gòu)較為清晰的情況下性能最優(yōu)，社團結(jié)構(gòu)模糊情況下性能略差于Oslom算法。

為比較各種算法的時間效率，本文再次生成了LFR仿真網(wǎng)絡(luò)集R3，包含10個仿真網(wǎng)絡(luò)， 網(wǎng)絡(luò)規(guī)模由小到大（1000～10000），其他參數(shù)相同（k=20， maxk=50， minc=20， maxc=100，mu=0.1）。

圖8所示為5種算法運行于10個LFR仿真網(wǎng)絡(luò)的時間?？梢钥闯?，隨著網(wǎng)絡(luò)規(guī)模的擴大，各算法消耗時間越來越多。Bigclam算法運行效率較低，當節(jié)點數(shù)目達到10000時，運行時間比最好算法運行時間幾乎多出一倍。5種算法在節(jié)點數(shù)目較少時（小于4000）運行時間相差不大，當節(jié)點數(shù)目大于5000時，本文算法和Bgll算法體現(xiàn)出較好的時間效率，直到網(wǎng)絡(luò)規(guī)模達到10000節(jié)點時，運行時間僅僅不到40s。

5 結(jié)語

本文提出一個基于局部模塊度改進社團劃分算法，算法首次提出了社團與節(jié)點之間的親密度的概念，以其作為新節(jié)點加入社團的衡量標準，以Clauset模塊度增量作為局部社團終止指標，極大提高了社團劃分的精度與速度。算法還提出以局部度最大節(jié)點作為社團種子節(jié)點，并以可控規(guī)模的LFR數(shù)據(jù)集網(wǎng)絡(luò)實驗分析了局部度最大節(jié)點在局部社團分布規(guī)律，證明其作為種子節(jié)點可行性和有效性。應(yīng)用本文算法在大規(guī)模實際網(wǎng)絡(luò)和人工仿真網(wǎng)絡(luò)實驗中，研究表明，本文算法比一些目前具有代表性的算法有更穩(wěn)定的性能和更好的時間效率。

參考文獻：

[1]DUCH J， ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical Review E， 2005， 72（2）： 027104.

[2]FORTUNATO S. Community detection in graphs[J]. Physics Reports，2010， 486（3）： 75-174.

[3]李曉佳，張鵬，狄增如，等. 復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)[J]. 復(fù)雜系統(tǒng)復(fù)雜性科學(xué)，2008， 5（3）： 19-42.（LI X J， ZHANG P， DI Z R， et al. Community structure of complex networks[J]. Complex Systems and Complexity Science， 2008， 5（3）： 19-42.）

[4]LANCICHINETTI A， FORTUNATO S， KERTSZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics， 2009， 11（3）： 033015.

[5]汪小帆， 劉亞冰. 復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)算法綜述 [J]. 電子科技大學(xué)學(xué)報， 2009， 38（5）： 537-543.（WANG X F， LI Y B. Overview of algorithms for detecting community structure in complex networks[J]. Journal of University of Electronic Science and Technology of China， 2009， 38（5）： 537-543.）

[6]劉旭，易東云.基于局部相似性的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J].自動化學(xué)報，2011， 37（12）： 1520-1529. （LIU X， YI D Y. Complex network community detection by local similarity[J]. Acta Automatica Sinica， 2011， 37（12）： 1520-1529.）

[7]CLAUSET A. Finding local community structure in networks[J]. Physical Review E， 2005， 72（2）： 026132.

[8]LUO F， WANG J， PROMISLOW E. Exploring local community structures in large networks[J]. Web Intelligence and Agent Systems， 2008， 6（4）： 387-400.

[9]BAGROW J P. Evaluating local community methods in networks[J].Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（5）： P05001.

[10]CHEN M， KUZMIN K， SZYMANSKI B K. Extension of modularity density for overlapping community structure[C]// Proceedings of the 2014 IEEE/ACM International Conference on Social Networks Analysis and Mining. Piscataway， NJ： IEEE， 2014： 856-863.

[11]CHEN Q， FANG M. An efficient algorithm for community detection in complex networks[EB/OL].[2015-10-25].http：//140.123.102.14：8080/reportSys/file/paper/htchiang/htchiang_10_paper.pdf.

[12]REDNER S. How popular is your paper？ An empirical study of the citation distribution[J]. The European Physical Journal B-condensed Matter and Complex Systems， 1998， 4（2）： 131-134.

[13]CHEN Q， WU T T. A method for local community detection by finding maximaldegree nodes[C]// Proceedings of the 2010 International Conference on Machine Learning and Cybernetics. Piscataway， NJ： IEEE， 2010， 1： 8-13.

[14]BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics： Theory and Experiment， 2008， 30（2）： 155-168.

[15]ROSVALL M， BERGSTROM C T. Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems[J]. PloS One， 2011， 6（4）： e18209.

[16]YANG J， LESKOVEC J. Overlapping community detection at scale： a nonnegative matrix factorization approach[C]// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York： ACM， 2013： 587-596.

[17]LANCICHINETTI A， RADICCHI F， RAMASCO J J， et al. Finding statistically significant communities in networks[J]. PloS One， 2011， 6（4）： e18961.

[18]袁超，柴毅. 復(fù)雜網(wǎng)絡(luò)的局部社團結(jié)構(gòu)挖掘算法[J].自動化學(xué)報，2014，40（5）：921-934.（YUAN C， CHAI Y. Method for local community mining in the complex networks[J]. Acta Automatica Sinica， 2014， 40（5）： 921-934.）