面向大規(guī)模應(yīng)用層拓撲的社團發(fā)現(xiàn)技術(shù)

收稿日期：2013-05-09

基金項目：國家重點基礎(chǔ)研究發(fā)展計劃（973）（2011CB302605）；國家高技術(shù)研究發(fā)展計劃（863）（2011AA010705，2012AA012506）；

國家自然科學(xué)基金（61173145，61202457）。

作者簡介：黃振（1989-），男，江西撫州人，碩士研究生，主要研究方向：復(fù)雜網(wǎng)絡(luò)、DNS行為分析；

張宇（1979-），男，河北樂亭人，博士，講師，主要研究方向：網(wǎng)絡(luò)拓撲、BGP、復(fù)雜網(wǎng)絡(luò)等；

張宏莉（1973-），女，吉林榆樹人，博士，教授，博士生導(dǎo)師，主要研究方向：網(wǎng)絡(luò)與信息安全、網(wǎng)絡(luò)測量、并行計算等。

面向大規(guī)模應(yīng)用層拓撲的社團發(fā)現(xiàn)技術(shù)

黃振， 張宇， 張宏莉（哈爾濱工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001）摘要：社團發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域里一個極具挑戰(zhàn)性的方向。特別地，對于現(xiàn)實世界中許多規(guī)模巨大的應(yīng)用層拓撲，一些社團發(fā)現(xiàn)算法因為計算復(fù)雜度過高而不適用。另一些社團發(fā)現(xiàn)算法的實際性能還有待評估。為此，提出了可用于衡量社團發(fā)現(xiàn)算法實際應(yīng)用價值的三個指標：（1）可擴展性，衡量算法能處理的應(yīng)用層拓撲的規(guī)模；（2）準確度，衡量社團劃分結(jié)果好壞；（3）敏感度，衡量社團劃分結(jié)果的一致程度。在7個大規(guī)模的現(xiàn)實世界應(yīng)用層拓撲圖上，對三個針對大規(guī)模網(wǎng)絡(luò)的社團發(fā)現(xiàn)算法（CNM算法、Wakita算法和Louvain算法）進行了比較分析。實驗結(jié)果表明，Louvain算法在可擴展性上最優(yōu)且所得劃分結(jié)果準確度最高，CNM算法在敏感度上表現(xiàn)最好。

關(guān)鍵詞：社團結(jié)構(gòu)； 社團發(fā)現(xiàn)； 社交網(wǎng)絡(luò)； 復(fù)雜網(wǎng)絡(luò)； 大規(guī)模網(wǎng)絡(luò)

中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2013）04-0034-05

Community Detection for Large-scale Application-layer Topologies

HUANG Zhen，ZHANG Yu，ZHANG Hongli

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）

Abstract：Community detection is a very challenging research direction in the field of complex networks’ research. In particular， as the large scale of real world’s application layer topology， some community detection algorithms are not applicable because of high computational complexity. And some algorithms’ actual performance remains to be evaluated. Therefore， the paper proposes three indicators that can be used to measure community detection algorithms’ actual application value： （1） extensibility， used to measure the scale of application layer topology that can be dealt with； （2） accuracy， used to measure the partition result is good or bad； （3） sensitivity， used to measure the partition result’s consistent. The paper uses seven large-scale application layer topologies to analyze three community detection algorithms for large-scale network， i.e. CNM algorithm， Wakita algorithm and Louvain algorithm. The results show that Louvain algorithm performs best on scalability and accuracy， and CNM algorithm’s performance on sensitivity is best.

Key words：Community Structure； Community Detection； Social Networks； Complex Networks； Massive Networks

0引言

