基于相似度的社團劃分算法

吳蔚蔚，劉功申，黃 晨

（上海交通大學信息內容分析技術國家工程實驗室，上海，200240）

基于相似度的社團劃分算法

吳蔚蔚，劉功申，黃 晨

（上海交通大學信息內容分析技術國家工程實驗室，上海，200240）

為對復雜網絡進行合理劃分，找出真實存在的社團結構，提出一種基于局部模塊度和相似度的社團劃分算法。計算網絡中相連節點之間的相似度，快速聚合關聯性最高的節點，從而實現社團的初步劃分。以局部模塊度為閾值，根據社團相似度聚合社團，得到具有最佳模塊度的結果，避免模塊度缺陷，提高算法準確度。算法進行社團劃分時只需要網絡局部信息，降低了時間復雜度。在實際網絡和計算機仿真網絡實驗中的應用結果表明，與NS1，CNM，LAP等算法相比，該算法具有較低的計算復雜度和較高的準確率。

節點；相似度；社團；復雜網絡；模塊度

1 概述

復雜網絡作為生物系統、社會系統、網絡、萬維網等一系列復雜系統的抽象代表，近年來已經吸引來了來自眾多領域學者的研究［1-2］。復雜網絡中的社團結構預示著網絡中的節點聚合的趨勢，同一社團列的節點之間的聯系會越發緊密，而社團與社團之間的節點聯系會越發稀疏，所以，社團結構是復雜網絡的一個非常重要的屬性。對復雜網絡進行社團劃分同時也具有顯著的應用意義，如收集具有相同話題的網頁、發現代謝網絡周期的功能單元等，此外，最近有很多研究結果顯示，社團的屬性與整體網絡的屬性有很大不同，忽略對社團結構的研究很可能會錯失很多有意義的屬性。

劃分社團結構的優秀算法都需要滿足以下兩點要求：較高的社團劃分準確度和較低的計算復雜度。在過去幾年中，學者們就如何在復雜網絡中劃分社團提出了許多算法，但是大多都很難同時達到以上兩點。

在目前已知的眾多算法中，主要有2類聚類算法，一類是劃分算法，另一類是層聚類算法。基于拉普拉斯矩陣譜圖的特征向量的譜平分算法，和基于盡量增大2個端點都在同一社團的邊的數量的貪心算法的KL算法［3］是劃分算法中最經典的2種。但這類算法需要預先給定社團數量，不適合實際工作。層聚類算法在社會學領域中分為凝聚和分裂2種，這兩類算法都需要先計算每對節點對的連接強度。鏈接強度的計算方法有很多種，如邊界數、邊聚集系數、相異性指數、信息度、基于隨機游走的相似性等。凝聚算法會重復的聚合連接強度最高的節點對，分裂算法會重復的刪除連接強度最低的節點對之間的邊，從而獲得劃分網絡的結果。文獻［4］提出一種基于邊界數分裂方法，即GN算法。該算法在許多網絡都能成功應用，但它的復雜度不太理想，對任意一個m條邊n個節點的網絡，GN算法的時間復雜度是O（m2n），而在稀疏網絡情況下，時間復雜度將達到O（n3）。文獻［5］提出了相類似的層聚類算法，即CNM算法，其計算復雜度為O（md lb（n）），d是聚類分析時群落結構的深度，稀疏網絡情況下為接近線性的O（n lb2（n）），但準確率都不是很高。其他小眾但卻有巨大影響力的算法有基于信息論的社團發現算法和標號轉播算法等。文獻［6］的信息論算法（InfoMap算法）以極高的計算復雜度O（n（n+m））為代價得到了極高的準確度。該算法是目前非重疊社團劃分的眾多算法中準確度較高的一種算法。

本文提出一種新的社團劃分算法，首先根據節點相似度，通過只合并最相似節點對的方式實現對網絡的初步社團劃分，簡化網絡結構。再以局部模塊度為閾值，根據社團相似度進一步聚合社團，從而避免文獻［7］算法每次聚合都要計算模塊度的缺點，降低時間復雜度。

2 背景知識

