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

羅 浪，張紹武，陳 韜

（西北工業(yè)大學(xué) 自動化學(xué)院，陜西 西安 710072）

近年來，復(fù)雜網(wǎng)絡(luò)已在計算機科學(xué)、生物學(xué)、統(tǒng)計物理學(xué)、社會學(xué)和經(jīng)濟學(xué)等領(lǐng)域在內(nèi)的廣泛關(guān)注，并且逐步體現(xiàn)出了一定的應(yīng)用價值。復(fù)雜網(wǎng)絡(luò)最重要、最普遍的拓?fù)浣Y(jié)構(gòu)屬性之一是社團結(jié)構(gòu)，社團結(jié)構(gòu)是指在復(fù)雜網(wǎng)絡(luò)中那些節(jié)點之間連接非常緊密的小團體。團體內(nèi)節(jié)點連接緊密，團間連接稀疏。網(wǎng)絡(luò)社團結(jié)構(gòu)的發(fā)現(xiàn)與分析對于了解整個網(wǎng)絡(luò)結(jié)構(gòu)、特征及功能有其重要意義，且在生物學(xué)、物理學(xué)、計算機、社會學(xué)和經(jīng)濟學(xué)等領(lǐng)域發(fā)揮的重要作用[1-3]。

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

1 基本概念

1.1 共有鄰居數(shù)

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

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

1.2 稠密子團

給定一個無權(quán)無向的網(wǎng)絡(luò)G（V，E），設(shè)網(wǎng)絡(luò)中度最大的節(jié)點為 va，則 va的鄰居節(jié)點集合為 N={v1，v2，…，vk}， 集合 N中與節(jié)點va的共享鄰居數(shù)最多的節(jié)點集合為 N′={v1，…，vr}，次多的節(jié)點集合為N″={v1，…，vo}，則稠密子團定義為Cd={vx=（{va}∪N′∪N″）}。

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

1.3 邊聚類系數(shù)

在網(wǎng)絡(luò)G=（V，E）中，假設(shè)兩個節(jié)點vi和vj有一條邊為eij，節(jié)點vi和vj在網(wǎng)絡(luò)中的共有相鄰節(jié)點vk，則有相鄰邊 eik、ejk，與eij形成一個邊數(shù)為3的閉合路徑即一個三角環(huán)。則復(fù)雜網(wǎng)絡(luò)中一條邊的邊聚類系數(shù)[7]Cij定義為

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

2 DIDE算法

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

1）稠密子團選取

Step 1取網(wǎng)絡(luò)中節(jié)點度最大的節(jié)點作為初始節(jié)點；

Step 2尋找初始節(jié)點鄰居節(jié)點v0；

Step 3計算v0與初始節(jié)點的共有鄰居數(shù)；

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

2）稠密子團擴張

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

Step 2尋找稠密子團鄰居節(jié)點vi；

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

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

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

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

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

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

3）孤立節(jié)點的加入

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

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

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

3 實驗與分析

1）計算機生成網(wǎng)絡(luò)

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

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

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

2）三社團網(wǎng)絡(luò)

三社團網(wǎng)絡(luò)是由19個節(jié)點，37條邊構(gòu)成了一個經(jīng)典的驗證網(wǎng)絡(luò)，如圖4所示。

圖4 三社團網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.4 The structure of three groups network

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

3）Zachary網(wǎng)絡(luò)

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

圖5為DIDE算法對Zachary網(wǎng)絡(luò)的社團劃分結(jié)果。圖中菱形社團的局部模塊度Q值為0.782 5；三角形社團的局部模塊度值Q為值0.708 5。

表1 五種算法對Zachary網(wǎng)絡(luò)的社團劃分結(jié)果Tab.1 The results of detecting Zachary network community by 5 algorithms

圖5 DIDE對Zachary網(wǎng)絡(luò)劃分結(jié)果圖Fig.5 Tthe result of detecting Zachary network community by DIDE

4）美國足球俱樂部網(wǎng)絡(luò)

美國足球網(wǎng)絡(luò)是美國大學(xué)生足球聯(lián)賽得出的一個復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點代表一只足球隊，邊代表兩個球隊之間進行過一場比賽，它一共包含115個節(jié)點及616條邊。聯(lián)賽中存在若干聯(lián)盟，每個節(jié)點都屬于其中一個聯(lián)盟，聯(lián)盟內(nèi)部球隊間比賽次數(shù)多于聯(lián)盟間球隊進行的比賽次數(shù)。這115支球隊共存在12個聯(lián)盟。

表2是DIDE算法與其它算法對美國足球俱樂部網(wǎng)絡(luò)社團劃分結(jié)果對比，從表2中結(jié)果表明，在分團數(shù)方面DIDE與Liu的算法分為12個團要優(yōu)于Zhang算法以及 GN、FN算法。而在正確率方面，同為12個分團數(shù)，由于DIDE算法在循環(huán)中同時加入多個節(jié)點，從而減少孤立節(jié)點，所以要比Liu算法準(zhǔn)確度更高。

DIDE算法對美國足球俱樂部網(wǎng)絡(luò)的社團劃分結(jié)果如圖6所示，表3為12個聯(lián)盟球隊編號以及每個聯(lián)盟的局部模塊度Q值。

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

在美國足球俱樂部網(wǎng)絡(luò)中，DIDE算法一共錯分了9個節(jié)點（43，59，60，64，81，83，91，98，111），由于實際原因，這些節(jié)點所代表的球隊跟外聯(lián)盟球隊比賽次數(shù)要多于聯(lián)盟內(nèi)部比賽次數(shù)導(dǎo)致了DIDE算法出現(xiàn)了一些錯分情況，但是DIDE算法仍能夠達到較高的劃分正確率。

4 結(jié) 論

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

圖6 DIDE對美國足球俱樂部網(wǎng)絡(luò)劃分結(jié)果圖Fig.6 The result of detecting American football club network community by DIDE

表3 DIDE算法得到的聯(lián)盟球隊編號及局部模塊度值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]胡健，楊炳儒.基于邊聚集系數(shù)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法[J].計算機應(yīng)用研究，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]劉微，張大為，謝福鼎，等.基于共享鄰居數(shù)的社團結(jié)構(gòu)發(fā)現(xiàn)算法[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，等.復(fù)雜網(wǎng)絡(luò)聚類算法[J].軟件學(xué)報，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]王立敏，高學(xué)東，宮雨，等.基于相對密度的社團結(jié)構(gòu)探測算法[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.