基于局部信息的復雜網(wǎng)絡(luò)社團結(jié)構(gòu)發(fā)現(xiàn)算法＊

趙曉慧 ，劉 微 ，謝鳳宏 ，趙鳳霞

(1.遼寧師范大學 計算機與信息技術(shù)學院，遼寧 大連 116081；2.秦皇島職業(yè)技術(shù)學院 信息工程系，河北 秦皇島 066100)

近年來，復雜網(wǎng)絡(luò)已經(jīng)成為眾多領(lǐng)域的關(guān)注對象。例如，萬維網(wǎng)、人類社會網(wǎng)、生物技術(shù)網(wǎng)絡(luò)和科學家合作關(guān)系網(wǎng)[1-4]等。復雜網(wǎng)絡(luò)已成為當前最重要的多學科交叉研究領(lǐng)域之一[5]。社團結(jié)構(gòu)是復雜網(wǎng)絡(luò)的一個重要特性，它把網(wǎng)絡(luò)中的點分到不同的“組”或“團”之中。其中社團內(nèi)部節(jié)點連接比較稠密，但是社團之間節(jié)點連接則比較稀疏[6]。發(fā)現(xiàn)網(wǎng)絡(luò)中的社團結(jié)構(gòu)，對于了解網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)性質(zhì)具有非常重要的意義[7]。

復雜網(wǎng)絡(luò)中社團結(jié)構(gòu)的發(fā)現(xiàn)方法，根據(jù)向網(wǎng)絡(luò)中添加邊還是刪除邊，可以分為凝聚方法和分裂方法。具有代表性的是GIRVAN和NEWMAN提出的基于邊介數(shù)的GN分裂算法[8]和 BREIGER提出的 Concor算法[9]。GN算法是通過不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊對網(wǎng)絡(luò)進行劃分。而Concor算法則是利用對相關(guān)系數(shù)的重復迭代產(chǎn)生一個相關(guān)系數(shù)矩陣，進而對網(wǎng)絡(luò)進行聚類。圖形分割中比較著名的方法是基于貪婪方法的Kernighan-Lin算法[10]和基于Laplace圖特征值譜平分法[11]。Kernighan-Lin算法是一種基于貪婪思想的社團發(fā)現(xiàn)方法，該方法可以把一個復雜網(wǎng)絡(luò)劃分為兩個大小已知的社團。譜平分法是利用網(wǎng)絡(luò)Laplace矩陣的特征值近似相等的原理進行社團結(jié)構(gòu)劃分。Zhang等人在2010年提出了一種復雜網(wǎng)絡(luò)中社團結(jié)構(gòu)的模糊分析方法[12]。該方法利用節(jié)點與社團核連接的緊密程度，判斷將節(jié)點并入某個社團核中，從而實現(xiàn)了發(fā)現(xiàn)社團結(jié)構(gòu)的目的。

一般來說，使用網(wǎng)絡(luò)中的整體信息來劃分網(wǎng)絡(luò)得到的精度較高，但時間復雜度往往也很高；而利用局部信息劃分網(wǎng)絡(luò)，雖然可以得到較低的時間復雜度[13]，但劃分精度往往不夠理想。因此，如何利用局部信息而又能得到比較好的劃分結(jié)果，是一個十分值得研究的問題。

本文通過定義邊的聚類系數(shù)，提出了基于節(jié)點局部信息的社團發(fā)現(xiàn)算法。該方法通過不斷地計算局部邊的聚類系數(shù)，并利用凝聚算法的思想得到了網(wǎng)絡(luò)的社團結(jié)構(gòu)。通過對三個社團網(wǎng)絡(luò)和Zachary網(wǎng)絡(luò)的劃分，表明了該算法的可行性。

1 預(yù)備知識

給定一個具有n個節(jié)點的無向無權(quán)網(wǎng)絡(luò)G=＜V，E＞，其 中 ，V={vi|i=1…n}，E={(vi，vj)|vi，vj∈V}。 A 是 G 的 鄰接矩陣，其中，若 i、j兩節(jié)點有邊相連，則 aij=1；否則，aij=0。Ni={j|aij=1}表示節(jié)點 i的鄰居集合，用 di表示節(jié)點i的度。

節(jié)點 i的聚類系數(shù) Xi為[6]：

其中，Si表示di個節(jié)點之間實際存在的邊的集合，(di(di-1)/2)表示在di個節(jié)點之間最多可能存在的邊數(shù)。從幾何上看，節(jié)點i的聚類系數(shù)Xi表示包含節(jié)點 i在內(nèi)的實際的三角形數(shù)量和包含節(jié)點i在內(nèi)的可能存在的三角形數(shù)量之比。如果aij=1，那么可以定義邊eij的聚類系數(shù) Cij為：