復雜網絡是彼此錯綜聯系在一起的節點組成集合，本節著重介紹社團結構的衡量標準和相似度衡量標準，這些是本文算法的知識基礎。

2.1 社團結構

用G=（V，E）表示一個無權重無方向的網絡，其中，V表示網絡中節點的集合；E表示網絡中邊的集合。

社團結構是一個定性的定義，一般將網絡中具有相同屬性的節點劃分在一個社團。學者們嘗試用不同的算法將其量化，其中以Newman根據社團內節點連接緊密、社團間節點聯系稀疏而提出的模塊度Q最為著名，在無權重網絡中其定義如下：

其中，ai=∑jeij，eij表示網絡中橫跨社團Ci和社團Cj的邊的數量占所有邊數的比例。

模塊度Q越高代表社團結構劃分得越優秀，由此產生了眾多基于模塊度的貪心思想的社團劃分算法。由于模塊度Q的計算量很大，該類算法具有較高的計算復雜度，文獻［7］提出了局部模塊度Q′，只需計算局部信息而不用考慮全局，計算量得到大幅減少，其定義如下：

其中，Lin表示社團內的邊數；Lout表示該社團與外界連接的邊數。

盡管使用模塊度來評價社團劃分結果是業界比較流行的，但該方式仍有其局限性，如不能發現網絡中心的強連通小社區和當網絡不具有社區結構時，也有比較大的模塊度等。所以，本文使用NM I（Normalized M utual Information）來作為算法準確度評價的指標［8］。基于信息論的NM I用于量化衡量分區的相似性，已經被證明是可靠的指標，其被應用于網絡社團中的公式為：

其中，A表示實際社團；B表示通過算法劃分的社團；CA表示A社團數量；CB表示B社團數量；在N矩陣中，Nij表示在記在A的社團i又在B的社團j的所有節點數量；Ni.表示N矩陣第i行的和；N.j表示N矩陣第j列的和。

2.2 相似度

2.2.1 節點相似度

節點相似度用來量化節點對的連接強度。節點相似度有很多種計算方式，如Jaccard指標、Adam ic-Adar指標、Leicht-Holme-Newman指標等。據文獻［9］中對社團劃分節點相似度的計算公式如式（4）所示。

其中，T（i）表示節點ni的鄰節點集；z∈T（i）∩T（j）表示節點ni和節點nj的公共鄰節點集；k（z）表示節點z的度。但是式（1）不能區分出直接相連的節點對與不直接相連的節點對的相似度。如在Zachary棒球俱樂部網絡中，通過式（4）計算，節點3與節點34的相似度極高。但事實上這2個節點分屬不同社團，故進一步修正式（4）為式（5）：

對于一些特殊情況：如當z∈?時，即相鄰節點ni和節點nj沒有公共鄰節點時，如果ni的度為1，則Sij=1，否則Sij=0。如圖1所示，n8和n9沒有公共鄰節點，但顯然n9完全依賴n8，S98應為一個極大值。

圖1 節點相似度計算示意圖

2.2.2 社團相似度

將節點相似度推廣到社團相似度，可得到下式：

其中，T（Ci）表示與社團Ci有邊直接連接的社團集合；K（Cz）表示社團Cz中與其他社團連接的邊數。當Cz∈?時，即社團Ci和社團Cj沒有公共鄰社團時，如果，則SCij=1，否則SCij=0。

2.3 基于節點相似度的聚類社團發現算法

基于節點相似度的聚類社團發現算法于近期提出，步驟如下：（1）隨機選取某未劃分社團的節點；（2）聚合與該節點相似的鄰節點；（3）網絡中所有節點都劃分社團，算法結束，反之重復步驟（1）。

