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

　近年來，復(fù)雜網(wǎng)絡(luò)已經(jīng)成為眾多領(lǐng)域的關(guān)注對象。例如，萬維網(wǎng)、人類社會網(wǎng)、生物技術(shù)網(wǎng)絡(luò)和科學(xué)家合作關(guān)系網(wǎng)[1-4]等。復(fù)雜網(wǎng)絡(luò)已成為當(dāng)前最重要的多學(xué)科交叉研究領(lǐng)域之一[5]。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個重要特性，它把網(wǎng)絡(luò)中的點(diǎn)分到不同的“組”或“團(tuán)”之中。其中社團(tuán)內(nèi)部節(jié)點(diǎn)連接比較稠密，但是社團(tuán)之間節(jié)點(diǎn)連接則比較稀疏[6]。發(fā)現(xiàn)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，對于了解網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)性質(zhì)具有非常重要的意義[7]。
　復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(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ò)進(jìn)行劃分。而Concor算法則是利用對相關(guān)系數(shù)的重復(fù)迭代產(chǎn)生一個相關(guān)系數(shù)矩陣，進(jìn)而對網(wǎng)絡(luò)進(jìn)行聚類。圖形分割中比較著名的方法是基于貪婪方法的Kernighan-Lin算法[10]和基于Laplace圖特征值譜平分法[11]。Kernighan-Lin算法是一種基于貪婪思想的社團(tuán)發(fā)現(xiàn)方法，該方法可以把一個復(fù)雜網(wǎng)絡(luò)劃分為兩個大小已知的社團(tuán)。譜平分法是利用網(wǎng)絡(luò)Laplace矩陣的特征值近似相等的原理進(jìn)行社團(tuán)結(jié)構(gòu)劃分。Zhang等人在2010年提出了一種復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的模糊分析方法[12]。該方法利用節(jié)點(diǎn)與社團(tuán)核連接的緊密程度，判斷將節(jié)點(diǎn)并入某個社團(tuán)核中，從而實(shí)現(xiàn)了發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)的目的。
　一般來說，使用網(wǎng)絡(luò)中的整體信息來劃分網(wǎng)絡(luò)得到的精度較高，但時間復(fù)雜度往往也很高；而利用局部信息劃分網(wǎng)絡(luò)，雖然可以得到較低的時間復(fù)雜度[13]，但劃分精度往往不夠理想。因此，如何利用局部信息而又能得到比較好的劃分結(jié)果，是一個十分值得研究的問題。
本文通過定義邊的聚類系數(shù)，提出了基于節(jié)點(diǎn)局部信息的社團(tuán)發(fā)現(xiàn)算法。該方法通過不斷地計(jì)算局部邊的聚類系數(shù)，并利用凝聚算法的思想得到了網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。通過對三個社團(tuán)網(wǎng)絡(luò)和Zachary網(wǎng)絡(luò)的劃分，表明了該算法的可行性。

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