隨著復(fù)雜網(wǎng)絡(luò)研究的深入進行，人們發(fā)現(xiàn)現(xiàn)實世界網(wǎng)絡(luò)中普遍存在社團結(jié)構(gòu)。社團結(jié)構(gòu)是指網(wǎng)絡(luò)可根據(jù)其自身的拓撲結(jié)構(gòu)被劃分為若干個社團；同一社團內(nèi)的節(jié)點連接緊密，而不同社團間的節(jié)點連接稀疏。網(wǎng)絡(luò)的社團結(jié)構(gòu)有助于人們分析復(fù)雜網(wǎng)絡(luò)的拓撲性質(zhì)和結(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)中各組成模塊的功能、揭示復(fù)雜網(wǎng)絡(luò)中隱藏的規(guī)律和預(yù)測復(fù)雜網(wǎng)絡(luò)的行為等。目前，社團發(fā)現(xiàn)技術(shù)已經(jīng)被廣泛應(yīng)用到網(wǎng)絡(luò)輿情分析控制等領(lǐng)域。

社團發(fā)現(xiàn)的歷史最早可以追溯到圖劃分。傳統(tǒng)社團發(fā)現(xiàn)方法包括圖劃分方法中的Kernighan-Lin算法和譜平分算法，以及社會學(xué)方法中的層級聚類方法和K-Means聚類方法。近幾年，又提出了一些新的社團發(fā)現(xiàn)算法，比如GN算法[1]、CNM算法[2]、Wakita算法[3]、Louvain算法[4]、模擬退火算法[5]、譜劃分方法[6]、派系過濾算法[7]等。

現(xiàn)實世界網(wǎng)絡(luò)的巨大規(guī)模對社團發(fā)現(xiàn)技術(shù)形成了嚴峻挑戰(zhàn)。在已提出的社團發(fā)現(xiàn)算法中，絕大部分算法都只能處理幾千個節(jié)點的網(wǎng)絡(luò)，而現(xiàn)實世界網(wǎng)絡(luò)的規(guī)模大多在百萬個節(jié)點以上。這就使得絕大部分社團發(fā)現(xiàn)算法在分析現(xiàn)實世界網(wǎng)絡(luò)方面失去了實際應(yīng)用價值。Kwak等人[8]已經(jīng)就社團發(fā)現(xiàn)算法的比較開展了一定的研究。為了更為有效地篩選得到具有實際應(yīng)用價值的社團發(fā)現(xiàn)算法，在其工作基礎(chǔ)上，本文提出了三個指標來衡量社團發(fā)現(xiàn)算法。這三個指標分別是：可擴展性、準確度和敏感度。基于這三個指標，文中使用三個社團發(fā)現(xiàn)算法——CNM算法、Wakita算法、Louvain算法——進行了一系列對比實驗。通過對實驗結(jié)果的分析，能夠充分理解為什么這三個指標可以體現(xiàn)該算法的實際應(yīng)用價值，從而為算法的選擇以及算法設(shè)計提供有益的指導(dǎo)。

1衡量指標

1.1可擴展性

可擴展性用以定性評估社團發(fā)現(xiàn)算法所能處理的網(wǎng)絡(luò)規(guī)模大小。隨著需要分析處理的網(wǎng)絡(luò)規(guī)模逐漸增大，社團發(fā)現(xiàn)算法所消耗的時間也將逐漸增長。因此，可擴展性也可定性地描述為算法所消耗時間隨數(shù)據(jù)規(guī)模增大而增長的趨勢。可在規(guī)模依次增大的多個現(xiàn)實世界網(wǎng)絡(luò)數(shù)據(jù)集上運行同一個社團發(fā)現(xiàn)算法，計算得出社團發(fā)現(xiàn)算法處理每個數(shù)據(jù)集所消耗的時間。這樣，便可以觀察到社團發(fā)現(xiàn)算法所消耗時間的增長趨勢，也就是該社團發(fā)現(xiàn)算法的可擴展性。增長趨勢越明顯，算法的可擴展性越差，算法所能處理的網(wǎng)絡(luò)規(guī)模越小。

在篩選具有實際應(yīng)用價值的社團發(fā)現(xiàn)算法的過程中，可擴展性是需要考慮的首個因素。只有具備足夠高強的可擴展性，算法才能真正適用于一些規(guī)模巨大的網(wǎng)絡(luò)分析。

