基于引力作用的可選粒度社區發現算法

董宇欣，遲闊，印桂生

（哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001）

基于引力作用的可選粒度社區發現算法

董宇欣，遲闊，印桂生

（哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001）

社區發現是復雜網絡研究中的一個重要領域，且應用廣泛，但目前已有的大多數算法都需采用社區評判函數來確定社區結構的劃分，且僅能得到一種劃分結果。引入宇宙星系模型和萬有引力定律，基于引力思想提出一種新的復雜網絡社區發現算法，為網絡中節點賦予質量并構建出社區框架，繼而利用引力作用完成社區結構劃分，并可對發現社區的粒度大小進行選擇以得到多種劃分結果，無需先驗知識及相關參數。通過真實網絡實驗驗證，并與現有的社區發現算法比較，本文提出的算法能有效且較為準確地挖掘出復雜網絡中的社區結構。

復雜網絡；可選粒度；社區發現；引力作用

復雜網絡廣泛存在于現實世界中［1］，隨著互聯網的發展，大規模在線社交網絡的出現也使得網絡結構更加趨于復雜，社區發現也變得尤為重要。社區作為網絡中一些具有某種相同屬性的節點組合，能夠更加方便、快速且準確地尋找具有相同屬性的節點，使得復雜網絡更加易于分析，且社區結構在信任機制，網絡影響力傳播，尋找惡意節點聯盟等方面也起著十分重要的作用［2］。因此如何準確和快速地在復雜網絡中發現并挖掘出社區結構，深入研究社區結構的演化過程對復雜網絡的研究和發展具有重要的推動作用。

復雜網絡的社區發現問題到目前主要有兩類劃分方法：一類基于層次聚類，利用樹圖來劃分社區；另一類基于中心聚類思想，通過聚類范圍的擴大來實現社區的擴充。Newman等最初提出了GN算法［1］，通過計算網絡中每條邊的邊介數，不斷地移除邊介數最大的邊來達到劃分社區結構的目的，算法執行后可以得到多種社區粒度不同的劃分結果，但無法確定最優的社區結構，且算法的時間復雜度過高，不適合大規模的復雜網絡。為了解決最優社區結構劃分的問題，Newman等又提出了網絡模塊度函數來作為社區劃分評判函數［3］，后來很多模塊度優化算法和優化策略被引入［4?7］，許多類似的社區評判函數也被提出［8?9］。此外還有很多不需要利用社區評判函數來幫助進行社區發現的算法也被提出，這些算法大部分基于中心聚類思想［10?11］。這些算法不需要社區評判函數來輔助進行社區發現，而是通過尋找網絡社區的核心進而完成社區結構的劃分。雖然上述算法一定程度上可以挖掘出網絡中的社區結構，且可適合應用于大型網絡，但往往僅能得到一種劃分結果，而在社區研究中可能需要對同一網絡下不同粒度的社區進行分析。

基于宇宙星系模型及萬有引力思想，本文提出了一種基于節點間引力作用的可選粒度的復雜網絡社區發現方法，將引力作用引入復雜網絡，通過為網絡中的節點賦予質量，引力搜索節點最終劃分出網絡的社區結構，并可調整所得社區的粒度大小。最后利用真實網絡對算法的準確性進行驗證。

1 宇宙星系模型的引入

在本節中，將宇宙星系模型引入到復雜網絡中，將網絡中的每一個節點映射為宇宙中的星體，為每個節點賦予相應的質量，仿照宇宙中星系結構的形成，通過節點間引力的相互作用聚類來劃分社區結構。

給定復雜網絡的無權無向圖NG＝（V，E），網絡中的節點個數為N，邊條數為M、V是節點集合，E是邊集合。此外也可以用N×N的鄰接矩陣A＝［aij］N×N來表示網絡圖，其中，對于任意vi，vj∈V，若存在eij∈E則aij＝1，否則aij＝0。節點vi的度，是節點vi與其他節點直接相連的邊數目的總和。假設網絡中存在節點集合的集合｛C1，C2，…，Cn｝，1≤n≤N，對任意i，j∈｛1，2，…，n｝，當滿足下列條件時：①Ci∈V；②Ci≠φ；.每個節點集合稱為NG的一個社區。

