摘  要： 為了快速準(zhǔn)確地對在線社會網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，提出了一種基于局部思想的社區(qū)劃分算法。該算法利用節(jié)點和社區(qū)聚集系數(shù)的性質(zhì)，結(jié)合局部模塊度將節(jié)點劃分成相對獨立的社區(qū)。算法運(yùn)行時，只需要了解與目標(biāo)節(jié)點相關(guān)的局部網(wǎng)絡(luò)信息，時間復(fù)雜度相對較低，并且也可以用來對整個在線社會網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。利用該算法分別對Zachary空手道俱樂部網(wǎng)絡(luò)和在線社會網(wǎng)絡(luò)進(jìn)行劃分實驗，得到滿意的結(jié)果。
關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò)；在線社會網(wǎng)絡(luò)；社區(qū)劃分；聚集系數(shù)；局部社區(qū)

　在線社會網(wǎng)絡(luò)是以計算機(jī)和網(wǎng)絡(luò)為中介進(jìn)行社交、聯(lián)系和協(xié)作形成人與人之間的社會網(wǎng)絡(luò)，如Facebook、人人網(wǎng)等。國內(nèi)外學(xué)者研究發(fā)現(xiàn)在線社會網(wǎng)絡(luò)具有明顯的社區(qū)結(jié)構(gòu)和小世界特性[1]，具有節(jié)點度的冪律分布特性和高聚類特性[2]。在這樣一個異常龐大復(fù)雜的系統(tǒng)中，如何按照Newman等人給出的經(jīng)典定義[3]，即社區(qū)內(nèi)部連接的緊密程度大于社區(qū)間連接的緊密程度，將在線社會網(wǎng)絡(luò)中聯(lián)系比較緊密的節(jié)點劃分成一個社區(qū)，使之成為若干個稀疏的子系統(tǒng)，具有重要的意義。對在線社會網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，可以幫助更好地了解網(wǎng)絡(luò)結(jié)構(gòu)，協(xié)調(diào)各個社區(qū)之間的關(guān)系，為信息的查詢、搜索提供更為方便快捷的途徑。
　關(guān)于社區(qū)劃分的算法已經(jīng)提出很多，如譜平分法[4-5]、GN算法[6]、Newman快速算法[7]及利用堆結(jié)構(gòu)的貪婪算法[8]等。這些算法都是從網(wǎng)絡(luò)的全局信息出發(fā)，尋找整個網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，而在線社會網(wǎng)絡(luò)是一個異常龐大、動態(tài)變化的復(fù)雜系統(tǒng)，獲得全局信息是非常困難的；同時很多時候，人們并不需要獲得整個網(wǎng)絡(luò)的社區(qū)劃分，而只關(guān)心某一個節(jié)點所在的局部社區(qū)。例如，在人人網(wǎng)中，只關(guān)心某個人所在的社區(qū)，或者是某一個特定的社區(qū)。在這種情況下，就沒有必要消耗過多的時間計算和尋找全網(wǎng)的社區(qū)結(jié)構(gòu)。近年來復(fù)雜網(wǎng)絡(luò)中運(yùn)用局部的概念來劃分社區(qū)的方法也有很多[9-11]。參考文獻(xiàn)[9]提出“局部模塊性”的概念，通過最大化局部模塊度為目標(biāo)來劃分局部社區(qū)，但單純的最大化局部模塊度難以得到正確的社區(qū)劃分，并且時間復(fù)雜度較高。參考文獻(xiàn)[10]提出一種廣度搜索方法來尋找某個節(jié)點所在的局部社區(qū)，稱為BB算法，該算法的不足之處在于它把社區(qū)整個一層鄰居節(jié)點全部加入或全部排除在社區(qū)之外。參考文獻(xiàn)[11]提出以節(jié)點度為優(yōu)先的快速局部社區(qū)劃分算法，但僅僅是通過度數(shù)較大的節(jié)點來吸引度數(shù)較小的節(jié)點并加入到它所在的社區(qū)，對于邊緣節(jié)點和度數(shù)較大的節(jié)點來說，并不能得到正確的網(wǎng)絡(luò)劃分。
　本文提出的在線社會網(wǎng)絡(luò)局部社區(qū)劃分算法，與之前提出的局部社區(qū)劃分算法相比，本質(zhì)上是一種聚類算法。由于尋找的是局部社區(qū)，所以不用計算確定網(wǎng)絡(luò)的中心節(jié)點，而是從任意初始節(jié)點開始，通過搜索它的鄰居節(jié)點，選擇符合條件的節(jié)點加入社區(qū)。算法中采用計算社區(qū)聚集系數(shù)的方法，即假如鄰居節(jié)點屬于目標(biāo)社區(qū)，比較各鄰居節(jié)點加入后的社區(qū)聚集系數(shù)，選擇使得聚集系數(shù)最大的鄰居節(jié)點加入社區(qū)，并且采用Clauset引入的局部模塊度Q對社區(qū)進(jìn)行終止判斷[9]。局部社區(qū)劃分算法只需要節(jié)點的局部信息就可以得到社區(qū)劃分，對于規(guī)模龐大的在線社會網(wǎng)絡(luò)中尋找局部社區(qū)來講，是十分快捷方便的。但是由于采用的是局部社區(qū)劃分，所以得到的社區(qū)往往是局部最優(yōu)而不是全局最優(yōu)的。若要得到整個網(wǎng)絡(luò)的社區(qū)劃分，就需要不斷迭代此算法。