該類算法的問題在于步驟（2）中，如何選定與指定節點相似的節點。目前衡量節點相似度的算法有很多，但相似度閾值的確認問題還未能被有效的解決，從而影響了算法的準確度。閾值過高，會使得最終社團劃分得過于碎片零散；閾值過低，會使得最終社團劃分得過于粗獷，將實際上應屬于不同的社團的節點合并在了一個社團中。文獻［9］直接規避了這個問題，提出根據不同網絡，實時調整閾值，但具體如何調整閾值，沒有展開。文獻［7］提出以公共鄰節點數量作為節點相似度、用模塊度作為每一次合并節點的閾值的算法，記該算法為NS1，這樣做雖然保證了準確度卻提高了計算復雜度；文獻［10］提出的算法，首先使用基于節點相似度和寬松的閾值聚類網絡中節點，再依次計算每個節點在其他社團時的模塊度，從而以模塊度增大的方向對當前社團劃分做微調整，記該算法為NS2，這種做法僅適用于個別節點劃分錯誤的情況，對于大規模節點劃分錯誤無效（如前期閾值選擇過低，錯誤的將不同社團合并到一個社團），而且增加了算法的復雜度。

3 本文算法

3.1 算法描述

對網絡進行社團劃分，是為了將具有相同屬性的節點聚合在一起，從而讓人們更進一步研究網絡子結構屬性。由此可以推論出相似度越大的2個節點，越有可能屬于同一個社團。

對于網絡G=（V，E），計算出節點相似度矩陣S，首先不斷合并具有最大相似度的節點對，完成社團初步劃分。再根據局部模塊度的增量進步一合并社團，直到獲取最大的模塊度。

算法具體描述如下：

輸入 一個無向無權重網絡G=（V，E）

輸出 網絡的社團結構

步驟1 如果V=?，算法結束。否則，根據2.3節知識獲得nxn的節點相似度矩陣S=｛Sij｝，其中，n為G的節點數，即n=|V|。新建V′=V。

步驟2 在V中任意選取節點ni，根據相似度矩陣S，選取其最相似節點集N。V′=V′-ni。

步驟3 如果節點ni和節點集N不屬于任何社團，新建社團Ci，Ci=ni+N。如果節點ni或節點集N中的任意節點有社團屬性，分別屬于為Cx，Cy等，則合并這些社團為Cz，使ni∈Cz，N∈Cz。

步驟4 當V′≠?時，跳轉步驟2。

步驟5 定義局部模塊度Q′=0。

步驟6 新建社團集C，集合中包含網絡當前劃分的社團。新建Qmax=Q′。

步驟7 根據2.2節知識獲得社團相似度矩陣SC=｛SCij｝。

步驟8 在C中任取一社團Ci，根據社團相似度矩陣SC，選取其最相似社團集CN。C=C-Ci。

步驟9 合并社團Ci和最相似社團集CN組成新的社團C′i。計算局部模塊度Q′i，如果Q′i＞Qmax，則Qmax=Q′i；反之，退回步驟8。

步驟10 當C≠?時，跳轉步驟8；當C=?時，如果Qmax＞Q′，Q′=Qmax，跳轉步驟6。

步驟11 輸出結果

3.2 可行性分析

基于相似度的聚類算法和依據模塊度的聚類算法如CNM算法思維類似，都是以局部最優獲取最終結果，這就不可避免地造成結局不是最優，所以該類貪心算法準確度很難達到100%，但目前已有算法中，沒有能達到完全準確的算法。所以，本文提出的這種依據相似度的貪心算法，若能實現比已知同類算法時間復雜度低且準確度高，就是一個優秀的社團發現算法。本節將著重分析本文提出的算法如何降低了時間復雜度和提高了準確性。

3.2.1 時間復雜度分析

本文提出的算法計算花費主要由2個部分構成：一是通過節點相似度初步劃分網絡，二是通過局部模塊度和社團相似度對進一步聚合社團。初步依據最相似聚類節點，所有節點需遍歷一次，且每個節點都要需要在其鄰節點中找出最相似的節點，故時間復雜度為O（kn），k為節點度數。進一步聚合網絡階段，依據模塊度和社團相似度，至多需要合并O（lg m）次，m為網絡中邊的數目，每次合并計算社團相似度和模塊度增量的時間復雜度為O（n），故該部分的時間復雜度為O（n lg m）。綜上所示，本文提出的算法時間復雜度為O（n lg m）。而NS1算法的時間復雜度為O（mn），NS2算法復雜度為O（n2m）。因此，本文算法的時間復雜度遠高于同類基于節點相似度的聚類算法，在一定程度上提高了運行效率。