其中，Nij=Ni∩Nj，表示節(jié)點i和j的公共鄰居集合[14]，|Nij|表示以eij為邊組成的實際三角形的數(shù)量，(di+dj-|Nij|-2)表示包含節(jié)點i和j在內(nèi)的可能存在的三角形數(shù)量。

邊的聚類系數(shù)表示邊所連接的兩個節(jié)點的連接強度，值越大表明這兩個節(jié)點在同一個社團的可能性越大。 顯然，0≤Cij≤1。

以圖1所示的簡單網(wǎng)絡(luò)為例，計算邊e36和e67的聚類系數(shù)。節(jié)點 3 的度 d3=4，其鄰居集合 N3={1，2，4，6}；節(jié)點 6 的度 d6=6，N6={1，3，5，7，9}； 節(jié)點 7 的度 d7=5，N7={5，6，8，9，10}。 因此， 節(jié)點 3 和節(jié)點 6 的公共鄰居集合N36={1}，節(jié)點6和節(jié)點7的公共鄰居集合N67={5，8，9}。計算邊 e36和 e67的聚類系數(shù)分別為 C36=|N36|/(d3+d6-|N36|-2)=1/(5+6-1-2)=1/9，C67=|N67|/(d7+d6-|N67|-2)=3/(5+6-3-2)=1/2。

圖1 簡單網(wǎng)絡(luò)

由結(jié)果可以看出，邊C67較大，而C36較小。說明節(jié)點6和節(jié)點7具有較強的凝聚性，即這兩個節(jié)點在同一個社團內(nèi)的可能性較大。

2 算法描述

給定一個具有n個節(jié)點的無向無權(quán)網(wǎng)絡(luò)。首先選取度最大的節(jié)點作為社團的初始節(jié)點，通過鄰接矩陣構(gòu)造該社團的鄰居集合。然后判斷該集合中節(jié)點vi與社團連接的緊密程度。如果節(jié)點vi滿足以下兩個條件之一，說明vi與該社團連接緊密，將該點加入到社團中去，更新社團及其鄰居集合。

(1)vi有不小于一半的鄰居節(jié)點在社團中；

(2)在與社團相連的所有邊中，節(jié)點vi的一條邊eij的聚類系數(shù)在這些邊中是最大的，并且vi的其他邊的聚類系數(shù)小于該邊的聚類系數(shù)。

重復這個過程，直到社團的鄰居節(jié)點中沒有節(jié)點能夠加入社團，標記所得到的社團。然后從其余節(jié)點中重復上述過程，直到整個網(wǎng)絡(luò)劃分完畢。

具體算法如下：

輸入：一個無向網(wǎng)絡(luò)，G=＜V，E＞，其中，V={vi|i=1…n}，E={(vi，vj)|vi，vj∈V}。

輸出：網(wǎng)絡(luò)的社團結(jié)構(gòu)。

(1)初始社團 Ci為空。

(2)選取剩余網(wǎng)絡(luò)中度最大的節(jié)點vm作為社團Ci的初始節(jié)點。令Ci=Ci+vm，V=V-vm，并建立社團Ci的鄰居集合。

(3)計算社團 Ci的鄰居集合，計算與社團 Ci相連的所有邊的聚類系數(shù)，找到聚類系數(shù)最大的邊所對應(yīng)的節(jié)點vn，計算節(jié)點vn其他邊的聚類系數(shù)。如果節(jié)點vn滿足條 件(1)或(2)，則 將 該 節(jié) 點 并 入 社 團 Ci， 令 Ci=Ci+vn、V=V-vn，更新社團 Ci的鄰居集合。

(4)重復步驟(3)，直到 Ci的鄰居集合中不再有新的節(jié)點加入到社團中為止，輸出社團Ci。令V=V-Ci，若V不空，令 i=i+1，返回步驟(1)。

(5)輸出結(jié)果。

3 實驗與分析

3.1 三個社團網(wǎng)絡(luò)

下面以計算機生成的三個社團網(wǎng)絡(luò)為例，如圖2所示，該網(wǎng)絡(luò)包含19個節(jié)點和37條邊。利用本文提出的算法詳細分析該網(wǎng)絡(luò)，結(jié)果如表1所示。表中①表示該節(jié)點具有當前網(wǎng)絡(luò)中最大的度數(shù)值；②表示該節(jié)點有不小于一半的鄰居節(jié)點與上一節(jié)點所在的社團相連；③表示該節(jié)點是上一節(jié)點所在社團的鄰居并集中具有最大聚類系數(shù)的節(jié)點，并且該點的其他聚類系數(shù)小于該點與社團連接的邊的聚類系數(shù)。③中內(nèi)容指的是聚類系數(shù)值(具有最大聚類系數(shù)的邊)。

