基于局部信息的復雜網絡社團結構發現算法＊

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

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

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

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

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

本文通過定義邊的聚類系數，提出了基于節點局部信息的社團發現算法。該方法通過不斷地計算局部邊的聚類系數，并利用凝聚算法的思想得到了網絡的社團結構。通過對三個社團網絡和Zachary網絡的劃分，表明了該算法的可行性。

1 預備知識

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

節點 i的聚類系數 Xi為[6]：

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

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

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

以圖1所示的簡單網絡為例，計算邊e36和e67的聚類系數。節點 3 的度 d3=4，其鄰居集合 N3={1，2，4，6}；節點 6 的度 d6=6，N6={1，3，5，7，9}； 節點 7 的度 d7=5，N7={5，6，8，9，10}。 因此， 節點 3 和節點 6 的公共鄰居集合N36={1}，節點6和節點7的公共鄰居集合N67={5，8，9}。計算邊 e36和 e67的聚類系數分別為 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 簡單網絡

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

2 算法描述

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

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

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

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

具體算法如下：

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

輸出：網絡的社團結構。

(1)初始社團 Ci為空。

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

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

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

(5)輸出結果。

3 實驗與分析

3.1 三個社團網絡

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

圖2 由19個點組成的三個社團網絡

表1 三社團網絡算法分析表

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

3.2 實例

20世紀70年代初期，ZACHARY W用了兩年的時間觀察美國一所大學空手道俱樂部成員間的相互社會關系。基于這些成員在俱樂部內部及外部的社會關系，ZACHARY W 構造了它們之間的關系網[15]，如圖 3(a)所示。整個網絡是由34個節點和78條邊組成，節點代表俱樂部的成員，邊代表成員之間的關系。

圖3 空手道俱樂部內部成員的關系網絡

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

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

[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，等.復雜網絡聚類算法[J].軟件學報，2009，20(1)：54-56.

[6]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

[7]王立敏，高學東，馬紅權.基于最大節點接近度的局部社團結構探測算法[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]劉紹海，劉青昆，謝福鼎，等.復雜網絡基于局部模塊度的社團劃分方法[J].計算機工程與設計，2009，3(20)：4708-4714.

[14]解亻芻，汪小帆.復雜網絡的一種快速局部社團劃分算法[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.