3.2.2 準確度分析

社團劃分的目的是社團內節點連接緊密、社團間節點聯系稀疏，依據此提出模塊度Q是目前對社團劃分算法的評價標準，但其存在自身局限，Q值越高不代表越接近真實情況。下面通過一個簡單的例子來說明。考慮2個社團構成的網絡，社團S1為100個節點的完全圖（任意節點之間都存在邊），社團S2為4個節點的完全圖，社團S1與社團S2之間以一條邊連接，如圖2（a）所示。很明顯的這個網絡應該被劃分為S1和S2兩個社團，但對于指著這種劃分，模塊度Q才為0.002 417 38，而對于圖2（b）這種劃分方式，模塊度Q為0.002 564 459，比前者要高，但劃分結果卻遠離社團實際真實情況。

圖2 社團S1和社團S2組成的網絡及其劃分

所以，以模塊度最大化作為每一步節點合并的標準，對個別情況（如上文舉例的社團大小差異過大）中的部分節點的社團歸類不適用，即模塊度不適用于單個節點對聚類。但是用節點相似度就避免了這類情況，再次考慮圖2（a）所示網絡，連接S1和S2的2個節點沒有公共鄰節點，故兩個點的相似度為0，從而自然將2個社團劃分開。

本文嘗試用比較粗獷的方式定義算法評價標準：使社團間的邊數最小化。即如式（7）所示，i，j表示網絡中的節點，eij當且僅當節點i，j相連是為1，否則為0。

如果節點i，j被劃分到不同社團，則社團間的邊數至少為公共鄰節點數量。即：

其中，T（i）表示節點i的鄰節點。所以可以通過以公共鄰節點數量作為相似度，將公共鄰節點多的節點對劃分在一個社團，從而實現社團間的邊數最小。文獻［6］根據實驗表明，增加考慮公共鄰節點的度數，可以提高算法的準確度。因此，本文算法采用包含公共鄰節點和其度數的RA指標作為衡量兩相鄰節點相似度的標準，以最相似作為閾值聚合節點保證初步快速社團劃分的準確度。

由此可以得出，本文提出的算法比以依據模塊度增量的聚類算法（如CNM算法）和以模塊度增量作為每次聚類單個節點的閾值的算法（如NS1算法）準確度高。后續實驗數據也證明了本文算法比同類聚類算法具有更高的準確度。

4 實驗與結果分析

為了評估本文提出算法的效果，本節將該算法應用于一些實際網絡，如海豚社團網、Zachary空手道俱樂部網絡、足球隊網絡和計算機仿真網絡。所有實驗均在2.3 GH的處理器和3 GB內存的筆記本上運行。

4.1 現實網絡

4.1.1 海豚社團網絡

Lusseau通過7年的觀察，總結了生活在新西蘭附近海域的62只海豚的社團網絡，這個網絡也是如今復雜網絡領域中重要的測試用例［11］。海豚群漸漸分化為成年海豚群和年幼海豚群，成年海豚群又進一步分化成更小的海豚群。

使用本文算法劃分海豚社團，過程如圖3所示。其中，圖3（a）為Lusseau觀察總結出的海豚網絡；圖3（b）為基于節點相似度快速聚合社團的結果，該過程將網絡初步劃分出10個社團。圖中節點代表海豚個體，點與點之間的連線代表這2個海豚相似度最高。圖3（c）為基于社團相似度和局部模塊度進一步聚合社團結果，圖中4中顏色代表本算法劃分出的4個不同社團。

圖3 本文算法處理海豚網絡過程

本文算法與其他算法的準確度及時間復雜度對比結果如表1表示，本文算法運算時間最低，可近似于忽略不計，準確度NM I為0.580 1，比InfoM ap算法高2.4%，比NS1算法高1.0%。同時本文算法在時間和NM I上相比于CNM算法、LAP算法和M ultiLevel算法都有一定優勢。

表1 海豚網絡社團劃分算法對比

4.1.2 大學足球隊網絡