　一般說來，一個具有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，社區(qū)內(nèi)部的連接密度要遠(yuǎn)遠(yuǎn)大于社區(qū)間的連接密度。因此，局部模塊度Q越大，則社區(qū)結(jié)構(gòu)越明顯。局部模塊度只需要已知節(jié)點的局部信息而不是網(wǎng)絡(luò)的全局信息，所以適用于局部社區(qū)的劃分，和Newman等人提出的全局模塊度相比[13]，可以在一定程度上降低算法的復(fù)雜度。
2 算法設(shè)計
　本文提出的局部社區(qū)劃分算法不需要確定中心節(jié)點，而是將指定節(jié)點加入結(jié)果社區(qū)，得到一個局部社區(qū)，通過計算其鄰居節(jié)點加入該社區(qū)后的社區(qū)聚集系數(shù)，選擇聚集系數(shù)最大的節(jié)點加入此社區(qū)，形成新的局部社區(qū)，繼續(xù)選擇鄰居節(jié)點，并重復(fù)計算。在將節(jié)點加入局部社區(qū)的過程中，算法重復(fù)計算社區(qū)的局部模塊度Q，直到Q值不再增大為止，此時該局部社區(qū)形成。為了降低算法的復(fù)雜度，做如下關(guān)于鄰居節(jié)點的規(guī)定：如果一個節(jié)點一半以上的鄰居節(jié)點都在結(jié)果社區(qū)中，那么不再計算社區(qū)聚集系數(shù)，將此節(jié)點直接加入社區(qū)。算法步驟如下：
?。?）初始化。對于網(wǎng)絡(luò)中每一個節(jié)點，將其保存為一個如下的線性動態(tài)鏈表，包括節(jié)點的度、節(jié)點聚集系數(shù)、社區(qū)聚集系數(shù)、鄰居節(jié)點集、局部模塊度及節(jié)點標(biāo)號（初始值為0）。如表1所示。
　（2）從指定節(jié)點開始，作為一個局部社區(qū)。搜索其鄰居節(jié)點，依次計算各鄰居節(jié)點加入此社區(qū)后社區(qū)的聚集系數(shù)Cij，選取使得Cij最大的一個節(jié)點j加入（約定若最大的Cij相等，則任選一個節(jié)點加入）；計算此時社區(qū)的局部模塊度Q，更新j的社區(qū)標(biāo)號為1；
?。?）若有節(jié)點超過一半的鄰居都在此社區(qū)中，不計算，直接加入，更新節(jié)點標(biāo)號和局部模塊度；
?。?）若節(jié)點沒有超過一半的鄰居都在此社區(qū)中，那么計算社區(qū)所有的鄰居節(jié)點的社區(qū)聚集系數(shù)，并將聚集系數(shù)取得最大的節(jié)點加入結(jié)果社區(qū)，并更新Q值和節(jié)點標(biāo)號；
　（5）當(dāng)社區(qū)的鄰居節(jié)點集使得Q值減小或者不再增加時，算法終止，局部社區(qū)形成；
（6）若需要劃分整個網(wǎng)絡(luò)，則從社區(qū)標(biāo)號為0的節(jié)點中指定一個節(jié)點，重復(fù)步驟（1）~（5），就可以得到下一個局部社區(qū)，并重復(fù)此過程，社區(qū)劃分完畢。
由以上算法得出，將社區(qū)全部劃分完畢時，本文算法的時間復(fù)雜度為O（n2），n為社區(qū)的全部節(jié)點數(shù)。當(dāng)要尋找的只是某個局部社區(qū)時，算法的時間復(fù)雜度要低于O（n2），GN分裂算法的時間復(fù)雜度為O（n3）。
3 算法示例
　下面給出一個簡單網(wǎng)絡(luò)對該算法進(jìn)行簡要的分析說明，該社區(qū)包括19個節(jié)點，37條邊，可以劃分成三個社區(qū)。如圖1所示。

