李學(xué)強(qiáng)　鐘大偉　孫圣民

摘要：在大型復(fù)雜網(wǎng)絡(luò)中自動搜尋或發(fā)現(xiàn)社區(qū)具有重要的實際應(yīng)用價值。該文把超圖模型以及基于此的聚類算法應(yīng)用到社區(qū)結(jié)構(gòu)發(fā)現(xiàn)領(lǐng)域。對于簡單圖的社區(qū)發(fā)現(xiàn)，引入了邊凝聚系數(shù)和三角環(huán)等概念，提出了基于三角環(huán)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法。通過Zachary網(wǎng)絡(luò)的實例驗證和算法的對比分析，證明了該算法在時間復(fù)雜度上能提高一個數(shù)量級。

關(guān)鍵詞：社區(qū)結(jié)構(gòu)；三角環(huán)；邊凝聚系數(shù)；社會網(wǎng)絡(luò)

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）07-1540-03

在現(xiàn)實生活中存在著各種各樣的網(wǎng)絡(luò)系統(tǒng)，如人際關(guān)系網(wǎng)、合作網(wǎng)、交通運(yùn)輸網(wǎng)、計算機(jī)網(wǎng)等。許多現(xiàn)實系統(tǒng)的網(wǎng)絡(luò)模型是介于完全規(guī)則和完全隨機(jī)之間的，這種網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò)[1]。復(fù)雜網(wǎng)絡(luò)不僅具有小世界、無標(biāo)度特性還具有社區(qū)結(jié)構(gòu)[2]的特性。社區(qū)內(nèi)部的節(jié)點之間的聯(lián)系相對緊密，而社區(qū)之間的聯(lián)系相對稀疏[3]。復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)的研究起源于社會學(xué)的研究工作。能夠在大型復(fù)雜網(wǎng)絡(luò)中自動搜尋或發(fā)現(xiàn)社區(qū)具有重要的實用價值，如社會網(wǎng)絡(luò)中的社區(qū)代表根據(jù)興趣或背景而形成的真實的社會團(tuán)體[4]，發(fā)現(xiàn)社會網(wǎng)絡(luò)中的這些社區(qū)有助于我們更好地理解和應(yīng)用社會網(wǎng)絡(luò)。目前，社區(qū)發(fā)現(xiàn)的算法很多，其中Kernighan-Lin算法[5]、Laplace圖特征值的譜二分法[6]、GN算法[7]等比較經(jīng)典。其中GN算法是Newman和Girvan在其研究中提出了基于邊介數(shù)的分割方法，盡管該方法計算量很大，但由于其性能優(yōu)越而成為社區(qū)發(fā)現(xiàn)研究的重要參考模型。

盡管人們對復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題已進(jìn)行了大量的研究，但是仍然還存在一些目前無法解決的問題，如社區(qū)的概念雖然大量使用，但缺乏嚴(yán)格的數(shù)學(xué)定義；大多數(shù)的發(fā)現(xiàn)算法計算量很大；很多算法不是針對異構(gòu)數(shù)據(jù)集。因此，復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)研究還遠(yuǎn)沒有形成體系，有許多工作有待于進(jìn)一步完善[8]。

本文給出一種新的社區(qū)發(fā)現(xiàn)算法，根據(jù)三角環(huán)來判斷社區(qū)。該文的結(jié)構(gòu)如下：第1節(jié)算法的整體描述；第2節(jié)對算法進(jìn)行實例驗證并與經(jīng)典算法作對比；第3節(jié)總結(jié)全文。

1 算法介紹及分析

1.1 相關(guān)概念的引入

三角環(huán)：網(wǎng)絡(luò)中邊數(shù)為3的閉合回路形成的三角形。如圖1中，節(jié)點3、4、6；節(jié)點4、5、6等可以構(gòu)成三角環(huán)的形式。