　首先選取網(wǎng)絡(luò)中度最大的節(jié)點(diǎn)7作為社團(tuán)C1的初始節(jié)點(diǎn)，然后判斷社團(tuán)C1的鄰居集合{3，4，5，6，8}是否有點(diǎn)可以加入。發(fā)現(xiàn)節(jié)點(diǎn)6的度數(shù)值為2，并且有一條邊與社團(tuán)C1相連，因此有不小于一半的節(jié)點(diǎn)與社團(tuán)C1相連符合算法條件(1)，所以可以將節(jié)點(diǎn)6加入到社團(tuán)C1中去，得到社團(tuán)C1的鄰居集合為{3，4，5，8}。經(jīng)計(jì)算發(fā)現(xiàn)，與社團(tuán)C1相連的邊聚類系數(shù)中e74=0.400 0，是所有與社團(tuán)相連的邊中聚類系數(shù)最大的。但是與節(jié)點(diǎn)4相連的邊中聚類系數(shù)最大的是邊e42，然而節(jié)點(diǎn)2不在社團(tuán)C1中，不符合算法條件(2)，因此不能將節(jié)點(diǎn)4加入到社團(tuán)中去。觀察到社團(tuán)C1的鄰居集合中節(jié)點(diǎn)5的度數(shù)值為4，與社團(tuán)C1相連的邊數(shù)為2，符合算法條件(1)，因此可將節(jié)點(diǎn)5加入到社團(tuán)C1中去，此時社團(tuán)C1的鄰居集合為{2，3，4，8}。發(fā)現(xiàn)與社團(tuán)C1相連的邊中還是e74的聚類系數(shù)最大，并且e42是節(jié)點(diǎn)4聚類系數(shù)最大的邊，節(jié)點(diǎn)2不在社團(tuán)C1內(nèi)，故節(jié)點(diǎn)4不能加入社團(tuán)C1。但是社團(tuán)C1的鄰居集合中節(jié)點(diǎn)4的度數(shù)值為4，與社團(tuán)C1相連的邊數(shù)為2，符合算法條件(1)，故將節(jié)點(diǎn)4加入到社團(tuán)中去，則更新社團(tuán)的鄰居集合為{2，3，8}。經(jīng)計(jì)算可知，e42=0.500 0是與社團(tuán)C1相連的聚類系數(shù)中最大的，而節(jié)點(diǎn)2的聚類系數(shù)最大的邊是e23而非e24，因此不能將節(jié)點(diǎn)2加入到社團(tuán)C1中。然而在更新后的社團(tuán)鄰居集合中，節(jié)點(diǎn)2和節(jié)點(diǎn)3的度數(shù)值都為4，并且都有兩條邊與社團(tuán)C1相連，符合算法條件(1)，因此將節(jié)點(diǎn)2和節(jié)點(diǎn)3加入到社團(tuán)C1中，則社團(tuán)的鄰居集合變?yōu)閧1，8}。此時得出與社團(tuán)C1相連的邊中聚類系數(shù)最大的是e21=0.333 3，而且節(jié)點(diǎn)1的聚類系數(shù)最大的邊也是e21，符合算法條件(2)，所以將節(jié)點(diǎn)1加入到社團(tuán)C1中去，更新社團(tuán)的鄰居集合為{8}，發(fā)現(xiàn)節(jié)點(diǎn)8的度數(shù)值為5，與社團(tuán)C1有一條邊相連，不符合算法條件(1)，而且節(jié)點(diǎn)8與社團(tuán)C1的聚類系數(shù)為0，小于其他邊的聚類系數(shù)，亦不符合算法條件(2)，因此不能將節(jié)點(diǎn)8加入到社團(tuán)C1中去。此時鄰居集合中沒有其他節(jié)點(diǎn)可以再加入到社團(tuán)C1中去，該社團(tuán)發(fā)現(xiàn)完畢。將社團(tuán)C1從網(wǎng)絡(luò)中移除，鄰居集合清空。同理，分析剩余網(wǎng)絡(luò)，分別得到社團(tuán)C2和社團(tuán)C3，這時對應(yīng)的結(jié)構(gòu)被認(rèn)為是網(wǎng)絡(luò)的實(shí)際社團(tuán)結(jié)構(gòu)，實(shí)驗(yàn)結(jié)果與原圖一致。
3.2 實(shí)例
　20世紀(jì)70年代初期，ZACHARY W用了兩年的時間觀察美國一所大學(xué)空手道俱樂部成員間的相互社會關(guān)系。基于這些成員在俱樂部內(nèi)部及外部的社會關(guān)系，ZACHARY W構(gòu)造了它們之間的關(guān)系網(wǎng)[15]，如圖3(a)所示。整個網(wǎng)絡(luò)是由34個節(jié)點(diǎn)和78條邊組成，節(jié)點(diǎn)代表俱樂部的成員，邊代表成員之間的關(guān)系。