　假如現(xiàn)在想要尋找19節(jié)點所在的社區(qū)。首先，選擇19節(jié)點作為初始節(jié)點，那么節(jié)點19形成一個初始社區(qū)C（S），S表示社區(qū)節(jié)點集合。此時，S={19}。19節(jié)點有4個鄰居節(jié)點N19={14，17，16，18}，分別計算各個鄰居節(jié)點加入社區(qū)C（S）后的社區(qū)聚集系數(shù)Cij，見表2，此時18節(jié)點和16節(jié)點的社區(qū)聚集系數(shù)相等。按照之前的約定，任選一個節(jié)點加入社區(qū)，如選擇18節(jié)點加入，則S={19，18}，局部模塊度Q=1/6。在社區(qū)C（S）中，現(xiàn)在的鄰居節(jié)點集為{17，16，14，15}，重新計算這4個節(jié)點加入社區(qū)C（S）后的社區(qū)聚集系數(shù)Cij，見表3，此時發(fā)現(xiàn)16節(jié)點的社區(qū)聚集系數(shù)最大，將16節(jié)點加入，則S={19，18，16}，此時Q=1/4。觀察此時的社區(qū)情況，17節(jié)點有一半的鄰居節(jié)點N17={19，18，16}在目的社區(qū)中，此時不用計算直接將17節(jié)點加入，Q=1/2。同理，加入15節(jié)點和14節(jié)點，局部模塊度Q分別為8/11和11/12，此時S={19，18，16，17，15，14}，見表4所示，表中黑色粗體部分為節(jié)點在局部社區(qū)中的鄰居節(jié)點集?，F(xiàn)在的社區(qū)還有一個鄰居節(jié)點{11}，假如現(xiàn)在{11}節(jié)點屬于這個局部社區(qū)，計算社區(qū)的局部模塊度Q，得出Q=9/12，和之前的局部模塊度相比，處于降低的趨勢（之前為11/12），此時算法終止，局部社區(qū)形成。同樣的道理，可以劃分出另外2個社區(qū)。
4 算法應(yīng)用及分析
4.1 Zachary空手道俱樂部網(wǎng)絡(luò)
　在20世紀(jì)70年代初，ZACHARY W通過觀察美國大學(xué)空手道俱樂部成員間的人際關(guān)系，并根據(jù)俱樂部成員間平時的交往狀況建立了一個網(wǎng)絡(luò)[14]。網(wǎng)絡(luò)包含34個節(jié)點、78條邊，如圖2所示。節(jié)點代表俱樂部的成員，邊代表成員間的關(guān)系。由于突發(fā)原因，俱樂部主管與校長之間因是否提高收費問題產(chǎn)生爭執(zhí)，并最終導(dǎo)致俱樂部分裂成兩部分。其中節(jié)點34和節(jié)點1分別代表了俱樂部校長和主管，白色和灰色的節(jié)點分別代表分裂后的兩個社區(qū)節(jié)點。Zachary空手道俱樂部網(wǎng)絡(luò)是用來判斷社區(qū)劃分效果的常用實驗網(wǎng)絡(luò)，用來檢驗測試算法能否準(zhǔn)確劃分網(wǎng)絡(luò)結(jié)構(gòu)。

