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

董宇欣，遲闊，印桂生

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001）

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

董宇欣，遲闊，印桂生

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001）

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

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

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

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

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

1 宇宙星系模型的引入

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

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

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

在復(fù)雜網(wǎng)絡(luò)中引入宇宙模型后，接下來通過引力作用來劃分社區(qū)結(jié)構(gòu)。這里引入萬有引力計(jì)算公式：

式中：fij表示個體vi與vj之間的引力；G為引力常量，由于本文的研究對象均為同構(gòu)網(wǎng)絡(luò)，因此將其設(shè)定為1；mi表示個體vi的質(zhì)量；Rij表示網(wǎng)絡(luò)中節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的拓?fù)渚嚯x，為了簡化計(jì)算，這里認(rèn)為只有直接相連的節(jié)點(diǎn)間存在引力作用，因此式（1）可修改為

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

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

2.1 構(gòu)建社區(qū)框架

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

圖1 一個網(wǎng)絡(luò)中的Star節(jié)點(diǎn)Fig.1 The Star nodes in a network

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法步驟

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 The experimental data set

實(shí)驗(yàn)所采用的對比算法是GN算法［1］，F(xiàn)ast算法和基于拓?fù)鋭莸纳鐓^(qū)發(fā)現(xiàn)算法［10］。最后將各算法劃分結(jié)果與真實(shí)網(wǎng)絡(luò)劃分結(jié)果進(jìn)行對比。

3.1 空手道俱樂部社交網(wǎng)絡(luò)

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

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

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

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

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

表2 各算法劃分結(jié)果準(zhǔn)確率的對比Table 2 The accuracy of the results compared

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

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

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

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

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

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

3.3 VAST通信網(wǎng)絡(luò)

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

表4 VAST數(shù)據(jù)集各網(wǎng)絡(luò)的信息Table 4 The information of VAST

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

表5 各個網(wǎng)絡(luò)的社區(qū)劃分結(jié)果對比Table 5 Comparision of community division results

4 結(jié)論

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

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

2）可根據(jù)需要劃分出不同粒度的社區(qū)結(jié)構(gòu)；

3）算法的時間復(fù)雜度較低，可應(yīng)用于大規(guī)模的實(shí)際網(wǎng)絡(luò)；

4）算法可以獲得合理且較為準(zhǔn)確的實(shí)驗(yàn)結(jié)果。

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

［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］淦文燕，赫南，李德毅，等.一種基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法［J］.軟件學(xué)報，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］鄧小龍，王柏，吳斌，等.基于信息熵的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分建模和驗(yàn)證［J］.計(jì)算機(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.網(wǎng)絡(luò)出版時間：2015?04?28.

國家自然科學(xué)基金資助項(xiàng)目（61272186）；黑龍江省自然科學(xué)基金資助項(xiàng)目（F201110）.

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

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