1.2準確度

準確度用于衡量社團發(fā)現(xiàn)算法所得出的社團劃分結(jié)果的質(zhì)量。盡管存在很多方法來衡量社團劃分結(jié)果質(zhì)量，但是Newman和Girvan提出的模塊性[1]已經(jīng)成為事實上的標準。因此，文中將準確度定義為社團劃分結(jié)果的模塊性值。模塊性值越大，社團劃分結(jié)果越好，社團發(fā)現(xiàn)算法的準確度越高。

模塊性的提出基于以下觀點：隨機圖中不存在社團結(jié)構(gòu)。因此，通過對比結(jié)果子圖的實際邊密度和空模型的期望邊密度，就能確定圖中是否存在社團結(jié)構(gòu)。空模型是原始圖的一個副本。除了不包含社團結(jié)構(gòu)外，空模型和原始圖的結(jié)構(gòu)屬性要基本相同。文中選擇的空模型要求模型中每個節(jié)點的度和原始圖中該節(jié)點的度均要保持一致。模塊性的計算公式是：

Q=12m∑ijAij-kikj2mδ（Ci，Cj）（1）第4期黃振，等：面向大規(guī)模應(yīng)用層拓撲的社團發(fā)現(xiàn)技術(shù)智能計算機與應(yīng)用第3卷

A是圖的鄰接矩陣，m是圖的邊數(shù)，ki為節(jié)點i的度，Ci是社團劃分結(jié)果中節(jié)點i所屬的社團編號。當(dāng)節(jié)點i和j被劃分到同一個社團中，即Ci=Cj時，δ（Ci，Cj）的值為1，否則為0。只要遍歷圖的所有節(jié)點對，就能計算得到社團劃分結(jié)果的模塊性Q值。

1.3敏感度

已經(jīng)證明，社團發(fā)現(xiàn)是NP完全問題。因此，絕大部分社團發(fā)現(xiàn)算法都是啟發(fā)式近似算法。這就導(dǎo)致社團發(fā)現(xiàn)算法將存在結(jié)果不一致的問題。也就是說，當(dāng)同一個圖的節(jié)點輸入順序發(fā)生改變時，社團發(fā)現(xiàn)算法將在該圖上得到不同的劃分結(jié)果。Kwak等人[8]的研究也得出了相同的結(jié)論。當(dāng)這種不一致性較為明顯時，社團發(fā)現(xiàn)算法所得出的劃分結(jié)果將失去參考意義。為了衡量社團發(fā)現(xiàn)算法所得劃分結(jié)果的不一致程度，文中提出了敏感度這個指標。

敏感度可通過計算所有劃分結(jié)果的節(jié)點成對概率進行衡定。節(jié)點成對概率由Kwak等人[8]提出。通過改變節(jié)點的輸入順序，并在同一個圖上多次運行某一社團發(fā)現(xiàn)算法。由于社團發(fā)現(xiàn)算法的結(jié)果會出現(xiàn)不一致，就會得到這個圖的多個劃分結(jié)果。節(jié)點成對概率定義為在這多次劃分結(jié)果中，節(jié)點i和節(jié)點j劃分入同一個社團的概率。節(jié)點成對概率pij計算公式為：

pij=∑Nn=1δn（Ci，Cj）/N（2）

式中，N為在同一個圖上運行相同算法的次數(shù)；Ci和Cj分別為節(jié)點i和節(jié)點j所屬社團編號。從公式（2）中，可以知道節(jié)點成對概率pij的取值在0到1之間。若pij為0，則表示在多個劃分結(jié)果中，節(jié)點i和節(jié)點j一次都未被劃分入同一個社團中；若pij為1，則表示節(jié)點i和節(jié)點j每次都被劃分進同一個社團中。

2實驗條件和數(shù)據(jù)

采用三個快速社團發(fā)現(xiàn)算法來進行一系列對比實驗。這三個算法分別是：CNM算法[2]、Wakita算法[3]和Louvain算法[4]。三個算法的原理都是通過最大化模塊性Q的值來得到盡可能好的社團劃分結(jié)果。表1是進行對比實驗的軟硬件環(huán)境配置。