點凝聚系數(shù)：對于某個點的鄰居節(jié)點之間實際存在的邊數(shù)與鄰居節(jié)點之間可能存在的最大邊數(shù)之比。一個網(wǎng)絡(luò)的凝聚系數(shù)就是網(wǎng)絡(luò)中節(jié)點凝聚系數(shù)的平均值。如圖1：節(jié)點1的鄰居節(jié)點分別是2、3、4、5、6，共5個節(jié)點。它們之間存在的最大邊數(shù)為：5（5-1）/2=10；實際上這5個節(jié)點間的有7條邊，那么節(jié)點1的點凝聚系數(shù)為：7/10=0.7。

邊凝聚系數(shù)：借助于節(jié)點的凝聚系數(shù)，來引入邊的凝聚系數(shù)概念。一條邊的邊凝聚系數(shù)定義為包含該邊的三角環(huán)所占的比例：

[Cij=zij+1min（ki-1，kj-1）] （1）

其中，[ki]，[kj]分別表示節(jié)點i和節(jié)點j的度數(shù)，[zij]表示網(wǎng)絡(luò)中實際包含的三角環(huán)的個數(shù)。上式中的分母表示包含該邊的最大可能的三角環(huán)的個數(shù)。圖1中，節(jié)點3和節(jié)點6的度數(shù)分別是5和4，則最多形成min（5-1，3-1）=3個三角環(huán)；而實際上包邊E3，6的三角環(huán)有三個：節(jié)點1、3、6，節(jié)點3、5、6，節(jié)點3、4、6.所以C3，6=4/3。

圖1 凝聚系數(shù)示意圖

將整個網(wǎng)絡(luò)G視為圖，那么一個社區(qū)V實際上就是G的子圖。社區(qū)V中的一個節(jié)點i的度[ki]來自兩部分，分別是V的內(nèi)部（[kiin（V）=j∈VAi，j]）和V的外部（[kiout（V）=j?VAi，j]）。下面給出社區(qū)緊密程度的兩種級別[9]：

如果社區(qū)V內(nèi)的任意一個節(jié)點i的[kiin（V）]均大于[kiout（V）]，即[kiin（V）>kiout（V）]，則稱該社區(qū)是強(qiáng)連接社區(qū)。

如果社區(qū)V內(nèi)的所有節(jié)點的[kiin（V）]和大于[kiout（V）]的和，即[i∈Vkiin（V）>i∈Vkiout（V）]，則稱該社區(qū)為弱連接社區(qū)。

1.2 算法的思想及主要流程

前面提到的GN算法是一種分裂算法。它的基本思想是，通過不斷的從網(wǎng)絡(luò)中移除介數(shù)最大的邊將整個網(wǎng)絡(luò)分解成不同社區(qū)。在這里，邊的介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過該邊的最短路徑的數(shù)目。這種算法為區(qū)分一個社區(qū)內(nèi)部邊和連接社區(qū)之間的邊提供了一種有效的度量標(biāo)準(zhǔn)。

GN算法雖然能彌補(bǔ)一些傳統(tǒng)算法的不足，但是一般要指定社區(qū)的個數(shù)，否則，該算法不知道要將網(wǎng)絡(luò)分解到什么程度停止。另外，該算法的時間復(fù)雜度較高，為O（n3）。算法效率較低的一個重要原因是邊介數(shù)的計算開銷大。針對上述情況，這里提出一種基于三角環(huán)的社區(qū)發(fā)現(xiàn)方法（Triangle Ring Community Detecting簡稱TRCD算法）?？紤]無向無權(quán)重的形式，用鄰接矩陣[Ai，j]表示節(jié)點間的關(guān)系，有邊相連則值為1，無邊相連則為0。

上述兩個社區(qū)的級別可以作為判斷子圖是否為一個社區(qū)的標(biāo)準(zhǔn)，只有滿足上述兩個定義的子圖才能作為一個社區(qū)。首先從整個網(wǎng)絡(luò)開始，不斷的刪除邊，直到不存在滿足上述定義的社區(qū)為止。該文中的方法和前面的GN算法類似，都是分裂式算法。該方法不是根據(jù)邊介數(shù)來選擇要刪除的邊，而

是根據(jù)邊凝聚系數(shù)這個新的指標(biāo)。

根據(jù)上述基本思想得到算法的具體步驟如下：

Step1：根據(jù)公式（1）所示，計算整個網(wǎng)絡(luò)中的每一條邊的凝聚系數(shù)[Cij]；

