董宇欣，遲闊，印桂生

（哈爾濱工程大學(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ò)研究中的一個(gè)重要領(lǐng)域，且應(yīng)用廣泛，但目前已有的大多數(shù)算法都需采用社區(qū)評(píng)判函數(shù)來(lái)確定社區(qū)結(jié)構(gòu)的劃分，且僅能得到一種劃分結(jié)果。引入宇宙星系模型和萬(wàn)有引力定律，基于引力思想提出一種新的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，為網(wǎng)絡(luò)中節(jié)點(diǎn)賦予質(zhì)量并構(gòu)建出社區(qū)框架，繼而利用引力作用完成社區(qū)結(jié)構(gòu)劃分，并可對(duì)發(fā)現(xiàn)社區(qū)的粒度大小進(jìn)行選擇以得到多種劃分結(jié)果，無(wú)需先驗(yàn)知識(shí)及相關(guān)參數(shù)。通過(guò)真實(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)的演化過(guò)程對(duì)復(fù)雜網(wǎng)絡(luò)的研究和發(fā)展具有重要的推動(dòng)作用。

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

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

1 宇宙星系模型的引入

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

給定復(fù)雜網(wǎng)絡(luò)的無(wú)權(quán)無(wú)向圖NG＝（V，E），網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)為N，邊條數(shù)為M、V是節(jié)點(diǎn)集合，E是邊集合。此外也可以用N×N的鄰接矩陣A＝［aij］N×N來(lái)表示網(wǎng)絡(luò)圖，其中，對(duì)于任意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，對(duì)任意i，j∈｛1，2，…，n｝，當(dāng)滿足下列條件時(shí)：①Ci∈V；②Ci≠φ；.每個(gè)節(jié)點(diǎn)集合稱為NG的一個(gè)社區(qū)。

宇宙由數(shù)以億計(jì)的星體所組成，部分星體與臨近星體之間由于萬(wàn)有引力的作用而相互運(yùn)動(dòng)，最終形成星系系統(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ò)中來(lái)模擬網(wǎng)絡(luò)結(jié)構(gòu)并嘗試通過(guò)節(jié)點(diǎn)間相互吸引來(lái)實(shí)現(xiàn)社區(qū)結(jié)構(gòu)的劃分，因此需要為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)賦予質(zhì)量。本文用圖NG來(lái)描述網(wǎng)絡(luò)，一個(gè)節(jié)點(diǎn)的度表示該節(jié)點(diǎn)與周圍節(jié)點(diǎn)的聯(lián)系密集程度，一個(gè)節(jié)點(diǎn)的度越大，表示該節(jié)點(diǎn)與周圍較多節(jié)點(diǎn)彼此之間相互聯(lián)系，也能從一定程度上反映該節(jié)點(diǎn)在社區(qū)中的重要性，因此本文選用節(jié)點(diǎn)度的大小作為其質(zhì)量大小。

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

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

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

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

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

社區(qū)框架可看作由Star節(jié)點(diǎn)和Planet節(jié)點(diǎn)組成。宇宙的一個(gè)星系中，恒星的數(shù)量可能是多個(gè)，因此假定網(wǎng)絡(luò)中的社區(qū)核心也不僅僅局限于一個(gè)?？紤]到網(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ù)上文為每個(gè)節(jié)點(diǎn)定義的質(zhì)量，從全局的角度選取具有局部極大T值和局部極大M值的節(jié)點(diǎn)的并集作為網(wǎng)絡(luò)的Star節(jié)點(diǎn)集合。如圖1所示。

圖1 一個(gè)網(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)所形成的的三角形個(gè)數(shù)與其度大小的比值，可以反映該節(jié)點(diǎn)在與周圍節(jié)點(diǎn)聯(lián)系規(guī)模條件下的聯(lián)系緊密程度。局部極大T值節(jié)點(diǎn)定義為：存在節(jié)點(diǎn)vi，i∈｛1，2，…，N｝，對(duì)任意滿足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｝，對(duì)任意滿足eij＝1的節(jié)點(diǎn)vj，都有M（vi）≥M（vj）。

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

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

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

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

社區(qū)C對(duì)節(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)引力大小之和，即

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

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

此時(shí)，網(wǎng)絡(luò)中仍然有一些節(jié)點(diǎn)沒(méi)有被劃分進(jìn)入社區(qū)，本文利用各社區(qū)的引力關(guān)系大小搜索這些節(jié)點(diǎn)。同樣利用F值作為這些節(jié)點(diǎn)劃入相應(yīng)社區(qū)的依據(jù)，當(dāng)F（vi，Ci）＞0時(shí)，說(shuō)明了社區(qū)Ci中的節(jié)點(diǎn)對(duì)節(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）來(lái)構(gòu)建全網(wǎng)絡(luò)的引力矩陣。

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

3）將Star節(jié)點(diǎn)集合中相連的Star節(jié)點(diǎn)初始化進(jìn)入同一個(gè)社區(qū)，不相連的則初始化進(jìn)入不同的社區(qū)，初始化后得到各個(gè)社區(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）在各個(gè)社區(qū)的Star節(jié)點(diǎn)集合中，以其中具有極大M值的Star節(jié)點(diǎn)為中心，將與其相連的Star節(jié)點(diǎn)劃分進(jìn)同一個(gè)細(xì)化社區(qū)，若其中有極大T值節(jié)點(diǎn)同時(shí)連接多個(gè)極大M值節(jié)點(diǎn)，則將其劃入對(duì)其引力大小更大的細(xì)化社區(qū)中。也可以僅對(duì)其中部分社區(qū)的Star節(jié)點(diǎn)進(jìn)行上述處理，其余不做改變。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

2）可根據(jù)需要?jiǎng)澐殖霾煌６鹊纳鐓^(qū)結(jié)構(gòu)；

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

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

在下一步工作中，將嘗試把算法引入到重疊社區(qū)劃分和動(dòng)態(tài)網(wǎng)絡(luò)社區(qū)演化中，并利用更大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)集來(lái)進(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ù)鋭?shì)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法［J］.軟件學(xué)報(bào)，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ò)出版時(shí)間：2015?04?28.

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

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

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