　根據(jù)本文的算法，以Zachary網(wǎng)絡(luò)為例，Zachary網(wǎng)絡(luò)進(jìn)行劃分。由于篇幅有限，以第一社團(tuán)為例分析該算法。首先選取當(dāng)前網(wǎng)絡(luò)中度最大的節(jié)點(diǎn)34作為社團(tuán)C1的初始節(jié)點(diǎn)，得到社團(tuán)C1的鄰居集合為{9，10，14，15，16，19，20， 21，23，24，27，28，29，30，31，32，33}。根據(jù)算法條件(1)將節(jié)點(diǎn)10、15、16、19、21、23和27號節(jié)點(diǎn)加入到社團(tuán)C1中，更新后社團(tuán)的鄰居節(jié)點(diǎn)為{9，14，20，24，28， 29，30，31，32，33}。查找到社團(tuán)C1的最大聚類系數(shù)為e34，33=0.588 2，發(fā)現(xiàn)該聚類系數(shù)同時是節(jié)點(diǎn)33的最大的邊聚類系數(shù)，因此將節(jié)點(diǎn)33加入到社團(tuán)C1中去，社團(tuán)C1的鄰居節(jié)點(diǎn)變?yōu)閧9，14，20，24，28，29，30，31，32}。根據(jù)算法條件(1)可以將節(jié)點(diǎn)30和31加入到社團(tuán)C1中去，然后更新鄰居節(jié)點(diǎn){9，14，20，24，28，29，32}，再根據(jù)算法條件(2)，得到最大聚類系數(shù)e30，24=0.400 0，判斷可以將節(jié)點(diǎn)24加入到社團(tuán)C1中去，則社團(tuán)C1的鄰居集合變?yōu)閧9，14，20，26，28，29，32}。接下來根據(jù)算法條件(1)，將節(jié)點(diǎn)9和28加入到社團(tuán)C1中，更新鄰居結(jié)合為{1，3，14，20，25，26，29，32}。計(jì)算發(fā)現(xiàn)最大聚類系數(shù)e93=0.181 8，但是e93不是節(jié)點(diǎn)3聚類系數(shù)最大的邊，故不能將節(jié)點(diǎn)3加入到社團(tuán)C1中去。然后根據(jù)算法條件(1)可陸續(xù)將節(jié)點(diǎn)29、32、25和26號節(jié)點(diǎn)加入到社團(tuán)C1中去。更新鄰居集合為{1，3，14，20}，發(fā)現(xiàn)其他鄰居節(jié)點(diǎn)不能再加入到社團(tuán)C1中，至此社團(tuán)C1發(fā)現(xiàn)完畢。將社團(tuán)C1從網(wǎng)絡(luò)中移除，并且清空鄰居集合。同理對剩余網(wǎng)絡(luò)進(jìn)行判斷，實(shí)驗(yàn)結(jié)果將網(wǎng)絡(luò)劃分為三個社團(tuán)，如圖3(b)所示。
　通過定義邊的聚類系數(shù)，本文提出一個基于局部信息的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法。從網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊出發(fā)，通過不斷計(jì)算邊的聚類系數(shù)進(jìn)行節(jié)點(diǎn)合并。由于該算法是基于局部信息的，所以降低了時間復(fù)雜度。同時利用邊聚類系數(shù)能夠處理很多易混淆的節(jié)點(diǎn)，這樣既節(jié)省了大量的計(jì)算時間又提高了計(jì)算的精度。通過對算法進(jìn)行測試，實(shí)驗(yàn)結(jié)果證明了該方法的可行性和有效性。
參考文獻(xiàn)
[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，等.復(fù)雜網(wǎng)絡(luò)聚類算法[J].軟件學(xué)報(bào)，2009，20(1)：54-56.
[6] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.
[7] 王立敏，高學(xué)東，馬紅權(quán).基于最大節(jié)點(diǎn)接近度的局部社團(tuán)結(jié)構(gòu)探測算法[J].計(jì)算機(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] 劉紹海，劉青昆，謝福鼎，等.復(fù)雜網(wǎng)絡(luò)基于局部模塊度的社團(tuán)劃分方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，3(20)：4708-4714.
[14] 解亻芻 ，汪小帆.復(fù)雜網(wǎng)絡(luò)的一種快速局部社團(tuán)劃分算法[J].計(jì)算機(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.