Step2：刪除凝聚系數(shù)最小的邊[Eij]；

Step3：重新計算以i和j為頂點的所有邊的凝聚系數(shù)，而其它的邊不需要重新計算；

Step4：返回Step2，直到網(wǎng)絡(luò)中不存在符合上述定義的社區(qū)。

1.3 算法分析

對于一個含有n個節(jié)點m條邊的網(wǎng)絡(luò)，整個算法運(yùn)行的時間為[O（m4/n2）]。顯然該算法的時間復(fù)雜度要低于GN的時間復(fù)雜度。因為所考慮的是局部信息，去邊以后無須所有的邊重新計算，所以降低了時間復(fù)雜度。該算法依賴于網(wǎng)絡(luò)中的三角環(huán)，如果網(wǎng)絡(luò)中三角環(huán)的數(shù)量很少，該方法將失去意義。大量的實例研究表明，社會網(wǎng)絡(luò)中三角環(huán)的數(shù)量比較大，而非社會網(wǎng)絡(luò)中，三角環(huán)的數(shù)量則相對較少。所以這種方法更適合于社會網(wǎng)絡(luò)。

2 實例驗證

2.1 在Zachary網(wǎng)絡(luò)上的實驗

圖2所示是某大學(xué)空手道俱樂部中34個成員之間的社會關(guān)系網(wǎng)絡(luò)，曾是人類學(xué)家懷恩扎卡利（Wayne Zachary）在20世紀(jì)70年代研究的對象。Zachary網(wǎng)絡(luò)在復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)分析中已經(jīng)成為一個經(jīng)典問題，成為了衡量社區(qū)結(jié)構(gòu)劃分算法準(zhǔn)確性的標(biāo)準(zhǔn)[10]。在調(diào)查研究過程中，該俱樂部的主管與校長因是否抬高俱樂部收費(fèi)的問題產(chǎn)生了爭執(zhí)。結(jié)果，這個俱樂部分裂成了兩個分別以校長和主管為核心的小俱樂部。下面以Zachary網(wǎng)絡(luò)為例檢驗TRCD算法在實際網(wǎng)絡(luò)中的應(yīng)用。

按照文中算法的流程，得到最終的結(jié)果如下圖3所示，為了與圖2方便比較，圖3中沒有將邊去掉。其中圓形節(jié)點代表由節(jié)點27得到社區(qū)A，方形節(jié)點代表另一個社區(qū)B。A和B社區(qū)就代表著以校長和主管為核心的小俱樂部，這個結(jié)果同實際存在的社區(qū)是一致的。

2.2 與經(jīng)典算法的比較

從算法準(zhǔn)確性和算法的復(fù)雜度兩方面將文中的算法與三種經(jīng)典的算法作對比。

GN算法是一種分裂方法，其基本思想是不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊。譜二分法是利用網(wǎng)絡(luò)結(jié)構(gòu)的Laplace矩陣中不為0的特征值所對應(yīng)的特征向量和同一個社區(qū)內(nèi)的節(jié)點對應(yīng)的元素近似值的原理對網(wǎng)絡(luò)社區(qū)進(jìn)行劃分。這兩種算法應(yīng)用到Zachary網(wǎng)絡(luò)中所得到的社區(qū)結(jié)構(gòu)如圖4所示。

其中圖4中所有的圓形節(jié)點是在同一社區(qū)，其余節(jié)點屬于另一個社區(qū)。K-L算法是一種試探優(yōu)化法，它是一種利用貪婪算法將復(fù)雜網(wǎng)絡(luò)劃分為兩個社區(qū)的二分法。若將K-L算法應(yīng)用到Zachary網(wǎng)絡(luò)，得到的結(jié)果和文中算法一致，如上圖3。

