夏濤

摘要：復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)目前已成為計算機科學、生物學、社會學等多個領域研究熱點之一。為快速準確地發(fā)現(xiàn)大規(guī)模網(wǎng)絡中社區(qū)結構，該文提出一種基于中心節(jié)點覆蓋的社區(qū)發(fā)現(xiàn)算法。算法以擁有最多鄰居節(jié)點的中心節(jié)點開始，依次找到能覆蓋整個網(wǎng)絡節(jié)點的最少中心節(jié)點，然后以這些中心節(jié)點作為小社區(qū)，計算相交小社區(qū)間合并度量分值，每次合并兩個具有最大合并度量分值的小社區(qū)，并以模塊性Q值作為全局最優(yōu)合并序列評價函數(shù)，全局最大Q的合并序列，即為最優(yōu)社區(qū)劃分結構。實驗結果表明，算法對網(wǎng)絡社區(qū)結構劃分的時間復雜度為nlogn（n為網(wǎng)絡節(jié)點數(shù)目）并具有較高準確率。

關鍵詞：社區(qū)發(fā)現(xiàn)；中心節(jié)點；社區(qū)合并度量

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）04-0019-04

Abstract： Complex network community discovery has become one of the hot issues in many fields， including computer science， biology， sociology， etc. In order to quickly and accurately find the community structure of large-scale network， this paper presents a discovery algorithm based on center node whose neighbors node can cover the whole network . The algorithm starts with the most central node whose neighbor nodes can cover entire network then define them as initial small communities， then calculate the combining measure scores between these cross communities pair， each time we will merge a pair of cross communities which get the most combining measure score， and modularity Q value as a global optimal evaluation function for the merge sequence， one merge sequence which achieve maximum Q is the optimal community structure partition of the network. As described， the algorithm can even divided into a dense network into communities with approximately linear time complexity .Applying the algorithm on several typical community social networks shows that the algorithm is of great accuracy and low time complexity.

Key words： community detect； core nodes； community combining measure

1 概述

現(xiàn)實世界中許多復雜系統(tǒng)都可以被直接或轉化為復雜網(wǎng)絡表示。復雜網(wǎng)絡一般存在一些統(tǒng)計特性，如“無標度”[1]，“小世界效應”[2]，“社區(qū)結構特性”[3]。現(xiàn)在，復雜網(wǎng)絡中社區(qū)結構發(fā)現(xiàn)已經(jīng)成為計算機科學、生物學、物理學、社會學等領域研究熱點之一。例如生物學中蛋白質網(wǎng)絡里同一社區(qū)內蛋白質往往具有相同功能，社會網(wǎng)絡中同一社區(qū)范圍內的所有個體具有相同行為特征，萬維網(wǎng)網(wǎng)絡中同一社區(qū)內網(wǎng)頁屬于同一主題或同一關鍵詞相關等。復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)目的就是探測并展示這些復雜網(wǎng)絡中固有的社區(qū)結構。

自復雜網(wǎng)絡中社區(qū)發(fā)現(xiàn)問題提出至今，各領域學者專家已經(jīng)提出多種發(fā)現(xiàn)算法。2004年Girvan和Newman提出了一個用于刻畫網(wǎng)絡社區(qū)結構優(yōu)劣的量化標準模塊性函數(shù)Q[4]，并啟發(fā)其他學者提出基于模塊性函數(shù)Q的一系列新算法[5-8]，但是該系列算法過程復雜，時間復雜度也較高；2007年Raghavan U N等針對大規(guī)模社交網(wǎng)絡提出了標簽傳播算法（LPA）[9]，該算法可以在5步之內使得95%以上節(jié)點標簽達到穩(wěn)定狀態(tài)并且適用于超大規(guī)模網(wǎng)絡，后續(xù)有Leung[10]，Barber[11]，liu[12]等對標簽傳播進行一系列優(yōu)化和擴展，但LPA算法的弱點是容易陷入局部最優(yōu)解同時最終結果對節(jié)點更新順序敏感，算法的準確率有待提升；而國內近年的研究如劉大有[13]，何東曉[14]等主要集中在運用蟻群算法和遺傳算法結合馬爾科夫隨機游走或模塊性函數(shù)Q來產(chǎn)生網(wǎng)絡社區(qū)結構劃分。

本文提出一種基于中心節(jié)點覆蓋的社區(qū)發(fā)現(xiàn)算法。算法以擁有最多鄰居節(jié)點的中心節(jié)點開始，依次找到能覆蓋整個網(wǎng)絡節(jié)點的最少中心節(jié)點，然后以這些中心節(jié)點作為小社區(qū)，計算相交小社區(qū)間合并度量分值，每次合并兩個具有最大合并度量分值的小社區(qū)，并以模塊性Q值作為全局最優(yōu)合并序序列評價函數(shù)，全局最大Q的合并序列即為最優(yōu)社區(qū)劃分結構。

4 結論及展望