圖2 由19個點組成的三個社團網(wǎng)絡(luò)

表1 三社團網(wǎng)絡(luò)算法分析表

首先選取網(wǎng)絡(luò)中度最大的節(jié)點7作為社團C1的初始節(jié)點，然后判斷社團 C1的鄰居集合{3，4，5，6，8}是否有點可以加入。發(fā)現(xiàn)節(jié)點6的度數(shù)值為2，并且有一條邊與社團C1相連，因此有不小于一半的節(jié)點與社團C1相連符合算法條件(1)，所以可以將節(jié)點6加入到社團C1中去，得到社團 C1的鄰居集合為{3，4，5，8}。經(jīng)計算發(fā)現(xiàn)，與社團C1相連的邊聚類系數(shù)中 e74=0.400 0，是所有與社團相連的邊中聚類系數(shù)最大的。但是與節(jié)點4相連的邊中聚類系數(shù)最大的是邊e42，然而節(jié)點2不在社團C1中，不符合算法條件(2)，因此不能將節(jié)點4加入到社團中去。觀察到社團C1的鄰居集合中節(jié)點5的度數(shù)值為 4，與社團 C1相連的邊數(shù)為 2，符合算法條件(1)，因此可將節(jié)點5加入到社團C1中去，此時社團C1的鄰居集合為 {2，3，4，8}。發(fā)現(xiàn)與社團 C1相連的邊中還是 e74的聚類系數(shù)最大，并且e42是節(jié)點4聚類系數(shù)最大的邊，節(jié)點2不在社團C1內(nèi)，故節(jié)點4不能加入社團C1。但是社團C1的鄰居集合中節(jié)點4的度數(shù)值為4，與社團C1相連的邊數(shù)為 2，符合算法條件(1)，故將節(jié)點 4加入到社團中去，則更新社團的鄰居集合為{2，3，8}。經(jīng)計算可知，e42=0.500 0是與社團C1相連的聚類系數(shù)中最大的，而節(jié)點2的聚類系數(shù)最大的邊是e23而非e24，因此不能將節(jié)點2加入到社團C1中。然而在更新后的社團鄰居集合中，節(jié)點 2和節(jié)點3的度數(shù)值都為4，并且都有兩條邊與社團C1相連，符合算法條件(1)，因此將節(jié)點2和節(jié)點3加入到社團C1中，則社團的鄰居集合變?yōu)閧1，8}。此時得出與社團C1相連的邊中聚類系數(shù)最大的是e21=0.333 3，而且節(jié)點1的聚類系數(shù)最大的邊也是e21，符合算法條件(2)，所以將節(jié)點 1加入到社團 C1中去，更新社團的鄰居集合為{8}，發(fā)現(xiàn)節(jié)點8的度數(shù)值為5，與社團 C1有一條邊相連，不符合算法條件(1)，而且節(jié)點8與社團C1的聚類系數(shù)為0，小于其他邊的聚類系數(shù)，亦不符合算法條件(2)，因此不能將節(jié)點8加入到社團C1中去。此時鄰居集合中沒有其他節(jié)點可以再加入到社團C1中去，該社團發(fā)現(xiàn)完畢。將社團C1從網(wǎng)絡(luò)中移除，鄰居集合清空。同理，分析剩余網(wǎng)絡(luò)，分別得到社團C2和社團C3，這時對應(yīng)的結(jié)構(gòu)被認為是網(wǎng)絡(luò)的實際社團結(jié)構(gòu)，實驗結(jié)果與原圖一致。

3.2 實例

20世紀70年代初期，ZACHARY W用了兩年的時間觀察美國一所大學空手道俱樂部成員間的相互社會關(guān)系?；谶@些成員在俱樂部內(nèi)部及外部的社會關(guān)系，ZACHARY W 構(gòu)造了它們之間的關(guān)系網(wǎng)[15]，如圖 3(a)所示。整個網(wǎng)絡(luò)是由34個節(jié)點和78條邊組成，節(jié)點代表俱樂部的成員，邊代表成員之間的關(guān)系。

圖3 空手道俱樂部內(nèi)部成員的關(guān)系網(wǎng)絡(luò)