圖3和圖4的區(qū)別是：節(jié)點3被劃分到兩個不同的社區(qū)。而真實的社區(qū)結(jié)構(gòu)如圖5所示，所以說，GN算法和譜二分法的結(jié)果使得節(jié)點3被錯誤劃分。并且譜二分法僅適用于由兩個社區(qū)組成的大網(wǎng)絡(luò)結(jié)構(gòu)，而GN算法對網(wǎng)絡(luò)社區(qū)進(jìn)行劃分時必須事先知道網(wǎng)絡(luò)中存在的社區(qū)個數(shù)。雖然K-L算法得到的社區(qū)跟實際結(jié)果一致，但是必須提前知道兩個社區(qū)的大小分別是16和18，因此K-L算法很難適用于實際網(wǎng)絡(luò)。這也說明了經(jīng)典算法存在一些不足。對TRCD算法而言，在進(jìn)行社區(qū)劃分之前不需要指定社區(qū)個數(shù)，這是一種自然劃分，能夠得到網(wǎng)絡(luò)中實際存在的社區(qū)結(jié)構(gòu)，而且算法的準(zhǔn)確性較高，所以該算法能克服其他算法的一些不足。

對于一個含有n個節(jié)點m條邊的網(wǎng)絡(luò)，TRCD算法的時間復(fù)雜度為O（m），空間復(fù)雜度是O（m4/n2）。將該算法與經(jīng)典的三種算法的復(fù)雜度作了對比，如表1。

[算法＼&空間復(fù)雜度＼&時間復(fù)雜度＼&GN算法＼&O（m+n）＼&O（m2n）＼&譜二分法＼&O（n2）＼&O（n3）＼&K-L算法＼&O（m+n）＼&O（n2）＼&TRCD算法＼&O（m+n）＼&O（m4/n2）＼&]

經(jīng)過對比分析，我們發(fā)現(xiàn)TRCD算法的思想易于理解，步驟簡潔；算法的準(zhǔn)確性較高；在復(fù)雜度方面，該算法也有一定的提高。

3總結(jié)

文中的TRCD算法，是在研究了近年來常見的一些方法的基礎(chǔ)上提出了根據(jù)邊的凝聚系數(shù)來求得下一步將要去掉的邊，因為考慮的是局部信息，去邊以后不需要重新計算所有的邊，所以與GN算法相比降低了時間復(fù)雜度。通過與經(jīng)典算法的比較，可以發(fā)現(xiàn)TRCD算法在算法的準(zhǔn)確性和算法復(fù)雜度方面都有一定的優(yōu)越性。特別地，該算法比較適合三角關(guān)系較多的網(wǎng)絡(luò)。

參考文獻(xiàn)：

[1] 楊博，劉大有，LIU Jiming，等.復(fù)雜網(wǎng)絡(luò)聚類方法[J].軟件學(xué)報，2009，20（1）：54-66.

[2] Santo F.Community Detection in Graphs[EB/OL].（2009-06-12）[2012-03-01].http：//arxiv.org/abs/0906.0612.（下轉(zhuǎn)第1550頁）

[3] Mucha P J，Richardson T，Macon K，et al.Community Struct- ure in time dependent， mutiscale，and multiplex networks[J].Science， 2010， 328（5980）：876-878.

[4] 林友芳，王天宇，唐銳，等.一種有效的社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法模型和算法[J].計算機(jī)研究與發(fā)展，2012，49（2）：337-345.

[5] FORTUNATO S.Community detection in graphs[J].Physics Report，2010，486（3-5）：75-174.

[6] Newman M E J，Girvan M.Finding and evaluating communit-y structure in network[J].Physical Review E，2004，69（2）：26-113.

[7] Luo Ting，Zhong Caiming，Ying Xinyang，et al.Detecting Co-Mmunity Structure Based on Edge Betweenness[EB/OL].（2011-09-15）[2012-03-02].http：//ieeexplore.ieee.org/stamp/stamp.jsp？tp=&arnumber=6019678&tag=1.

[8] 馬延妮.在線社會網(wǎng)絡(luò)團(tuán)結(jié)構(gòu)分析[D].北京：北京交通大學(xué)，2009.

[9] Han jian，Yang Bing-ru.Community structure discovery algo-rithm based on edge clustering coefficient[J]. Application Researchof Computer，2010，46（35）：86-89.

[10] Qi Luo.A new Community Structure Detection Method Based on Structural Similarity.（2012-01-02）[2012-03-02].http：//ieeexplore.ieee.org/stamp/stamp.jsp？tp=&arnumber=6128320.