董宇欣，遲闊，印桂生

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

基于引力作用的可選粒度社區(qū)發(fā)現(xiàn)算法

董宇欣，遲闊，印桂生

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

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

復雜網絡；可選粒度；社區(qū)發(fā)現(xiàn)；引力作用

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

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

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

1 宇宙星系模型的引入

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

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

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

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

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

2 基于引力搜索的可選粒度社區(qū)發(fā)現(xiàn)

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

2.1 構建社區(qū)框架

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

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

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

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

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

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

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

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

社區(qū)C對節(jié)點vi的引力F值定義為

式中：Fin（vi，C）表示節(jié)點vi與社區(qū)C中節(jié)點引力大小之和，即

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

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

2.2 引力搜索完成社區(qū)劃分

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

2.3 算法步驟

算法 基于引力作用的可選粒度社區(qū)發(fā)現(xiàn)算法（optional granularity community detection algorithm based on gravitation）

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

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

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

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

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

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

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

3 實驗分析

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

表1 實驗數(shù)據集Table 1 The experimental data set

實驗所采用的對比算法是GN算法［1］，F(xiàn)ast算法和基于拓撲勢的社區(qū)發(fā)現(xiàn)算法［10］。最后將各算法劃分結果與真實網絡劃分結果進行對比。

3.1 空手道俱樂部社交網絡

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

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

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

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

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

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

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

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

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

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

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

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

3.3 VAST通信網絡

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

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

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

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

4 結論

本文提出了基于引力作用的可選粒度復雜網絡社區(qū)發(fā)現(xiàn)算法。相比于目前現(xiàn)有的算法，本文所提出的算法具有如下優(yōu)勢：

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

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

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

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

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

［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］淦文燕，赫南，李德毅，等.一種基于拓撲勢的網絡社區(qū)發(fā)現(xiàn)方法［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］.計算機研究與發(fā)展，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.