宇宙由數以億計的星體所組成，部分星體與臨近星體之間由于萬有引力的作用而相互運動，最終形成星系系統。相類似地，復雜網絡由大量彼此間相互聯系的網絡節點組成，社區可看成是由若干彼此間聯系更為緊密的網絡節點所組成的局部團體。本文將宇宙星系模型引入到復雜網絡中來模擬網絡結構并嘗試通過節點間相互吸引來實現社區結構的劃分，因此需要為網絡中的每個節點賦予質量。本文用圖NG來描述網絡，一個節點的度表示該節點與周圍節點的聯系密集程度，一個節點的度越大，表示該節點與周圍較多節點彼此之間相互聯系，也能從一定程度上反映該節點在社區中的重要性，因此本文選用節點度的大小作為其質量大小。

在復雜網絡中引入宇宙模型后，接下來通過引力作用來劃分社區結構。這里引入萬有引力計算公式：

式中：fij表示個體vi與vj之間的引力；G為引力常量，由于本文的研究對象均為同構網絡，因此將其設定為1；mi表示個體vi的質量；Rij表示網絡中節點vi與節點vj的拓撲距離，為了簡化計算，這里認為只有直接相連的節點間存在引力作用，因此式（1）可修改為

2 基于引力搜索的可選粒度社區發現

本文通過下列步驟來挖掘網絡中的社區：首先找到作為社區核心的Star節點，進而聚類其周圍Planet節點構建社區框架，最后通過引力作用搜索剩余的節點完成社區結構的劃分。

2.1 構建社區框架

社區框架可看作由Star節點和Planet節點組成。宇宙的一個星系中，恒星的數量可能是多個，因此假定網絡中的社區核心也不僅僅局限于一個。考慮到網絡中的部分節點因與其相聯系的節點數目較多而具有較大的中心性，部分節點因與其聯系的節點更緊密而具有較大的中心性，本文中社區核心節點選取具有上述2種中心性的節點集合。依據上文為每個節點定義的質量，從全局的角度選取具有局部極大T值和局部極大M值的節點的并集作為網絡的Star節點集合。如圖1所示。

圖1 一個網絡中的Star節點Fig.1 The Star nodes in a network

在給定的網絡NG中，節點vi的T值定義為節點vi與其鄰居節點所形成的的三角形個數與其度大小的比值，可以反映該節點在與周圍節點聯系規模條件下的聯系緊密程度。局部極大T值節點定義為：存在節點vi，i∈｛1，2，…，N｝，對任意滿足eij＝1的節點vj，都有T（vi）≥T（vj）。

節點vi的M值定義為節點vi的質量，大小等于節點度的大小。局部極大M值節點定義為：存在節點vi，i∈｛1，2，…，N｝，對任意滿足eij＝1的節點vj，都有M（vi）≥M（vj）。

接下來要對Star節點集合進行劃分來完成社區的初始化。這里有2種劃分策略：

1）將所有相連的Star節點劃入到同一個社區中，不相連的Star節點則認為其分屬于不同的社區結構，這樣最終得到的社區是粗粒度的；

2）在上一種劃分策略基礎上，再對每個社區的Star節點進一步細分，以每個具有局部極大M值的節點為細化中心，將與其相連的局部極大T值節點劃入同一個社區，同時連接到多個局部極大M值節點的局部極大T值節點劃分到收到引力大小最大的細化社區中，這樣最終得到的社區結構是細粒度的。此外，還可以僅對部分粗粒度的社區結構進行細化，一些不需要進一步細化研究的粗粒度社區繼續保留，這樣就可以得到多種不同的中間粒度的社區初始化結果。

接下來通過聚類的方法構建社區框架：將與Star節點相連的節點納入社區中，并稱這些節點為Planet。此時可能會有一個Planet節點同時與多個社區相連的情況，本文根據社區對其引力作用的大小將其劃入對其引力更大的社區中。

社區C對節點vi的引力F值定義為

式中：Fin（vi，C）表示節點vi與社區C中節點引力大小之和，即

式中：Fout（vi，C）表示節點vi與社區C外節點引力大小之和，即

對于同時與社區Ci與社區Cj相連的Planet節點，當F（vi，C）＞0時，說明了社區Ci中的節點對節點vi的引力作用大于社區Cj中的節點，就將節點vi劃入社區Ci。反之，將其劃入社區Cj。

2.2 引力搜索完成社區劃分

此時，網絡中仍然有一些節點沒有被劃分進入社區，本文利用各社區的引力關系大小搜索這些節點。同樣利用F值作為這些節點劃入相應社區的依據，當F（vi，Ci）＞0時，說明了社區Ci中的節點對節點vi的引力作用大于社區Ci外的節點，則將節點vi劃入社區Ci中。