本算法思路簡潔，不同于Vincent D Blondel等[16]提出了以多步驟計算Q值作為起始和最終劃分憑據(jù)方法，提出基于擁有最多鄰居節(jié)點的初始中心方法，創(chuàng)新性地定義了社區(qū)合并置信度度量方法，最后以模塊性函數(shù)均值Q作為優(yōu)化函數(shù)獲取最優(yōu)劃分結果。不僅在小規(guī)模網(wǎng)絡中劃分準確，而且由于算法時間復雜度低可以適用于大規(guī)模網(wǎng)絡數(shù)據(jù)。

1） 在小規(guī)模網(wǎng)絡中劃分結果準確。如在空手道網(wǎng)絡中的社區(qū)結構劃分完全正確，在海豚網(wǎng)絡社區(qū)結構劃分只誤劃分了兩個節(jié)點。

2） 在大規(guī)模網(wǎng)絡中應用。算法最耗時間步驟僅僅在于起始時按照節(jié)點鄰居數(shù)量排序，且時間復雜度為O（nlogn），其他步驟均為線性時間復雜度，第二步直接大幅度縮減了計算量。這使得算法具有應用在大規(guī)模網(wǎng)絡中的可行性。

3） 存在的問題。本算法在兩個小數(shù)據(jù)集空手道數(shù)據(jù)和海豚網(wǎng)絡數(shù)據(jù)集中并沒有以取模塊性函數(shù)Q，而是取其均值作為目標優(yōu)化函數(shù)，得到較為準確地劃分結果，與目前大部分論文不同。而在大網(wǎng)絡數(shù)據(jù)集如科學家協(xié)作網(wǎng)絡中直接以模塊性函數(shù)Q作為評價函數(shù)，此時我們發(fā)現(xiàn)網(wǎng)絡中社區(qū)數(shù)量較大時，模塊性函數(shù)Q≈1，這也即模塊性函數(shù)Q的分辨率極限問題[17]。

4） 展望。從算法流程可以看出，算法第三步小社區(qū)之間存在交集，本算法在處理時需要對交叉節(jié)點進行二次劃分，這在一定程度上增加了算法的時間消耗，同時也給其創(chuàng)造了另外一種可能，也即劃分重疊社區(qū)的可能。今后將繼續(xù)改進算法并根據(jù)網(wǎng)絡規(guī)模確定劃分網(wǎng)絡社區(qū)結構的時使用平均模塊性函數(shù)Q與直接模塊性函數(shù)Q，同時嘗試將改進算法使其能夠運用在重疊社區(qū)發(fā)現(xiàn)研究中。

參考文獻：

[1] Barabási A-L，Albert R.Emergence of scaling in random networks[J].Science，1999， 286（5439）： 509-512.

[2] Watts D J，Strogatz S H.Collective dynamics of small-world networks[J]. Nature， 1998， 393（6638）： 440-442.

[3] Girvan M，Newman M E J.Community structure in social and biological networks[J]. Proceedings of National Academy ofScience，2002，9（12）：7821-7826.

[4] Newman M E J，Girvan M.Finding and evaluating community structure in networks[J]. Physical Review E，2004，69（2）： 026113.

[5] Newman M E J. Fast algorithm for detecting community structure in networks[J].Physical Review E， 2004， 69（6）： 066133.

[6] Guimera R，Amaral L A N.Functional cartography of complex metabolic networks[J].Nature， 2005， 433（7028）： 895-900.

[7] Newman M E J. Modularity and community structure in networks[J]. Proceedings of National Academy of Science， 2006，103（23）： 8577-8582.

[8] 金弟，劉大有，楊博，等.基于局部探測的快速復雜網(wǎng)絡聚類算法[J].電子學報，2011， 39（11）：2540-2546.

[9] Raghavan U N，Albert R，Kumara S.Near linear-time algorithm to detect community structures in large-scale networks[J].Physical Review E， 2007，76（3）： 036106.

[10] Leung I X Y，Hui P，Li`o P，et al.Towards real time community detection in large networks[J].Physical Review E，2009，79（6）：066107.

[11] Barber M J， Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E， 2009，80（2）：026129.

[12] 金弟，楊博，劉杰，等.復雜網(wǎng)絡簇結構探測—基于隨機游走的蟻群算法[J].軟件學報，2012， 23（3）：451-464.

[13] 何東曉，周栩，王佐，等.復雜網(wǎng)絡社區(qū)挖掘——基于聚類融合的遺傳算法[J].自動化學報， 2010，36（8）： 1160-1170.

[14] Zachary W W.An information flow model for conflict andfission in small groups[J].Journal of Anthropological Research， 1977， 33（4）：452-473.

[15] Lusseau D.The emergent properties of a dolphin social network. Proceedings of the Royal Society B： Biological Sciences， 2003，270（Supplement 2）： S186?S188.

[16] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks[J]. Journal of StatisticalMechanics：Theory and Experiment，2008.

[17] Fortunato S， Barthélemy M. Resolution limit in community detection[J]. Proceedings of National Academy of Science， 2007，104（1）：36-41.