基于最少中心節(jié)點覆蓋的社區(qū)發(fā)現(xiàn)方法

夏濤

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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)實世界中許多復(fù)雜系統(tǒng)都可以被直接或轉(zhuǎn)化為復(fù)雜網(wǎng)絡(luò)表示。復(fù)雜網(wǎng)絡(luò)一般存在一些統(tǒng)計特性，如“無標(biāo)度”[1]，“小世界效應(yīng)”[2]，“社區(qū)結(jié)構(gòu)特性”[3]。現(xiàn)在，復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)發(fā)現(xiàn)已經(jīng)成為計算機(jī)科學(xué)、生物學(xué)、物理學(xué)、社會學(xué)等領(lǐng)域研究熱點之一。例如生物學(xué)中蛋白質(zhì)網(wǎng)絡(luò)里同一社區(qū)內(nèi)蛋白質(zhì)往往具有相同功能，社會網(wǎng)絡(luò)中同一社區(qū)范圍內(nèi)的所有個體具有相同行為特征，萬維網(wǎng)網(wǎng)絡(luò)中同一社區(qū)內(nèi)網(wǎng)頁屬于同一主題或同一關(guān)鍵詞相關(guān)等。復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)目的就是探測并展示這些復(fù)雜網(wǎng)絡(luò)中固有的社區(qū)結(jié)構(gòu)。

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

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

4 結(jié)論及展望

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

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

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

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

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

參考文獻(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] 金弟，劉大有，楊博，等.基于局部探測的快速復(fù)雜網(wǎng)絡(luò)聚類算法[J].電子學(xué)報，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] 金弟，楊博，劉杰，等.復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測—基于隨機(jī)游走的蟻群算法[J].軟件學(xué)報，2012， 23（3）：451-464.

[13] 何東曉，周栩，王佐，等.復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘——基于聚類融合的遺傳算法[J].自動化學(xué)報， 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.