表1實驗環(huán)境

Tab.1 Experimental environment操作系統(tǒng)Red Hat Enterprise Linux Server release 5.2

（Tikanga）CPUIntel（R） Xeon（R） CPU E5405 @ 2.00GHz （共8個）CPU緩存6 MB內(nèi)存容量4 GB硬盤容量540 GB磁盤緩存大小3 GB

在這一系列對比實驗中，使用了7個現(xiàn)實世界網(wǎng)絡(luò)的數(shù)據(jù)。這些數(shù)據(jù)分別是：Karate[9]、C.Elegans[9]、Protein[10]、AS[11]、Facebook[10]、WWW[10]和Youtube[10]。而其詳細統(tǒng)計信息如表2所示。

表2實驗數(shù)據(jù)統(tǒng)計信息

Tab.2 Statistics of the experimental data統(tǒng)計信息實驗數(shù)據(jù)KarateC.ElegansProteinASFacebookWWWYoutube節(jié)點數(shù)342971 84632 93063 730325 7291 138 499邊數(shù)782 1482 203124 133817 0901 090 1082 990 443平均節(jié)點度4.614.52.47.525.76.75.3平均聚類系數(shù)0.570.290.0710.380.220.230.09

3實驗結(jié)果分析

下面將依次給出可擴展性、準確度和敏感度這三個指標所對應(yīng)的實驗結(jié)果，并根據(jù)這些實驗結(jié)果詳細說明這三個指標的實際應(yīng)用意義。

3.1可擴展性結(jié)果

可擴展性實驗中，分別使用三個快速算法處理Karate等7個數(shù)據(jù)，并在處理每個數(shù)據(jù)時，記錄各算法的運行時間。實驗結(jié)果如表3所示。

結(jié)合表2中的實驗數(shù)據(jù)統(tǒng)計信息，可以從表3中觀察分析，并得到以下結(jié)論：

（1）對于節(jié)點數(shù)小于5 000的網(wǎng)絡(luò)，三個算法基本不消耗任何運行時間；

表3可擴展性實驗結(jié)果

Tab.3 Results of scalability時間（s）

算法實驗數(shù)據(jù)KarateC.ElegansProteinASFacebookWWWYoutubeCNM000821 1742 5277 345 626Wakita00012625213 370Louvain000121742

（2）當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)超過5 000時，CNM算法效率開始下降；

（3）當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)超過100萬時，CNM算法效率下降嚴重；

（4）當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)超過100萬，邊數(shù)超過1 000萬時，Wakita算法消耗的時間明顯增加，Wakita算法的效率也開始明顯下降。

綜上所述，從算法運行時間的增長趨勢中，可以知道，Louvain算法可擴展性最高，其次是Wakita算法，最后是CNM算法。

3.2準確度結(jié)果

準確度對比實驗的過程分為以下3步：

（1）準備測試數(shù)據(jù)。對7個實驗數(shù)據(jù)中的每一個，重新對數(shù)據(jù)中的節(jié)點進行隨機編號，以達到打亂節(jié)點輸入順序的目的。每個數(shù)據(jù)都進行100次同樣的操作。因此，每個數(shù)據(jù)都能夠得到數(shù)據(jù)相同但節(jié)點輸入順序不同的100組數(shù)據(jù)。本文將這100組數(shù)據(jù)稱為一個數(shù)據(jù)集合。

（2）運行算法程序。在每一個數(shù)據(jù)集合上，分別運行三個算法，記錄每個算法在各個數(shù)據(jù)集合上得出的模塊性Q的值。

（3）處理測試結(jié)果。計算每個算法在各個數(shù)據(jù)集合上得到的模塊性Q的平均值和方差。

準確度實驗結(jié)果如表4所示。表4中，未能在合理時間內(nèi)得出社團劃分結(jié)果的用“——”表示。

表4準確度實驗結(jié)果

