基于稠密子團和邊聚類系數的局部社團挖掘算法

羅 浪，張紹武，陳 韜

（西北工業大學 自動化學院，陜西 西安 710072）

近年來，復雜網絡已在計算機科學、生物學、統計物理學、社會學和經濟學等領域在內的廣泛關注，并且逐步體現出了一定的應用價值。復雜網絡最重要、最普遍的拓撲結構屬性之一是社團結構，社團結構是指在復雜網絡中那些節點之間連接非常緊密的小團體。團體內節點連接緊密，團間連接稀疏。網絡社團結構的發現與分析對于了解整個網絡結構、特征及功能有其重要意義，且在生物學、物理學、計算機、社會學和經濟學等領域發揮的重要作用[1-3]。

目前已經提出了較多社團挖掘算法，根據刪除/添加邊、點準則，復雜網絡社團挖掘算法一般可分分裂和凝聚二類算法，其代表性經典算法分別為GN算法[4]，FN算法[5]。GN算法通過不斷刪除網絡中邊介數最大的邊對網絡進行劃分，時間復雜度較高；FN算法則通過模塊度值變化合并網絡對網絡實施劃分。 Wang等人[6]不斷尋找最大程度改進節點局部模塊度的點，將其加入社團，對網絡進行社團劃分。Hu等人[7]用邊聚類系數替換GN算法中的邊介數，提出一種基于邊聚類系數的分裂算法，但該算法仍有GN算法一些缺點。Zhang等人[8]利用鄰居節點與社團的連接緊密程度，不斷尋找滿足它要求的條件的節點，將這些節點加入社團，從而發現社團結構，該算法速度較快，但準確度不高。2011年，Liu等人[9]改進了Wang和Zhang算法，通過不斷尋找與社團共享鄰居數最多的鄰居節點，基于局部模塊度[10]劃分社團。由于該算法每次僅選取一個節點加入社團，導致最后剩下的孤立節點較多，因而算法準確度不高、運算時間較長。針對文獻[9]產生的孤立節點較多問題，本文提出一種基于稠密子圖和邊聚類系數的局部社團挖掘算法，并計算機生成網絡、Zachary網絡、三社團網絡和美國足球俱樂部網絡上進行了仿真實驗驗證。

1 基本概念

1.1 共有鄰居數

在社團的鄰居節點中，若某節點與社團C的共有鄰居節點數目越多，則此節點與社團C的連接就越緊密，也就是說該點屬于社團C的可能性就越大。給定一個無權無向網絡G（V，E），其鄰接矩陣為 A（aij），若節點 vi和 vj有邊相連則 aij=1，否則aij=0。 設Ni，Nj分別為節點 vi和 vj的所有鄰居節點集合。則任意兩個節點的共有鄰居數定義為：|Nij|=|Ni∩Nj|。如圖1 所示，節點 v4的鄰居節點為{v1，v2，v3，v5，v6，v7，v8}，節點 v7的鄰居節點為{v4，v5，v6，v8，v9}，則節點 v4與節點 v7的共有鄰 居為{v5，v6，v8}，即|N47|=3，相對于其他節點來說節點 v4與節點 v7的連接是最緊密的。而節點v3與節點v9跟任何節點都不具有共有鄰居，則N39為空集，即|N39|=0。

圖1 簡單連接圖Fig.1 Simple connection diagram

1.2 稠密子團

給定一個無權無向的網絡G（V，E），設網絡中度最大的節點為 va，則 va的鄰居節點集合為 N={v1，v2，…，vk}， 集合 N中與節點va的共享鄰居數最多的節點集合為 N′={v1，…，vr}，次多的節點集合為N″={v1，…，vo}，則稠密子團定義為Cd={vx=（{va}∪N′∪N″）}。

由于稠密子團是由一個節點和它的某些鄰居所組成，且連接的密集程度比較高，所以可以利用這個特性將稠密子團作為一個初始聚類團，并逐漸擴張成社團結構。

1.3 邊聚類系數

在網絡G=（V，E）中，假設兩個節點vi和vj有一條邊為eij，節點vi和vj在網絡中的共有相鄰節點vk，則有相鄰邊 eik、ejk，與eij形成一個邊數為3的閉合路徑即一個三角環。則復雜網絡中一條邊的邊聚類系數[7]Cij定義為

其中 ki、kj分別表示節點vi和vj的度，zij為網絡中實際包含該邊的三角環總數，分母為網絡中包含該邊的最大可能存在的三角環總數。邊聚類系數Cij反映兩個節點在同一個社團的可能性，Cij值越大，則這兩個節點在一個社團的可能性就越大。

2 DIDE算法

DIDE算法，首先通過選取一個稠密子團作為初始聚類團，然后通過對邊聚類系數和模塊度的值不斷擴張稠密子團，從而形成社團。實施過程如下：

1）稠密子團選取

Step 1取網絡中節點度最大的節點作為初始節點；

Step 2尋找初始節點鄰居節點v0；