　根據(jù)本文算法，任意選擇一個節(jié)點，如選擇13節(jié)點作為初始社區(qū)C（S）。此時13節(jié)點有兩個鄰居N13={1，4}，4節(jié)點具有更大的社區(qū)聚集系數(shù)C13，4并且加入社區(qū)后使得社區(qū)局部模塊度Q增大，所以選擇4節(jié)點加入社區(qū)。此時，S={13，4}。同樣的道理，依次加入節(jié)點{8，14，18，2，22，3，1}。此時觀察20節(jié)點共有兩個鄰居N20={1，2}在社區(qū)中，按照之前的約定，若有節(jié)點超過一半的鄰居都在此社區(qū)中，不計算，直接加入。然后進(jìn)一步加入{5，11，6}。與加入20節(jié)點同樣的道理，將節(jié)點{7，17，12}直接加入。最后搜索此時的社區(qū)鄰居節(jié)點集{34，31，9，33，28，10，32，29}，發(fā)現(xiàn)鄰居節(jié)點中沒有符合條件的節(jié)點加入社區(qū)。于是，局部社區(qū)形成。如圖2所示灰色部分節(jié)點。循環(huán)利用此算法，將網(wǎng)絡(luò)劃分成兩個社區(qū)，和初始結(jié)果一致。
  圖3表示在劃分第一個社區(qū)（灰色部分節(jié)點）的過程中，試探加入社區(qū)鄰居節(jié)點后局部模塊度Q的變化情況。其中，曲線表示的是經(jīng)過計算社區(qū)聚集系數(shù)和局部模塊度最終加入目的社區(qū)的節(jié)點{13，4，8，14，2，18，22，3，1，12，20，5，11，7，6，17}，其余部分表示經(jīng)過計算試探未能加入社區(qū)的節(jié)點。從圖中可以看出，最終加入社區(qū)的節(jié)點都使得社區(qū)的局部模塊度Q增加，直到局部模塊度不增加為止，最終形成局部社區(qū)。

4.2 在線社會網(wǎng)絡(luò)示例分析
　為驗證算法對真實在線社會網(wǎng)絡(luò)分析時的有效性和可靠性，設(shè)計了一組試驗，試驗數(shù)據(jù)集取自人人網(wǎng)，該數(shù)據(jù)集有166個節(jié)點，468條邊，網(wǎng)絡(luò)直徑為9，平均度為5.6，密度為0.034，平均聚類系數(shù)為0.322。節(jié)點代表人人網(wǎng)中的個人節(jié)點，邊表示朋友關(guān)系。由于人人網(wǎng)是非常具有影響力的大學(xué)生交友網(wǎng)站，數(shù)據(jù)集分析的對象限制于好友圈子，即這166個節(jié)點是某個人的166個朋友。從圖4中可以直觀地看出好友網(wǎng)絡(luò)已經(jīng)被劃分成5個相對獨立的子社區(qū)，這與平時對人人網(wǎng)的直觀理解相符合。而人人網(wǎng)的好友關(guān)系基本都是真實線下關(guān)系的反映，很自然可以劃分成小學(xué)同學(xué)、初中同學(xué)、高中同學(xué)、大學(xué)同學(xué)等。由于之前對數(shù)據(jù)進(jìn)行了篩選處理，即只選擇了小學(xué)同學(xué)、初中同學(xué)、高中同學(xué)、大學(xué)同學(xué)、研究生5個社區(qū)的朋友節(jié)點，劃分結(jié)果如圖4所示。

