摘 要： 為了快速準確地對在線社會網絡進行社區劃分，提出了一種基于局部思想的社區劃分算法。該算法利用節點和社區聚集系數的性質，結合局部模塊度將節點劃分成相對獨立的社區。算法運行時，只需要了解與目標節點相關的局部網絡信息，時間復雜度相對較低，并且也可以用來對整個在線社會網絡進行社區劃分。利用該算法分別對Zachary空手道俱樂部網絡和在線社會網絡進行劃分實驗，得到滿意的結果。
關鍵詞： 復雜網絡；在線社會網絡；社區劃分；聚集系數；局部社區
在線社會網絡是以計算機和網絡為中介進行社交、聯系和協作形成人與人之間的社會網絡，如Facebook、人人網等。國內外學者研究發現在線社會網絡具有明顯的社區結構和小世界特性[1]，具有節點度的冪律分布特性和高聚類特性[2]。在這樣一個異常龐大復雜的系統中，如何按照Newman等人給出的經典定義[3]，即社區內部連接的緊密程度大于社區間連接的緊密程度，將在線社會網絡中聯系比較緊密的節點劃分成一個社區，使之成為若干個稀疏的子系統，具有重要的意義。對在線社會網絡進行社區劃分，可以幫助更好地了解網絡結構，協調各個社區之間的關系，為信息的查詢、搜索提供更為方便快捷的途徑。
關于社區劃分的算法已經提出很多，如譜平分法[4-5]、GN算法[6]、Newman快速算法[7]及利用堆結構的貪婪算法[8]等。這些算法都是從網絡的全局信息出發，尋找整個網絡的社區結構，而在線社會網絡是一個異常龐大、動態變化的復雜系統，獲得全局信息是非常困難的；同時很多時候，人們并不需要獲得整個網絡的社區劃分，而只關心某一個節點所在的局部社區。例如，在人人網中，只關心某個人所在的社區，或者是某一個特定的社區。在這種情況下，就沒有必要消耗過多的時間計算和尋找全網的社區結構。近年來復雜網絡中運用局部的概念來劃分社區的方法也有很多[9-11]。參考文獻[9]提出“局部模塊性”的概念，通過最大化局部模塊度為目標來劃分局部社區，但單純的最大化局部模塊度難以得到正確的社區劃分，并且時間復雜度較高。參考文獻[10]提出一種廣度搜索方法來尋找某個節點所在的局部社區，稱為BB算法，該算法的不足之處在于它把社區整個一層鄰居節點全部加入或全部排除在社區之外。參考文獻[11]提出以節點度為優先的快速局部社區劃分算法，但僅僅是通過度數較大的節點來吸引度數較小的節點并加入到它所在的社區，對于邊緣節點和度數較大的節點來說，并不能得到正確的網絡劃分。
本文提出的在線社會網絡局部社區劃分算法，與之前提出的局部社區劃分算法相比，本質上是一種聚類算法。由于尋找的是局部社區，所以不用計算確定網絡的中心節點，而是從任意初始節點開始，通過搜索它的鄰居節點，選擇符合條件的節點加入社區。算法中采用計算社區聚集系數的方法，即假如鄰居節點屬于目標社區，比較各鄰居節點加入后的社區聚集系數，選擇使得聚集系數最大的鄰居節點加入社區，并且采用Clauset引入的局部模塊度Q對社區進行終止判斷[9]。局部社區劃分算法只需要節點的局部信息就可以得到社區劃分，對于規模龐大的在線社會網絡中尋找局部社區來講，是十分快捷方便的。但是由于采用的是局部社區劃分，所以得到的社區往往是局部最優而不是全局最優的。若要得到整個網絡的社區劃分，就需要不斷迭代此算法。
一般說來，一個具有社區結構的網絡，社區內部的連接密度要遠遠大于社區間的連接密度。因此，局部模塊度Q越大，則社區結構越明顯。局部模塊度只需要已知節點的局部信息而不是網絡的全局信息，所以適用于局部社區的劃分，和Newman等人提出的全局模塊度相比[13]，可以在一定程度上降低算法的復雜度。
2 算法設計
本文提出的局部社區劃分算法不需要確定中心節點，而是將指定節點加入結果社區，得到一個局部社區，通過計算其鄰居節點加入該社區后的社區聚集系數，選擇聚集系數最大的節點加入此社區，形成新的局部社區，繼續選擇鄰居節點，并重復計算。在將節點加入局部社區的過程中，算法重復計算社區的局部模塊度Q，直到Q值不再增大為止，此時該局部社區形成。為了降低算法的復雜度，做如下關于鄰居節點的規定：如果一個節點一半以上的鄰居節點都在結果社區中，那么不再計算社區聚集系數，將此節點直接加入社區。算法步驟如下：
（1）初始化。對于網絡中每一個節點，將其保存為一個如下的線性動態鏈表，包括節點的度、節點聚集系數、社區聚集系數、鄰居節點集、局部模塊度及節點標號（初始值為0）。如表1所示。
（2）從指定節點開始，作為一個局部社區。搜索其鄰居節點，依次計算各鄰居節點加入此社區后社區的聚集系數Cij，選取使得Cij最大的一個節點j加入（約定若最大的Cij相等，則任選一個節點加入）；計算此時社區的局部模塊度Q，更新j的社區標號為1；
（3）若有節點超過一半的鄰居都在此社區中，不計算，直接加入，更新節點標號和局部模塊度；
（4）若節點沒有超過一半的鄰居都在此社區中，那么計算社區所有的鄰居節點的社區聚集系數，并將聚集系數取得最大的節點加入結果社區，并更新Q值和節點標號；
（5）當社區的鄰居節點集使得Q值減小或者不再增加時，算法終止，局部社區形成；
（6）若需要劃分整個網絡，則從社區標號為0的節點中指定一個節點，重復步驟（1）~（5），就可以得到下一個局部社區，并重復此過程，社區劃分完畢。
由以上算法得出，將社區全部劃分完畢時，本文算法的時間復雜度為O（n2），n為社區的全部節點數。當要尋找的只是某個局部社區時，算法的時間復雜度要低于O（n2），GN分裂算法的時間復雜度為O（n3）。
3 算法示例
下面給出一個簡單網絡對該算法進行簡要的分析說明，該社區包括19個節點，37條邊，可以劃分成三個社區。如圖1所示。
假如現在想要尋找19節點所在的社區。首先，選擇19節點作為初始節點，那么節點19形成一個初始社區C（S），S表示社區節點集合。此時，S={19}。19節點有4個鄰居節點N19={14，17，16，18}，分別計算各個鄰居節點加入社區C（S）后的社區聚集系數Cij，見表2，此時18節點和16節點的社區聚集系數相等。按照之前的約定，任選一個節點加入社區，如選擇18節點加入，則S={19，18}，局部模塊度Q=1/6。在社區C（S）中，現在的鄰居節點集為{17，16，14，15}，重新計算這4個節點加入社區C（S）后的社區聚集系數Cij，見表3，此時發現16節點的社區聚集系數最大，將16節點加入，則S={19，18，16}，此時Q=1/4。觀察此時的社區情況，17節點有一半的鄰居節點N17={19，18，16}在目的社區中，此時不用計算直接將17節點加入，Q=1/2。同理，加入15節點和14節點，局部模塊度Q分別為8/11和11/12，此時S={19，18，16，17，15，14}，見表4所示，表中黑色粗體部分為節點在局部社區中的鄰居節點集。現在的社區還有一個鄰居節點{11}，假如現在{11}節點屬于這個局部社區，計算社區的局部模塊度Q，得出Q=9/12，和之前的局部模塊度相比，處于降低的趨勢（之前為11/12），此時算法終止，局部社區形成。同樣的道理，可以劃分出另外2個社區。
4 算法應用及分析
4.1 Zachary空手道俱樂部網絡
在20世紀70年代初，ZACHARY W通過觀察美國大學空手道俱樂部成員間的人際關系，并根據俱樂部成員間平時的交往狀況建立了一個網絡[14]。網絡包含34個節點、78條邊，如圖2所示。節點代表俱樂部的成員，邊代表成員間的關系。由于突發原因，俱樂部主管與校長之間因是否提高收費問題產生爭執，并最終導致俱樂部分裂成兩部分。其中節點34和節點1分別代表了俱樂部校長和主管，白色和灰色的節點分別代表分裂后的兩個社區節點。Zachary空手道俱樂部網絡是用來判斷社區劃分效果的常用實驗網絡，用來檢驗測試算法能否準確劃分網絡結構。
根據本文算法，任意選擇一個節點，如選擇13節點作為初始社區C（S）。此時13節點有兩個鄰居N13={1，4}，4節點具有更大的社區聚集系數C13，4并且加入社區后使得社區局部模塊度Q增大，所以選擇4節點加入社區。此時，S={13，4}。同樣的道理，依次加入節點{8，14，18，2，22，3，1}。此時觀察20節點共有兩個鄰居N20={1，2}在社區中，按照之前的約定，若有節點超過一半的鄰居都在此社區中，不計算，直接加入。然后進一步加入{5，11，6}。與加入20節點同樣的道理，將節點{7，17，12}直接加入。最后搜索此時的社區鄰居節點集{34，31，9，33，28，10，32，29}，發現鄰居節點中沒有符合條件的節點加入社區。于是，局部社區形成。如圖2所示灰色部分節點。循環利用此算法，將網絡劃分成兩個社區，和初始結果一致。
圖3表示在劃分第一個社區（灰色部分節點）的過程中，試探加入社區鄰居節點后局部模塊度Q的變化情況。其中，曲線表示的是經過計算社區聚集系數和局部模塊度最終加入目的社區的節點{13，4，8，14，2，18，22，3，1，12，20，5，11，7，6，17}，其余部分表示經過計算試探未能加入社區的節點。從圖中可以看出，最終加入社區的節點都使得社區的局部模塊度Q增加，直到局部模塊度不增加為止，最終形成局部社區。
4.2 在線社會網絡示例分析
為驗證算法對真實在線社會網絡分析時的有效性和可靠性，設計了一組試驗，試驗數據集取自人人網，該數據集有166個節點，468條邊，網絡直徑為9，平均度為5.6，密度為0.034，平均聚類系數為0.322。節點代表人人網中的個人節點，邊表示朋友關系。由于人人網是非常具有影響力的大學生交友網站，數據集分析的對象限制于好友圈子，即這166個節點是某個人的166個朋友。從圖4中可以直觀地看出好友網絡已經被劃分成5個相對獨立的子社區，這與平時對人人網的直觀理解相符合。而人人網的好友關系基本都是真實線下關系的反映，很自然可以劃分成小學同學、初中同學、高中同學、大學同學等。由于之前對數據進行了篩選處理，即只選擇了小學同學、初中同學、高中同學、大學同學、研究生5個社區的朋友節點，劃分結果如圖4所示。
在社區劃分的結果中，共劃分成5個社區，與之前的社區基本一致，只有少數節點被錯分（正確率為88%），但整體的劃分結果相對來說比較滿意。用GN算法對數據集進行劃分，共得到7個社區，正確率僅為83%。利用本文算法來劃分人人網朋友關系數據，不僅降低了算法的復雜度，也得到了較為正確的劃分結果。
本文基于聚集系數和局部的思想，提出了一種劃分在線社會網絡社區結構的方法。將本文方法和目前基于全網的社區劃分方法相比，該方法不需要事先知道劃分的社區數目，也不需要尋找中心節點，而是從任何一個節點出發進行社區劃分，從而降低了算法復雜度。與之前提出的一些局部社區劃分算法相比，不僅能夠適用于大規模在線社會網絡，得到正確的劃分結果，并且時間復雜度較低。對Zachary空手道俱樂部網絡和人人網朋友關系網絡的劃分結果與實際結果基本相符，說明算法是可行的。
參考文獻
[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] 解謅，汪小帆.復雜網絡的一種快速局部社團劃分算法[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.