大學足球隊網絡［12］代表的是某個賽季中大學足球隊的比賽情況。該網絡由115個節點組成，代表了115個參賽足球隊，節點之間用邊相連，表示2個足球隊之間有比賽。由于比賽將115個足球隊劃分為12個小組，因此小組內的球賽會比與組間球賽數量更多。使用本文算法劃分結果如表2所示。本文算法與其他算法的準確度及時間復雜度對比結果如表3所示。與CNM算法、InfoM ap算法和LAP算法相比，本文算法的運算時間最短，為0.000 8 s，準確度NM I為0.954 5，與InfoM ap差距4.7%，但是卻高出NS1算法8.2%，高出LAP算法1.3%，高出CNM算法25.7%，雖和M ultiLevel算法準確度持平，但用時僅為MultiLevel算法的40%。可見，相比于一些常見的算法，本文算法在現實網絡具有一定的優勢。

表2 本文算法處理足球隊網絡的社團劃分結果

表3 足球隊網絡社團劃分算法對比

通過將本文算法運用于海豚等3個現實網絡，可以很容易的發現本文提出的算法準確率可以達到InfoMap算法的水平，同時算法用時略低于LAP標簽算法。由此可見，本文算法在現實網絡中具有很高的準確度和較低的時間復雜度，是一種優秀的算法。

4.1.3 微博網絡

以上通過小規模實際網絡方面說明了本文算法的有效性。本節將選用大規模實際網絡來驗證本文算法。通過調用新浪微博API接口，下載存儲新浪用戶網絡信息。這里以用戶為節點，用戶之間相互關注為邊，從而截取構建出10萬個節點、100萬條邊的微博網絡。由于不知該網絡的正確社團劃分結果，所以這里以模塊度Q作為標準比較各類算法的準確度，一般認為，模塊度Q值越高，社團劃分效果越理想。本文算法與其他算法處理該網絡結果如表4所示。NS1算法獲得最高的Q值，但由于該算法每一步都需計算一次模塊度Q導致用時過多，本文算法取得與NS1差不多的模塊度（Q值相差2.4%），但用時僅為其用時的4.2%。

表4 微博網絡社團劃分算法對比

4.2 模擬網絡

基準圖［13］是由Lancichinetti等人提出的計算機模擬網絡，它的網絡擁有與現實網絡相類似的社團規模和節點度的異構分布，適合作為評估社團發現算法的測試用例。在基準圖中節點度分布和社團大小按照冪律分布。節點度冪律分布的指數為γ，社團規模冪律分布指數為β，μ稱為拌和參數，1-μ表示節點與所在社團內的節點連接的概率。

將本文提出的算法應用在平均節點度k=20、節點度分布指數γ=2.5、社團規模分布指數β=1.5、拌和參數μ從0.1到0.6的基準圖中。社團劃分結果如圖4所示。其中的3個圖分別代表節點數為1 000，50 000，10 000的基準圖。隨著拌合參數μ的增大，社團之間的區分越發模糊，即劃分社團難度越大。在圖4中可以看出，除了InfoMap算法一直以極高的時間復雜度為代價保持著NM I接近1的準確度，其他算法都隨著μ值增大，用時增加而準確率在下降。本文提出的算法無論在用時還是準確度上，都遠遠高于CNM算法。與MultiLevel算法相比，本文算法準確率與其持平，但用時略低于M ultiLevel算法。當μ≤0.6時，本文提出的算法的準確度NM I始終保持在0.8以上。雖然本文算法應用于計算機模擬網絡的優勢沒有應用于現實網絡那么明顯，但它能在極短的用時下，達到較高的準確度，實驗效果優于CNM算法，時間也略優于M ultiLevel算法。

圖4 基準圖

5 結束語

本文提出的基于相似度和局部模塊度的算法，是一種能夠在網絡中快速劃分社團結構的算法。該算法不需要事先確定社團數目和網絡的全局信息，只需要節點局部信息就能夠得到較好的結果，大幅降低了算法的時間復雜度。在具體實驗中以不同節點作為算法入口，發現最后的社團劃分結果都一致，即說明本文算法具有很好的穩定性。進一步通過與其他算法的對比實驗，實驗結果也證明了本文算法不僅具有著較高的準確率，同時時間復雜度也較低。不過目前對本文算法的分析還局限于社團非重疊網絡，后續工作是研究如何將該算法應用于重疊社團網絡中。