Step 3計算v0與初始節點的共有鄰居數；

Step 4將共有鄰居數最多、次多的v0都加入到稠密子團中。

2）稠密子團擴張

Step 1計算稠密子團的局部模塊度值 QC=Lin/（Lin+Lout），其中Lin為社團內部連接數目；Lout社團內部節點與社團外部節點連接數目；

Step 2尋找稠密子團鄰居節點vi；

Step 3計算vi與稠密子團的連接緊密程度值Ui=|Eic|/di，其中|Eic|表示節點vi與社團的連接數目，di表示節點vi的度；

Step 4 若 Ui＞0.5，將 vi加入稠密子團；

Step 5計算剩余鄰居節點vl邊聚類系數，若該鄰居節vl點與社團C相連的邊聚類系數最大，則將vl加入到社團C中，形成新社團C′；

Step 6 計算 C′的局部模塊度 Q′值，若 Q′-QC＜0，則將此節點從社團C′中移除；

Step 7當剩余鄰居節點vl全部計算完之后C，更新社團C，并計算社團的局部模塊度值QC。重復Step 2-6，直到局部模塊度值QC不再變化為止；

Step 8返回1），直到找不到稠密子團為止。

3）孤立節點的加入

在所有社團都劃分完之后，將孤立節點隨機加入到已劃分的社團中。

DIDE算法流程圖如圖2所示。

圖2 DIDE算法流程圖Fig.2 The flowchart of DIDE algorithm

3 實驗與分析

1）計算機生成網絡

首先我們在計算機生成網絡上驗證DIDE算法性能。計算機生成網絡是由128個節點組成，分為4個社團，每個社團包含32個節點。假設每個節點與社團內部的連接數為zin，與社團外部的連接數為zout，且zin+zout=16。隨著zout的不斷增加，該網絡的社團結構將會變得越來越模糊，當zout＞8時，則認為此時網絡不具有社團結構。DIDE算法及其他7種算法（Liu、Zhang、GN、FN、SA、CPM、FEC）對計算機生成網絡的劃分結果如圖3所示。

圖3 8種算法聚類精度比較Fig.3 Comparison of 8 algorithms relative to the fraction of vertices classified correctly

圖3可以看出，DIDE算法社團劃分性能優于 Zhang、Liu、GN、FN、SA、FEC、CPM 算法。 雖然 DIDE 算法社團劃分性能低于SA算法，但SA算法時間復雜度較高。SA算法的計算速度完全取決于模擬退火算法效率，但模擬退火算法收斂速度很緩慢。文獻[11]中利用SA算法對一個有3885節點、7260條邊的網絡進行社團劃分，居然花了3天時間。而DIDE的算法時間復雜度僅為O（n2），n為網絡的節點數，也可以達到較高的準確度。

2）三社團網絡

三社團網絡是由19個節點，37條邊構成了一個經典的驗證網絡，如圖4所示。

圖4 三社團網絡結構圖Fig.4 The structure of three groups network

DIDE算法對該網絡社團劃分過程如下：首先從度最大的節點v7、節點v8、節點v9和節點v17中隨機選取一個節點作為初始節點。我們取節點 v17，形成的稠密子團 Cd1={v14，v15，v17，v19}，利用邊聚類系數以及局部模塊度值擴張為社團C1={v14，v15，v16，v17，v18，v19}，它的局部模塊度 Q 值為 0.916 7。 然后選擇節點形成稠密子團 Cd2={v4，v5，v6，v7}，最后擴張為社團 C2={v1，v2，v3，v4，v5，v6，v7}，它的局部模塊度 Q 值為 0.7857。 同理可以得到以節點為初始節點的稠密子團 Cd3={v8，v9，v10，v11，v12，v13}，即 局 部 模 塊 度 Q 值 為 0.923 0 的 社 團 C3={v8，v9，v10，v11，v12，v13}。DIDE算法在三社團網絡上的劃分結果與實際網絡結構完全一致。

3）Zachary網絡

Zachary網絡為美國一所大學空手道俱樂部成員間相互社會關系網，該網絡由34個節點和78條邊組成，節點代表俱樂部成員，而邊代表俱樂部成員之間的關系。Zachary網絡上， DIDE、Zhang、GN、Liu、FN 算法社團劃分結果如表 1。 表 1結果表明：DIDE和Liu算法的劃分效果優于 Zhang、GN和FN算法，與實際網絡社團結構完全一致。

圖5為DIDE算法對Zachary網絡的社團劃分結果。圖中菱形社團的局部模塊度Q值為0.782 5；三角形社團的局部模塊度值Q為值0.708 5。

表1 五種算法對Zachary網絡的社團劃分結果Tab.1 The results of detecting Zachary network community by 5 algorithms

圖5 DIDE對Zachary網絡劃分結果圖Fig.5 Tthe result of detecting Zachary network community by DIDE

4）美國足球俱樂部網絡