　在社區(qū)劃分的結(jié)果中，共劃分成5個社區(qū)，與之前的社區(qū)基本一致，只有少數(shù)節(jié)點被錯分（正確率為88%），但整體的劃分結(jié)果相對來說比較滿意。用GN算法對數(shù)據(jù)集進(jìn)行劃分，共得到7個社區(qū)，正確率僅為83%。利用本文算法來劃分人人網(wǎng)朋友關(guān)系數(shù)據(jù)，不僅降低了算法的復(fù)雜度，也得到了較為正確的劃分結(jié)果。
　本文基于聚集系數(shù)和局部的思想，提出了一種劃分在線社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的方法。將本文方法和目前基于全網(wǎng)的社區(qū)劃分方法相比，該方法不需要事先知道劃分的社區(qū)數(shù)目，也不需要尋找中心節(jié)點，而是從任何一個節(jié)點出發(fā)進(jìn)行社區(qū)劃分，從而降低了算法復(fù)雜度。與之前提出的一些局部社區(qū)劃分算法相比，不僅能夠適用于大規(guī)模在線社會網(wǎng)絡(luò)，得到正確的劃分結(jié)果，并且時間復(fù)雜度較低。對Zachary空手道俱樂部網(wǎng)絡(luò)和人人網(wǎng)朋友關(guān)系網(wǎng)絡(luò)的劃分結(jié)果與實際結(jié)果基本相符，說明算法是可行的。
參考文獻(xiàn)
[1] ADAMIC L A， BUYUKKOKTEN O， ADAR E. A social networkcaught in the Web[J]. First Monday， 2003，6（8）：1-22.
[2] MISLOVE A， MARCON M， GUMMADI P K， et al. Measurement andanalysis of online social networks[C]. Internet Measurement Conference， 2007.
[3] NEWMAN M E J. Detecting community structure in networks[J]. Eur Phys J B， 2004， 38：321-330.
[4] FIEDLER M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory[J]. Czechoslovak Mathematical Journal，1973，23（298）：619-633.
[5] POTHEN A， SIMON H D， LIOU K P. Partitioning sparse matrices with eigenvectors of graphs[J]. Siam Journal On Matrix Analysis And APPlieations，1990，11（3）：430-452.
[6] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks[J]. Proc Natl Acad Sci，2001.99（12）：7821-7826.
[7] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Phys Rev E，2004，69（6）：066133.
[8] CLAUSET A， NEWMAN M E J， MOORE C. Finding community structure in very large networks[J]. Phys Rev E，2004，70（6）：066111.
[9] CLAUSET A. Finding local community structure in networks[J]. Phys Rev E， 2005， 72（2）：26132-26137.
[10] BAGROW J P， BOLLT E M. A local method for detecting communities[J]. Phys Rev E， 2005， 72（4）： 046108.
[11] 解謅，汪小帆.復(fù)雜網(wǎng)絡(luò)的一種快速局部社團(tuán)劃分算法[J].計算機(jī)仿真，2007，24（11）：82-85.
[12] Wang Xutao， Chen Guanrong， Lu Hongtao. A very fast algorithm for detecting community structures in complex networks[J]. Physica， 2007， A384：667-674.
[13] NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks[J]. Phys Rev E， 2004， 69（2）：026113.
[14] ZACHARY W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research， 1977， 33（4）： 452-473.