Tab.4 Results of accurancyQ平均值

算法實驗數(shù)據(jù)KarateC.ElegansProteinASFacebookWWWYoutubeCNM0.380 70.371 10.844 30.548 9——————Wakita0.412 30.308 20.830 80.517 50.373 70.895 2——Louvain0.415 20.391 40.843 20.586 80.633 10.935 70.719 7

從表4中，可以知道：Louvain算法得到的模塊性Q的平均值大于CNM算法和Wakita算法。這表明Louvain算法所得社團劃分結(jié)果的準確度要高于其它兩個算法；另外CNM算法的準確度則要高于Wakita算法。

3.3敏感度結(jié)果

根據(jù)準確度實驗所得的社團劃分結(jié)果來計算節(jié)點成對概率pij。節(jié)點成對概率的計算結(jié)果使用累積分布函數(shù)（CDF）圖展示。圖1為Karate數(shù)據(jù)和C.Elegans數(shù)據(jù)上計算得到的節(jié)點成對概率的累積分布函數(shù)圖。

從圖1中可以知道：在Karate數(shù)據(jù)上，CNM算法所得劃分結(jié)果的pij只有0和1這兩個值；這是最理想的結(jié)果，即劃分結(jié)果完全一致，不受節(jié)點輸入順序的影響；在C.Elegans數(shù)據(jù)上，CNM算法所得劃分結(jié)果的pij也大部分為0或1；Wakita算法的表現(xiàn)雖然比Louvain算法好，但相對CNM算法來說則要差上很多；因此，從節(jié)點成對概率角度進行判斷，對Karate數(shù)據(jù)和C.Elegans數(shù)據(jù)來說，敏感度由高到低依次是Louvain算法、Wakita算法、CNM算法。

圖2為三個算法在Protein數(shù)據(jù)和AS數(shù)據(jù)上得出的節(jié)點成對概率的CDF圖。

在Protein數(shù)據(jù)上，三個算法得出的結(jié)果曲線非常接近。其中，CNM算法的結(jié)果曲線與X軸基本平行， Louvain算法的結(jié)果曲線則略優(yōu)于Wakita算法的結(jié)果曲線。三個算法所得結(jié)果的節(jié)點成對概率絕大部分都為1，表明對于Protein數(shù)據(jù)而言，三個算法的敏感度都比較低。在AS數(shù)據(jù)上，CNM算法依然是表現(xiàn)最好的，敏感度最低。Louvain算法的結(jié)果曲線比較接近CNM算法的結(jié)果曲線。Wakita算法的結(jié)果曲線的傾斜度明顯高于CNM算法和Louvain算法。因此，在AS數(shù)據(jù)上，CNM算法的敏感度最低，Wakita算法的敏感度最高。

圖3為三個算法在Facebook數(shù)據(jù)、WWW數(shù)據(jù)的劃分結(jié)果上取得的節(jié)點成對概率的CDF圖。因為CNM算法的可擴展性較差，導(dǎo)致其在合理的時間內(nèi)無法處理完成Facebook數(shù)據(jù)和WWW數(shù)據(jù)而得到社團劃分結(jié)果，所以圖3中只有Wakita算法和Louvain算法的結(jié)果曲線。

從圖3中可以看到，在Facebook數(shù)據(jù)上，Wakita算法的結(jié)果曲線的傾斜度明顯高于Louvain算法的結(jié)果曲線，表明Louvain算法對于Facebook數(shù)據(jù)的敏感度要低于Wakita算法。但是，這兩個算法的結(jié)果曲線與X軸有的傾斜度都比較大，表明這兩個算法在Facebook數(shù)據(jù)上的敏感度都不是很理想。在WWW數(shù)據(jù)上，兩個算法的結(jié)果曲線很接近，且兩條結(jié)果曲線都接近于與X軸平行。總體來說，Louvain算法的結(jié)果曲線稍微優(yōu)于Wakita算法。因此，在WWW數(shù)據(jù)上，Louvain算法的敏感度低于Wakita算法。

