摘  要： 發現網絡中的社團結構有助于更好地理解網絡結構和分析網絡屬性。通過定義邊的聚類系數和基于局部信息的方法，提出了一種尋找復雜網絡中社團結構的算法。該算法首先在網絡的剩余節點中尋找度最大的節點，然后利用該節點的局部信息、邊的聚類系數和凝聚的思想，得到復雜網絡的社團結構。在兩個典型網絡上的測試結果表明了該方法的可行性。
關鍵詞： 復雜網絡；社團結構；邊的聚類系數；節點的度

　近年來，復雜網絡已經成為眾多領域的關注對象。例如，萬維網、人類社會網、生物技術網絡和科學家合作關系網[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網絡的劃分，表明了該算法的可行性。

    由結果可以看出，邊C67較大，而C36較小。說明節點6和節點7具有較強的凝聚性，即這兩個節點在同一個社團內的可能性較大。
2 算法描述
　給定一個具有n個節點的無向無權網絡。首先選取度最大的節點作為社團的初始節點，通過鄰接矩陣構造該社團的鄰居集合。然后判斷該集合中節點vi與社團連接的緊密程度。如果節點vi滿足以下兩個條件之一，說明vi與該社團連接緊密，將該點加入到社團中去，更新社團及其鄰居集合。
　(1)vi有不小于一半的鄰居節點在社團中；
　(2)在與社團相連的所有邊中，節點vi的一條邊eij的聚類系數在這些邊中是最大的，并且vi的其他邊的聚類系數小于該邊的聚類系數。
重復這個過程，直到社團的鄰居節點中沒有節點能夠加入社團，標記所得到的社團。然后從其余節點中重復　上述過程，直到整個網絡劃分完畢。
　具體算法如下：

　首先選取網絡中度最大的節點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條邊組成，節點代表俱樂部的成員，邊代表成員之間的關系。

　根據本文的算法，以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. Social network 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 social and biological networks[J]. Proceedings of the  Natlional Academy Sciences of the United States of America， 2002，99(12)：7821-7826.
[9] BREIGER R L， BOORMAN S A， ARABIE P. An algorithm for cluster relations data with applications to 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.