王天宏 武星 蘭旺森

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

關鍵詞：復雜網絡；社團劃分；節(jié)點親密度；模塊度；人工合成網絡

中圖分類號：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 引言

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

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

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

1 相關定義

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

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

2 本文算法

2.1 算法描述

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

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

2.2 時間復雜度

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

2.3 算法示例

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

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

3 大規(guī)模真實網絡實驗

3.1 實驗設定

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

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

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

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

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

以上所有網絡都轉換為無向無權網絡，各網絡的詳細情況如表5所示。

3.2 實驗結果

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

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

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

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

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

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

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

5 結語

本文提出一個基于局部模塊度改進社團劃分算法，算法首次提出了社團與節(jié)點之間的親密度的概念，以其作為新節(jié)點加入社團的衡量標準，以Clauset模塊度增量作為局部社團終止指標，極大提高了社團劃分的精度與速度。算法還提出以局部度最大節(jié)點作為社團種子節(jié)點，并以可控規(guī)模的LFR數據集網絡實驗分析了局部度最大節(jié)點在局部社團分布規(guī)律，證明其作為種子節(jié)點可行性和有效性。應用本文算法在大規(guī)模實際網絡和人工仿真網絡實驗中，研究表明，本文算法比一些目前具有代表性的算法有更穩(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]李曉佳，張鵬，狄增如，等. 復雜網絡中的社團結構[J]. 復雜系統(tǒng)復雜性科學，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]汪小帆， 劉亞冰. 復雜網絡中的社團結構算法綜述 [J]. 電子科技大學學報， 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]劉旭，易東云.基于局部相似性的復雜網絡社區(qū)發(fā)現方法[J].自動化學報，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]袁超，柴毅. 復雜網絡的局部社團結構挖掘算法[J].自動化學報，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.）