由于只有Louvain算法能夠在合理的時間內(nèi)處理完成Youtube數(shù)據(jù)，因此，無法在這個數(shù)據(jù)上比較三個算法的敏感度。

綜上所述，在這6個數(shù)據(jù)上，CNM算法在敏感度方面的表現(xiàn)最好，其得到的社團劃分結(jié)果比較一致，不容易受節(jié)點輸入順序的影響。同時，Wakita算法和Louvain算法的敏感度大小則取決于所處理的圖。對于某些圖而言，Wakita算法的敏感度相對較低，而對于另外一些圖，Louvain算法的敏感度較低。

4結(jié)束語

針對大多數(shù)社團發(fā)現(xiàn)算法并不具備實際應(yīng)用價值的情況，文中提出了三個用于篩選社團發(fā)現(xiàn)算法的指標：可擴展性、準確度和敏感度。可擴展性旨在衡量社團發(fā)現(xiàn)算法能夠處理的網(wǎng)絡(luò)規(guī)模；準確度體現(xiàn)社團發(fā)現(xiàn)算法所得社團劃分結(jié)果的好壞；敏感度則用來判斷社團發(fā)現(xiàn)算法所得劃分結(jié)果的一致程度。通過這三個指標的結(jié)合利用，就可以從眾多已提出的社團發(fā)現(xiàn)算法中選出能適合于實際應(yīng)用的社團發(fā)現(xiàn)算法。

為了查看這三個指標的實際表現(xiàn)情況，使用三種快速社團發(fā)現(xiàn)算法——CNM算法、Wakita算法和Louvain算法——進行了一系列的對比實驗。實驗結(jié)果表明，Louvain算法的可擴展性和準確度相對來說最高，CNM算法的敏感度最低。該結(jié)論可用于指導(dǎo)在實際應(yīng)用中如何選擇三種社團發(fā)現(xiàn)算法。比如，若要處理規(guī)模巨大的圖，則可使用可擴展性高的Louvain算法；若對結(jié)果的穩(wěn)定性要求較高，則可使用CNM算法。

從敏感度實驗結(jié)果中，可以看到對于大部分數(shù)據(jù)而言，社團發(fā)現(xiàn)算法的敏感度都不太理想。這就使得重復(fù)使用某一社團發(fā)現(xiàn)算法處理同一個圖所得到的社團劃分結(jié)果沒有太大的參考意義。因此，如何降低社團發(fā)現(xiàn)算法的敏感度，使得社團發(fā)現(xiàn)算法得到的結(jié)果能夠盡量一致將是下一步研究工作的重點。

參考文獻：

[1]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[C]// Proceedings of the National Academy of Science of the USA， 2002， 99（12）：7821–7826.

[2]CLAUSET A， NEWMAN M E J， MOORE C. Finding community structure in very large networks[J]. Phys. Rev. E.， 2004， 70：066-111.

[3]WAKITA K，TSURUMI T. Finding community structure in mega-scale social networks[C]//CoRR， abs/cs/0702048， 2007.

[4]BLONDEL V D， et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics： Theory and Experiment， 2008， 10（10008）：12.

[5]GUIMERA` R， SALES-PARDO M， LAN A. Modularity from fluctuations in random graphs and complex networks[R]. Physical Review E. 2004， 70：25-101.

[6]D L， MUNOZ M A . Detecting network communities： a new systematic and efficient algorithm[J]. Journal of Statistical Mechanics： Theory and Experiment， 2004，10（1）：1-12.

[7]PALL G， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005， 435（7043）：814–818.

[8]KWAK H， CHOI Y， EOM Y， et al. Mining communities in networks： a solution for consistency and its evaluation[C]//Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference， November 04-06， 2009.

[9]http：//www-personal.umich.edu/～mejn/.

[10]http：//socialnetworks.mpi-sws.org.

[11]OLIVEIRA R， et al. Observing the evolution of Internet AS topology[J]. SIGCOMM ’07， 2007 ，21（2）：313-324.