2.3 算法步驟

算法 基于引力作用的可選粒度社區發現算法（optional granularity community detection algorithm based on gravitation）

輸入：網絡圖NG＝（V，E）輸出：NG的最終社區劃分1）計算網絡中各節點的度，并以此作為節點的質量；由式（2）來構建全網絡的引力矩陣。

2）計算每個節點的T值大小，將具有局部極大T值的節點和具有局部極大M值的節點選取出來，作為整個網絡的Star節點集合。

3）將Star節點集合中相連的Star節點初始化進入同一個社區，不相連的則初始化進入不同的社區，初始化后得到各個社區的Star節點集合。若最終社區劃分結果想獲得粗粒度社區結構，則跳轉至5）；若最終社區劃分結果想獲得細粒度或中間粒度的社區結構則跳轉至4）。

4）在各個社區的Star節點集合中，以其中具有極大M值的Star節點為中心，將與其相連的Star節點劃分進同一個細化社區，若其中有極大T值節點同時連接多個極大M值節點，則將其劃入對其引力大小更大的細化社區中。也可以僅對其中部分社區的Star節點進行上述處理，其余不做改變。

5）由各個社區的Star節點集合將與其相連的節點（Planet節點）聚類進入各個社區中。若有Planet節點同時受到多個社區的吸引，則根據式（4）將其劃入對其引力值更大的社區。

6）利用社區對節點的引力作用的大小搜索剩余節點，將其劃分進對其引力值更大的社區中，直到所有的節點都被劃分進對其引力作用最大的社區中，完成社區結構的劃分。

算法的整體時間復雜度約為O（N2）。

3 實驗分析

本文選擇3個數據集（空手道俱樂部社交網絡、海豚社會網絡、VAST通信網絡）來驗證該算法的有效性（見表1）。

表1 實驗數據集Table 1 The experimental data set

實驗所采用的對比算法是GN算法［1］，Fast算法和基于拓撲勢的社區發現算法［10］。最后將各算法劃分結果與真實網絡劃分結果進行對比。

3.1 空手道俱樂部社交網絡

該網絡是社會網絡分析的常用經典數據集，整個網絡被分成了2個社區。

在圖2中，2個社區中都僅含有一個極大M值節點（節點1和節點34），因此均無法再細化。圖2是根據局部極大T值和局部極大M值所選取的Star節點；圖3是最終得到的社區劃分結果。

GN算法在模塊度Q函數取得最大值時劃分得到了4個社區；Fast算法劃分得到了2個社區，但有節點劃分錯誤；基于拓撲勢的社區發現算法結果也有2個節點被誤分。表2是對這4種算法劃分結果的準確率的對比。3.2 海豚社會網絡

圖2 空手道俱樂部社交網絡—Star節點的選取Fig.2 Zachary's karate club—Star selected

圖3 空手道俱樂部社交網絡—最終社區劃分結果Fig.3 Zachary's karate club—The final results

表2 各算法劃分結果準確率的對比Table 2 The accuracy of the results compared

該網絡也是社會網絡分析的常用數據集，網絡初始被分成了一大一小2個社區，但通過研究者的進一步觀察，大的社區又進一步分裂成3個小社區。

圖4和圖5展示了本章所提出的算法劃分海豚社會網絡的最終社區劃分結果。

本文所提的算法得到的粗粒度社區也為2個，同時右邊社區可進一步細化為3個小的社區，與真實情形相一致，表3是對這4種算法劃分結果的準確率的對比，這里僅列出細化后的社區劃分結果。

圖4 海豚社會網絡-算法的最終社區劃分結果（粗粒度社區）Fig.4 Dolphin social network—the final results（coars?ness）

圖5 海豚社會網絡-算法的最終社區劃分結果（細粒度社區）Fig.5 Dolphin social network—the final results（fine?grit）

表3 各算法劃分結果正確率的對比Table 3 The correct rate of the results compared

3.3 VAST通信網絡

該數據集記錄了400人在10 d中的通話情況，包含10個靜態網絡快照。表4給出了數據集中各個網絡的基本信息，此數據集并未有確切的社區劃分結果。

表4 VAST數據集各網絡的信息Table 4 The information of VAST

表5展示了本章所提出的算法在粗粒度社區劃分條件下對各網絡社區的劃分結果和與GN算法的對比情況，得到的粗粒度社區劃分結果與GN算法大致相同，部分社區會劃分可得到更細粒度，但對于研究意義不大，在此不再列出。