根據(jù)本文的算法，以 Zachary網(wǎng)絡(luò)為例，Zachary網(wǎng)絡(luò)進行劃分。由于篇幅有限，以第一社團為例分析該算法。首先選取當前網(wǎng)絡(luò)中度最大的節(jié)點34作為社團C1的初始節(jié)點，得到社團 C1的鄰居集合為{9，10，14，15，16，19，20，21，23，24，27，28，29，30，31，32，33}。 根據(jù)算法條件(1)將節(jié)點 10、15、16、19、21、23 和 27 號節(jié)點加入到社團 C1中 ， 更 新 后 社 團 的 鄰 居 節(jié) 點 為 {9，14，20，24，28，29，30，31，32，33}。 查找到社團 C1的最大聚類系數(shù)為e34，33=0.588 2，發(fā)現(xiàn)該聚類系數(shù)同時是節(jié)點 33的最大的邊聚類系數(shù)，因此將節(jié)點33加入到社團C1中去，社團C1的鄰居節(jié)點變?yōu)閧9，14，20，24，28，29，30，31，32}。根據(jù)算法條件 (1)可以將節(jié)點30和31加入到社團C1中去，然后更新鄰居節(jié)點{9，14，20，24，28，29，32}，再根據(jù)算法條件(2)，得到最大聚類系數(shù) e30，24=0.400 0，判斷可以將節(jié)點24加入到社團C1中去，則社團C1的鄰居集合變?yōu)?{9，14，20，26，28，29，32}。 接下來根據(jù) 算法條件(1)，將節(jié)點 9和 28加入到社團 C1中，更新鄰居結(jié)合為{1，3，14，20，25，26，29，32}。 計 算 發(fā) 現(xiàn) 最 大 聚 類 系 數(shù)e93=0.181 8，但是e93不是節(jié)點3聚類系數(shù)最大的邊，故不能將節(jié)點3加入到社團C1中去。然后根據(jù)算法條件(1)可陸續(xù)將節(jié)點29、32、25和26號節(jié)點加入到社團C1中去。更新鄰居集合為{1，3，14，20}，發(fā)現(xiàn)其他鄰居節(jié)點不能再加入到社團C1中，至此社團C1發(fā)現(xiàn)完畢。將社團C1從網(wǎng)絡(luò)中移除，并且清空鄰居集合。同理對剩余網(wǎng)絡(luò)進行判斷，實驗結(jié)果將網(wǎng)絡(luò)劃分為三個社團，如圖3(b)所示。

通過定義邊的聚類系數(shù)，本文提出一個基于局部信息的社團結(jié)構(gòu)發(fā)現(xiàn)算法。從網(wǎng)絡(luò)中的節(jié)點和邊出發(fā)，通過不斷計算邊的聚類系數(shù)進行節(jié)點合并。由于該算法是基于局部信息的，所以降低了時間復雜度。同時利用邊聚類系數(shù)能夠處理很多易混淆的節(jié)點，這樣既節(jié)省了大量的計算時間又提高了計算的精度。通過對算法進行測試，實驗結(jié)果證明了該方法的可行性和有效性。

[1]ALBERT R， JEONG H， BARABáSI A L.Diameter of the world-wide Web[J].Nature(London)， 1999， 401：130–131.

[2]SCOOT J.Socialnetwork analysis： a handbook [M].London： Sage Publications， 2002.

[3]HOLME P， HUSS M， JEONG H.Subnetwork hierarchies of biochemical pathways[J]， Bioinformatics， 2003， 19：532–538.

[4]NEWMAN M E J.Scientific collaboration networks[J].Physical.Review E， 2001， 64(1).

[5]楊博，劉大有，Liu Jiming，等.復雜網(wǎng)絡(luò)聚類算法[J].軟件學報，2009，20(1)：54-56.

[6]汪小帆，李翔，陳關(guān)榮.復雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學出版社，2006.

[7]王立敏，高學東，馬紅權(quán).基于最大節(jié)點接近度的局部社團結(jié)構(gòu)探測算法[J].計算機工程，2010，36(1)：25-29.

[8]GIRVAN M，NEWMAN M E J.Community structure in socialand biologicalnetworks [J].Proceedings ofthe Natlional Academy Sciences of the United States of America， 2002，99(12)：7821-7826.

[9]BREIGER R L， BOORMAN SA， ARABIE P.An algorithm forclusterrelationsdatawith applicationsto social network analysis and comparison with multidimensional scaling[J].Journal of Mathematical Psychology， 1975，12：328-383.

[10]KERNIGHAN B W，LIN S.A efficient beuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970， 49：291-307.

[11]POTHEN A，SIMON H，LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM J Matrix Anal Appl，1990，11(3)： 430-452.

[12]Zhang Dawei， Xie Fuding， 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.

[13]劉紹海，劉青昆，謝福鼎，等.復雜網(wǎng)絡(luò)基于局部模塊度的社團劃分方法[J].計算機工程與設(shè)計，2009，3(20)：4708-4714.

[14]解亻芻，汪小帆.復雜網(wǎng)絡(luò)的一種快速局部社團劃分算法[J].計算機仿真，2007，24(11)：82-85.

[15]ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research， 1977， 33：452-473.