美國足球網絡是美國大學生足球聯賽得出的一個復雜網絡，網絡中的節點代表一只足球隊，邊代表兩個球隊之間進行過一場比賽，它一共包含115個節點及616條邊。聯賽中存在若干聯盟，每個節點都屬于其中一個聯盟，聯盟內部球隊間比賽次數多于聯盟間球隊進行的比賽次數。這115支球隊共存在12個聯盟。

表2是DIDE算法與其它算法對美國足球俱樂部網絡社團劃分結果對比，從表2中結果表明，在分團數方面DIDE與Liu的算法分為12個團要優于Zhang算法以及 GN、FN算法。而在正確率方面，同為12個分團數，由于DIDE算法在循環中同時加入多個節點，從而減少孤立節點，所以要比Liu算法準確度更高。

DIDE算法對美國足球俱樂部網絡的社團劃分結果如圖6所示，表3為12個聯盟球隊編號以及每個聯盟的局部模塊度Q值。

表2 五種算法對美國足球俱樂部網絡社團劃分結果Tab.2 The result of detecting American football club network community by 5 algorithms

在美國足球俱樂部網絡中，DIDE算法一共錯分了9個節點（43，59，60，64，81，83，91，98，111），由于實際原因，這些節點所代表的球隊跟外聯盟球隊比賽次數要多于聯盟內部比賽次數導致了DIDE算法出現了一些錯分情況，但是DIDE算法仍能夠達到較高的劃分正確率。

4 結 論

本文通過定義稠密子團，利用邊聚類系數以及局部模塊度不斷擴張稠密子團，提出一種基于稠密子團和邊聚類系數的局部社團挖掘算法（DIDE）。DIDE算法以稠密子團這種連接密集程度比較高的聚類團為種子，在一定程度上減少算法時間復雜度，循環過程中同時加入多個節點以減少孤立節點數目，從而提高了社團劃分的準確性。在計算機生成網絡及其他幾個現實經典網絡（三社團網絡、Zachary網絡、美國足球俱樂部網絡）上，通過與Liu、Zhang、GN、FN算法進行對比，實驗結果表明 DIDE算法性能優于Liu、Zhang、GN、FN算法，比Liu方法更適合較大規模網絡社團劃分。

圖6 DIDE對美國足球俱樂部網絡劃分結果圖Fig.6 The result of detecting American football club network community by DIDE

表3 DIDE算法得到的聯盟球隊編號及局部模塊度值Tab.3 Union team numbers and local modularity value by DIDE

[1]ALBERT R，JEONG H，BARABSI A L.The diameter of the World Wide Web[J].Nature，1999（401）:130-131.

[2]SCOOT J P.Social network analysis:a handbook[M].London:Sage Publications，2000.

[3]HOLME P，HUSS M，JEONG H.Subnetwork hierarchies of biochemical pathways[J].Bioinformatics，2003，19（4）:532-538.

[4]NEWMAN M E J，Girvan M.Finding and evaluating community structure in networks.Phys.Rev.E，2004 （69）:02611.

[5]Newman M E J.Fast algorithm for detecting community structure in networks.Phys.Rev.E，2004（69）:066133.

[6]WANG Xu-tao，CHEN Guang-rong，LU Hong-tao.A very fast algorithm for detecting community structures in complex networks[J].Physica A，2007，384（2）:667-664.

[7]胡健，楊炳儒.基于邊聚集系數的社區結構發現算法[J].計算機應用研究，2009，26（3）:858-859.

HU Jian，YANG Bing-ru.Community structure discovery algorithm based on edge clustering coefficient[J].Application Research of Computers，2009，26（3）:858-859.

[8]ZHANG Da-wei，XIE Fu-ding，ZHANG Yong，et al.Fuzzy analysis of community detection in complex networks[J].Physica A:Statistical Mechanics and its Applications，2010，389（22）:5319-5327.

[9]劉微，張大為，謝福鼎，等.基于共享鄰居數的社團結構發現算法[J].計算機工程，2011，37（6）：172-174.

LIU Wei，ZHANG Da-wei，JI Min，et al.Community structure detection algorithm based on number of shared neighbors[J].Computer Engineering，2011，37（6）:172-174.

[10]Clauset A.Finding local community structure in networks.Phys[J].Rev.E， 2005（72）:026132.

[11]楊博，劉大有，Liu Ji-ming，等.復雜網絡聚類算法[J].軟件學報，2009，20（1）:54-56.

YANG Bo，LIU Da-you，LIU Ji-ming，et al.Complex network clustering algorithms[J].Journal of Software，2009，20 （1）:54-66.

[12]王立敏，高學東，宮雨，等.基于相對密度的社團結構探測算法[J].計算機工程，2009，35（1）:117-119.

WANG Li-min，GAO Xue-dong，GONG Yu，et al.Community structure detection algorithm based on relative density[J].Computer engineering，2009，35（1）:117-119.

[13]GIRVAN M，NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America，2002，99（12）:7821-7826.

[14]POTHEN A，SIMON H，LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM Journal on Matrix Analysis and Applications，1990，11（3）:430-452.