表5 各個網絡的社區劃分結果對比Table 5 Comparision of community division results

4 結論

本文提出了基于引力作用的可選粒度復雜網絡社區發現算法。相比于目前現有的算法，本文所提出的算法具有如下優勢：

1）算法本身無需任何先驗知識和參數；

2）可根據需要劃分出不同粒度的社區結構；

3）算法的時間復雜度較低，可應用于大規模的實際網絡；

4）算法可以獲得合理且較為準確的實驗結果。

在下一步工作中，將嘗試把算法引入到重疊社區劃分和動態網絡社區演化中，并利用更大規模的網絡數據集來進行實驗。

［1］GIRVAN M，NEWMAN M E J.Community structure in so?cial and biological networks［J］.Proc of the National Acade?my of Sciences of the United States of America，2002，99（12）：7821?7826.

［2］FORTUNATO S.Community detection in graphs［J］.Phys?ics Reports，2010，486（3／5）：75?174.

［3］NEWMAN M E J，GIRVAN M.Finding and evaluating com?munity structure in networks［J］.Physical Review E，2004，69（2）：026113.

［4］LEE J，GROSS S P，LEE J.Modularity optimization by con?formational space annealing［J］.Physical Review E，2012，85（5）：056702.

［5］SHANG Ronghua，BAI Jing，JIAO Licheng，et al.Commu?nity detection based on modularity and an improved genetic algorithm［J］.Physica A：Statistical Mechanics and Its Ap?plications，2013，392（5）：1215?1231.

［6］DUCH J，ARENAS A.Community detection in complex net?works using extremal optimization［J］.Phys Rev E，2005，72（2）：027104.

［7］GUIMER R，AMARAL L A N.Functional cartography of complex metabolic networks［J］.Nature，2005，433（7028）：895?900.

［8］PIZZUTI C.A multiobjective genetic algorithm to find com?munities in complex networks［J］.IEEE Trans on Evolution?ary Computation，2012，16（3）：418?430.

［9］LI Y Y，CHEN J，LIU R C，et al.A spectral clustering?based adaptive hybrid multi?objective harmony search algorithm for community detection［C］.Proc of the CEC 2012.［S.l.］，2012：1?8.

［10］淦文燕，赫南，李德毅，等.一種基于拓撲勢的網絡社區發現方法［J］.軟件學報，2009，20（8）：2241?2254.GAN Wenyan，HE Nan，LI Deyi，et al.Community dis?covery method in networks based on topological potential［J］.Journal of Software，2009，20（8）：2241?2254.

［11］鄧小龍，王柏，吳斌，等.基于信息熵的復雜網絡社團劃分建模和驗證［J］.計算機研究與發展，2012，49（4）：725?734.DENG Xiaolong，WANG Bai，WU Bin，et al.Modularity modeling and evaluation in community detection of complex network based on information entropy［J］.Journal of Com?puter Research and Development，2012，49（4）：725?734.

Optional granularity community detection algorithm based on gravitation

DONG Yuxin，CHI Kuo，YIN Guisheng

（College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China）

Community detection is an important field in the study of complex networks，and it is widely applied.But for most of the existing algorithms at present，community structure is determined by some community evaluation function，and only one division result can be obtained.Referenced from the galaxy model and the law of universal gravitation，a new community detection algorithm of complex network based on gravitational search is proposed，nodes in a network are given quality，and community framework is built.Then community structure is divided via gravitation.The granularity of the detected communities can be selected，and thereby a variety of division results can be obtained，without prior knowledge and the related parameters.Experiments in real networks，and compari?son with other pre?existing community detection algorithms prove that，the community structure of complex networks can be effectively and accurately excavated via the proposed algorithm.

complex network；optional granularity；community detection；gravitation

10.3969／j.issn.1006?7043.201404026

TP391

：A

：1006?7043（2015）06?0809?05

http：／／www.cnki.net／kcms／detail／23.1390.u.20150428.1117.020.html

2014?04?14.網絡出版時間：2015?04?28.

國家自然科學基金資助項目（61272186）；黑龍江省自然科學基金資助項目（F201110）.

董宇欣（1974?），女，副教授，博士；遲闊（1989?），男，博士研究生；印桂生（1964?），男，教授，博士生導師.

遲闊，E?mail：chik89769＠163.com.