［1］ Newman M E J.The Structure and Function of Complex Networks［J］.SIAM Review，2003，45（2）：167-256.

［2］ Albert R，Barabasi A L.Statistical Mechanics of Complex Networks［J］.Reviews of Modern Physics，2002，74：47-97.

［3］ Kernighan B W，Lin S.An Efficient Heuristic Procedure for Partitioning Graphs［J］.Bell System Technical Journal，1970，49（2）：291-307.

［4］ Girvan M，Newman M E J.Community Structure in Social and Biological Networks［J］.PNAS Proceedings of the National Academy of Sciences，2002，99（12）：7821-7826

［5］ Newman M E J.Fast Algorithm for Detecting Community Structure in Networks［J］.Physical Review E，2004，69（6）.

［6］ Rosvall M，Bergstrom C T.Maps of Radom Walks on Complex Networks［J］.Proceedings of the National Academy of Science，2008，105（4）：1118-1123.

［7］ 劉 微.基于共享鄰居數的社團結構發現算法［J］.計算機工程，2011，37（6）：172-174.

［8］ Xuan V N，Julien E，James B.Information Theoretic Measures for Clusterings Comparison：Variants，Properties，Normalization and Correction for Chance［J］.The Journal of Machine Learning Research，2011，11（10）：2837-2854.

［9］ Ying Pan.Detecting Community Structure in Complex Networks via Node Similarity［J］.Physica A，2010，389：2849-2857.

［10］ 胡 瓊.社會網絡結構劃分算法研究［D］.上海：上海交通大學，2014.

［11］ Lusseau D.The Emergent Properties of a Dolphin Social Network［J］.Proceedings of the Royal Society of London，Series B，2003，270（Suppl.）：186-188.

［12］ Sun PG，Gao L，Han Shanshan.Identification of Overlapping and Non-overlapping Community Structure by Fuzzy Clustering in Complex Networks［J］.Information Sciences，2011，181（6）：1060-1071.

［13］ Andrea L，Santo F，Filippo R.Benchmark Graphs for Testing Comm unity Detection Algorithm s［J］.Physical Review E，2008，78（4）.

編輯 金胡考

Comm unity Partition Algorithm Based on Similarity

WU Weiwei，LIU Gongshen，HUANG Chen
（National Engineering Laboratory of Information Content Analysis Technology，Shanghai Jiaotong University，Shanghai 200240，China）

The partition of complex network is useful to find the real community structure and help people research the real world，so this paper proposes a new algorithm of communities partition in network based on the local module degree and similarities.The algorithm calculates the similarities between the nodes in the network and aggregates the nodes which have the highest correlation.It aggregates the communities based on the local module degree and community similarity. Then the results is gotten which has the best local module degree.To verify the validity of the algorithm，this paper applies it in the real network and computer simulation network，and com pares the algorithm with other algorithm s.The result shows that the proposed algorithm has lower computational complexity and higher accuracy compared with NS1，CNM，LAP algorithm s，etc..

nodes；similarity；community；complex network；module degree

吳蔚蔚，劉功申，黃 晨.基于相似度的社團劃分算法［J］.計算機工程，2015，41（11）：67-72，83.

英文引用格式：Wu Weiwei，Liu Gongshen，Huang Chen.Community Partition Algorithm Based on Similarity［J］. Computer Engineering，2015，41（11）：67-72，83.

1000-3428（2015）11-0067-06

A

TP393

10.3969/j.issn.1000-3428.2015.11.012

國家“973”計劃基金資助項目（2013CB329603）；國家自然科學基金資助項目（61171173）。

吳蔚蔚（1990-），女，碩士，主研方向：復雜網絡；劉功申，副教授；黃 晨，碩士。

2014-10-09

2014-12-02 E-m ail：vivibear@sjtu.edu.cn