劉 倩，劉 群

（重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065）

0 引 言

近年來(lái)，學(xué)者對(duì)復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)性質(zhì)的研究集中于重疊社區(qū)發(fā)現(xiàn)算法。目前，已經(jīng)出現(xiàn)了許多發(fā)現(xiàn)網(wǎng)絡(luò)重疊社區(qū)的算法。其中，Evans等［1］和Ahn等［2］分別發(fā)表了從邊的角度來(lái)研究社團(tuán)劃分，文獻(xiàn)［3］還運(yùn)用領(lǐng)導(dǎo)的思想來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)重疊社區(qū)。其它算法有基于模糊聚類的發(fā)現(xiàn)算法［4］，基于非負(fù)矩陣分解的發(fā)現(xiàn)算法［5］，基于混合概率模型的方法［6］等。圖1是一個(gè)具有兩個(gè)社區(qū)并存在重疊節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)圖，其中每個(gè)圓圈虛線內(nèi)的節(jié)點(diǎn)集構(gòu)成一個(gè)社區(qū)，而三角形節(jié)點(diǎn)就是社區(qū)之間的重疊結(jié)點(diǎn)。

圖1 重疊社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)

本文提出了基于引力度擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法。該算法中的種子選取策略考慮了種子對(duì)網(wǎng)絡(luò)中其它節(jié)點(diǎn)的直接與間接影響力，這使算法選取的種子更加準(zhǔn)確，從而使社區(qū)劃分的結(jié)果更加精確。

1 基本概念

1.1 結(jié)點(diǎn)的度

給定一個(gè)具有n個(gè)節(jié)點(diǎn)和m 條邊的網(wǎng)絡(luò)G（V，E），其中V 表示節(jié)點(diǎn)集合，E 表示邊集合。節(jié)點(diǎn)u與節(jié)點(diǎn)v之間連接的邊表示為euv，邊euv的權(quán)重為wuv；如果節(jié)點(diǎn)u與節(jié)點(diǎn)v有邊連接，則wuv＝1，相反，wuv＝0。節(jié)點(diǎn)u的度ku的定義如下

例如，在圖2所示的小網(wǎng)絡(luò)結(jié)構(gòu)中，節(jié)點(diǎn)5的度為1＋1＋1＋1＝4，節(jié)點(diǎn)9的度為1＋1＋1＝3，節(jié)點(diǎn)1的度為1＋1＋1＝3。網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的度等于與這個(gè)節(jié)點(diǎn)相連接的所有邊數(shù)的總和。

圖2 小網(wǎng)絡(luò)結(jié)構(gòu)

1.2 隸屬度

給定一個(gè)網(wǎng)絡(luò)G（V，E），以及G 中的一個(gè)社區(qū)c和一個(gè)節(jié)點(diǎn)u，則節(jié)點(diǎn)u 對(duì)社區(qū)c的隸屬度B（u，c）［7］的定義如下

式中：隸屬度函數(shù)B（u，c）反映了節(jié)點(diǎn)u與社區(qū)c聯(lián)系的緊密程度，B（u，c）的值越大，節(jié)點(diǎn)u與社區(qū)c的連接越密集，而B（u，c）的值越小，節(jié)點(diǎn)u與社區(qū)c的連接越松散。如果節(jié)點(diǎn)u的所有鄰居節(jié)點(diǎn)都被包含在社區(qū)c中，則B（u，c）＝1，即節(jié)點(diǎn)u只屬于c這一個(gè)社區(qū)；否則，B（u，c）＜1，即節(jié)點(diǎn)u屬于多個(gè)社區(qū)。

例如，在圖2中，假設(shè)社區(qū)c包含的節(jié)點(diǎn)集合為｛1，2，3，4，5｝，其中，節(jié)點(diǎn)6對(duì)社區(qū)c的隸屬度B（6，c）的值是1／（1＋1＋1）＝1／3，節(jié)點(diǎn)7對(duì)社區(qū)c的隸屬度B（7，c）的值是（1＋1）／（1＋1＋1＋1）＝1／2，節(jié)點(diǎn)5的所有鄰居節(jié)點(diǎn)都在社區(qū)c里，則它對(duì)社區(qū)c的隸屬度B（5，c）＝1。

1.3 引力度

牛頓萬(wàn)有引力定律是解釋物體之間的相互作用的引力定律。且牛頓萬(wàn)有引力定律認(rèn)為，地球上的任何兩個(gè)物體之間都存在萬(wàn)有引力，該引力的大小與它們的質(zhì)量乘積成正比，與它們距離的平方成反比，并且與兩物體的化學(xué)本質(zhì)或物理狀態(tài)以及中介物質(zhì)無(wú)關(guān)，公式表示如下

式中：F——兩個(gè)物體之間的引力，m1、m2——兩個(gè)相互存在引力的物體的質(zhì)量，r——兩個(gè)存在引力的物體之間的距離，G——引力常數(shù)。

由牛頓萬(wàn)有引力定律可知，既然任意兩個(gè)物體之間都存在引力，那么網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)之間也存在萬(wàn)有引力。由于網(wǎng)絡(luò)具有自己的結(jié)構(gòu)特性，將網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的萬(wàn)有引力重新定義為式（4）

式中：mu、mv——網(wǎng)絡(luò)中節(jié)點(diǎn)u和節(jié)點(diǎn)v的質(zhì)量。用節(jié)點(diǎn)的質(zhì)量來(lái)衡量節(jié)點(diǎn)自身的特性，則質(zhì)量越小，自身的重要性也越??；質(zhì)量越大，自身的重要性也越大。根據(jù)網(wǎng)絡(luò)自身的結(jié)構(gòu)性質(zhì)，對(duì)任意一個(gè)節(jié)點(diǎn)，只有節(jié)點(diǎn)的度能直接反應(yīng)出該節(jié)點(diǎn)的相關(guān)信息，同時(shí)也體現(xiàn)了一個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中其它節(jié)點(diǎn)的直接通信能力。因此，我們采用節(jié)點(diǎn)的度來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)的質(zhì)量，則對(duì)任意節(jié)點(diǎn)u，就有mu＝ku。

而距離d（u，v）的衡量，我們?nèi)匀粡木W(wǎng)絡(luò)的結(jié)構(gòu)特性出發(fā)，用節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的最短路徑長(zhǎng)度來(lái)具體度量d（u，v）。網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的最短路徑長(zhǎng)度即是以節(jié)點(diǎn)u為起點(diǎn)，以v為終點(diǎn)的最短路徑中所含邊的數(shù)量，此長(zhǎng)度值還可以反應(yīng)出節(jié)點(diǎn)u最少能通過(guò)幾個(gè)節(jié)點(diǎn)就能與節(jié)點(diǎn)v取得聯(lián)系，即表明了一個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中其它節(jié)點(diǎn)間接通信的最大能力。

既然，網(wǎng)絡(luò)中的任意節(jié)點(diǎn)u都與其它節(jié)點(diǎn)之間存在引力，那么網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)與其它節(jié)點(diǎn)的引力就存在一個(gè)和值，就將網(wǎng)絡(luò)中的節(jié)點(diǎn)u與其它節(jié)點(diǎn)的引力之和定義為節(jié)點(diǎn)u的引力度，其定義式如式（5）

2 基于引力度擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法

給定一個(gè)網(wǎng)絡(luò)G（V，E），節(jié)點(diǎn)數(shù)｜V｜＝n，邊數(shù)｜E｜＝m；該算法主要由兩部分組成：①尋找初始社區(qū)；②對(duì)社區(qū)進(jìn)行擴(kuò)展。為了挖掘出網(wǎng)絡(luò)中的重疊社區(qū)，將網(wǎng)絡(luò)中未被劃分到任意一個(gè)社區(qū)中的節(jié)點(diǎn)標(biāo)記為 ‘M’，這些被標(biāo)記為 ‘M’的節(jié)點(diǎn)集合記為VM，而已經(jīng)被分配到至少一個(gè)社區(qū)中的節(jié)點(diǎn)標(biāo)記為 ‘D’，這些被標(biāo)記為 ‘D’的節(jié)點(diǎn)集合記為VD，且VM＝V－VD。首先，將網(wǎng)絡(luò)中所有節(jié)點(diǎn)的劃分狀態(tài)初始化為 ‘M’，即沒有任意一個(gè)節(jié)點(diǎn)已經(jīng)被劃分到某個(gè)社區(qū)。

2.1 尋找初始社區(qū)

步驟1 使用式（5），即用f（u）的定義公式來(lái)計(jì)算網(wǎng)絡(luò)中劃分狀態(tài)標(biāo)記為 ‘M’的節(jié)點(diǎn)的引力度值；

步驟2 選取引力度值最大的節(jié)點(diǎn)作為發(fā)現(xiàn)一個(gè)社區(qū)的種子；

步驟3 查詢種子節(jié)點(diǎn)的劃分狀態(tài)為 ‘M’的鄰居節(jié)點(diǎn)集合，這些鄰居節(jié)點(diǎn)與種子節(jié)點(diǎn)便形成了一個(gè)初始社區(qū)c；

步驟4 對(duì)于社區(qū)c中的每一個(gè)節(jié)點(diǎn)u，計(jì)算其隸屬度B（u，c）的值，如果存在B（u，c）＜Bc（Bc表示節(jié)點(diǎn)u與社區(qū)c聯(lián)系緊密程度的門限值）的節(jié)點(diǎn)，則將這些節(jié)點(diǎn)從社區(qū)c中移除；

步驟5 返回步驟4，直到 u ∈c，B（u，c）≥Bc，則獲得了最終的初始社區(qū)c。

2.2 擴(kuò)展社區(qū)

步驟1 找出社區(qū)c的鄰居節(jié)點(diǎn)集合，將其記為Nc，并計(jì)算鄰居節(jié)點(diǎn)集Nc中每個(gè)節(jié)點(diǎn)v的隸屬度B（v，c）的值；

步驟2 找出Nc中隸屬度B（v，c）≥Bv（Bv表示節(jié)點(diǎn)v與社區(qū)c聯(lián)系緊密程度的門限值）的所有節(jié)點(diǎn)，用Nv＝｛B（v，c）≥Bv｝表示這個(gè)節(jié)點(diǎn)集合；

步驟3 如果｜Nv｜＞0（｜Nv｜表示集合Nv中節(jié)點(diǎn)的個(gè)數(shù)），則添加Nv集合中的節(jié)點(diǎn)到社區(qū)c中，便形成了一個(gè)更大的社區(qū)c，返回步驟1；

步驟4 如果｜Nv｜＝0，則挖掘出了一個(gè)最終的社區(qū)c。

例如，在圖3中，假定初始社區(qū)c包含的節(jié)點(diǎn)集為｛1，2，3，4，5｝，它的鄰居節(jié)點(diǎn)集合為｛8，7，6｝，其中B（8，c）＝1／4，B（7，c）＝2／5，B（6，c）＝3／5，添加節(jié)點(diǎn)6到社區(qū)c中。添加節(jié)點(diǎn)6之后，社區(qū)c的鄰居節(jié)點(diǎn)集Nc中的任意節(jié)點(diǎn)v，都有B（v，c）＜Bv。此時(shí)，停止社區(qū)擴(kuò)展過(guò)程并發(fā)現(xiàn)了一個(gè)最終的社區(qū)c＝｛1，2，3，4，5，6｝，即圖3中的三角形節(jié)點(diǎn)集。

圖3 社區(qū)擴(kuò)展

2.3 算法流程圖

圖4表明了如何挖掘出一個(gè)網(wǎng)絡(luò)中的所有重疊社區(qū)。當(dāng)作社區(qū)擴(kuò)展時(shí)，查找鄰居節(jié)點(diǎn)集是不考慮鄰居節(jié)點(diǎn)是否已經(jīng)被劃分到了某個(gè)社區(qū)，因此就可以發(fā)現(xiàn)社區(qū)之間的重疊結(jié)點(diǎn)，即發(fā)現(xiàn)重疊社區(qū)。

3 實(shí)驗(yàn)與結(jié)果分析

為了測(cè)試本文算法的可行性，將算法運(yùn)用在真實(shí)網(wǎng)絡(luò)上進(jìn)行了測(cè)試，并與Lancichinetti［8］等提出的重疊社區(qū)發(fā)現(xiàn)算法 （LMF算法［9］）做了性能上的對(duì)比。

3.1 模塊度

圖4 算法流程

為了衡量一個(gè)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分質(zhì)量的優(yōu)劣，New－man［10］提出了模塊度Q 這一衡量指標(biāo)。雖然該模塊度已經(jīng)在復(fù)雜網(wǎng)絡(luò)中得到了廣泛的認(rèn)可與運(yùn)用，但是，仍然存在諸多問(wèn)題，例如它不能解決衡量重疊社區(qū)結(jié)構(gòu)劃分質(zhì)量的限制性問(wèn)題［11］。為了解決此問(wèn)題，又有人提出了衡量重疊社區(qū)結(jié)構(gòu)劃分質(zhì)量的模塊度函數(shù)，本文采用文獻(xiàn)［12］中的擴(kuò)展模塊度函數(shù)EQ（extend modularity）來(lái)衡量重疊社區(qū)結(jié)構(gòu)劃分的質(zhì)量。EQ 的定義如下

式中：m——網(wǎng)絡(luò)中節(jié)點(diǎn)之間連接的總邊數(shù)，Qu、Qv——節(jié)點(diǎn)u、節(jié)點(diǎn)v所屬的社區(qū)個(gè)數(shù)，Auv——網(wǎng)絡(luò)的鄰接矩陣?yán)锏脑?，也反映了?jié)點(diǎn)u與節(jié)點(diǎn)v的連接情況，如果節(jié)點(diǎn)u與節(jié)點(diǎn)v有連接，則Auv＝1，相反，Auv＝0，Ku、Kv分別表示節(jié)點(diǎn)u、節(jié)點(diǎn)v的度。

3.2 真實(shí)網(wǎng)絡(luò)

本文算法中Bc（Bc表示節(jié)點(diǎn)u與社區(qū)c聯(lián)系緊密程度的門限值）的取值影響著社區(qū)劃分的尺度與社區(qū)結(jié)構(gòu)的優(yōu)劣和明顯程度。下面主要從Bc取0.4與0.5來(lái)討論我們算法劃分的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的結(jié)果。

3.2.1 Zachary’s karate club

Zachary社會(huì)網(wǎng)是復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中經(jīng)常被用來(lái)進(jìn)行測(cè)試的經(jīng)典小型網(wǎng)絡(luò)數(shù)據(jù)集，該網(wǎng)絡(luò)反映了美國(guó)一所大學(xué)空手道俱樂(lè)部成員之間的社會(huì)關(guān)系。網(wǎng)絡(luò)包含34個(gè)節(jié)點(diǎn)與78條邊，每一個(gè)節(jié)點(diǎn)表示一個(gè)俱樂(lè)部成員，每一條邊表示俱樂(lè)部成員之間除了具有俱樂(lè)部成員的關(guān)系外，他們私下還是朋友的關(guān)系。本文算法將Zachary社會(huì)網(wǎng)劃分的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)與真實(shí)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)如圖5所示。

圖5 社區(qū)劃分

在圖5的圖（a）、圖（b）、圖（c）中，實(shí)心圓節(jié)點(diǎn)集表示一個(gè)社區(qū)，實(shí)心正方形節(jié)點(diǎn)集表示另一個(gè)社區(qū)，三角形節(jié)點(diǎn)集表示社區(qū)之間的重疊節(jié)點(diǎn)。圖5 （a）是真實(shí)社區(qū)結(jié)構(gòu)圖，節(jié)點(diǎn)3是兩個(gè)社區(qū)之間的重疊節(jié)點(diǎn)。在圖5（b）中，Bc取值為0.4，網(wǎng)絡(luò)被本文算法劃分為兩個(gè)社區(qū)，節(jié)點(diǎn)3、9、10、14、31是兩個(gè)社區(qū)之間的重疊節(jié)點(diǎn)。在圖5（c）中，Bc取值為0.5，此時(shí)本文算法仍然將網(wǎng)絡(luò)劃分為2個(gè)社區(qū)，但重疊節(jié)點(diǎn)是3、10。將圖5中的圖（b）、圖（c）與圖（a）作對(duì)比，可以得出Bc＝0.5時(shí)，我們算法所劃分的社區(qū)結(jié)構(gòu)與真實(shí)社區(qū)結(jié)構(gòu)更相符合。

3.2.2 American College football

College football網(wǎng)通常也是社區(qū)發(fā)現(xiàn)中算法運(yùn)用的網(wǎng)絡(luò)數(shù)據(jù)集對(duì)象，該網(wǎng)絡(luò)描述了美國(guó)一所大學(xué)里各學(xué)院之間玩足球游戲的社會(huì)關(guān)系。網(wǎng)絡(luò)包含了115個(gè)結(jié)點(diǎn)和615條邊，節(jié)點(diǎn)表示足球隊(duì)，節(jié)點(diǎn)之間的邊則表示足球隊(duì)之間有足球比賽的社會(huì)關(guān)系。當(dāng)Bc取值為0.4時(shí)，我們算法將網(wǎng)絡(luò)劃分為11個(gè)非重疊社區(qū)；當(dāng)Bc取值為0.5 時(shí)，算法將網(wǎng)絡(luò)劃分為14個(gè)非重疊社區(qū)。

3.2.3 Email

Email網(wǎng)是Rovira i Virgeili大學(xué)的一個(gè)郵件網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含1133個(gè)節(jié)點(diǎn)和5451條邊。我們算法在Bc取值為0.4時(shí)將網(wǎng)絡(luò)劃分為232個(gè)社區(qū)，社區(qū)之間有101個(gè)重疊節(jié)點(diǎn)，在Bc取值為0.5時(shí)將網(wǎng)絡(luò)劃分為261個(gè)社區(qū)，社區(qū)之間有107個(gè)重疊節(jié)點(diǎn)。

本文算法與LMF算法在3個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行測(cè)試的算法性能結(jié)果見表1。

表1 算法性能對(duì)比

從3個(gè)網(wǎng)絡(luò)的描述與表1可以得出，當(dāng)網(wǎng)絡(luò)數(shù)據(jù)集不同，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)也不相同，隨著節(jié)點(diǎn)數(shù)的增多，我們算法的運(yùn)行時(shí)間與LMF算法的運(yùn)行時(shí)間都在增加，尤其是本文算法的運(yùn)行時(shí)間增加更快。對(duì)表1作進(jìn)一步分析，在karate網(wǎng)絡(luò)中，Bc取0.4與0.5時(shí)，我們算法的EQ 值都比LMF算法的EQ 值略低，說(shuō)明本文算法劃分的社區(qū)結(jié)構(gòu)不如LMF算法劃分的社區(qū)結(jié)構(gòu)明顯，且我們算法在Bc取0.5比Bc取0.4時(shí)的EQ 值高，即Bc取0.5時(shí)的社區(qū)劃分結(jié)果更好。在football網(wǎng)絡(luò)中，Bc取0.4與0.5時(shí)，我們算法的EQ 值都比LMF算法的EQ 值高，表明我們算法劃分的社區(qū)結(jié)構(gòu)比LMF算法劃分的社區(qū)結(jié)構(gòu)更優(yōu)。而在email網(wǎng)絡(luò)中，Bc取0.4時(shí)，我們算法的EQ 值比LMF算法的EQ 值高，即我們算法劃分的社區(qū)結(jié)構(gòu)比LMF算法劃分的社區(qū)結(jié)構(gòu)更好，但Bc取0.5 時(shí)，我們算法的EQ 值卻比LMF 算法的EQ 值低，即我們算法劃分的社區(qū)結(jié)構(gòu)比LMF算法劃分的社區(qū)結(jié)構(gòu)稍差。

3.2.4 KDD Cup2012

KDD Cup2012是2012年在中國(guó)舉行的國(guó)際性數(shù)據(jù)挖掘大賽，大賽任務(wù)一是好友推薦，其數(shù)據(jù)集是由騰訊微博提供的大量微博數(shù)據(jù)。騰訊微博也是一個(gè)社會(huì)關(guān)系網(wǎng)絡(luò)，每一個(gè)微博用戶就是網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，用戶在微博上與其他用戶取得的聯(lián)系就是網(wǎng)絡(luò)中的邊。該微博數(shù)據(jù)集分為很多項(xiàng)目文件，其中的user＿profile.txt文件描述的是每個(gè)騰訊微博用戶的一些基本信息，如用戶的編號(hào)、出身日期、興趣愛好等，user＿sns.txt文件描述的是微博用戶之間在微博上有聯(lián)系的社會(huì)關(guān)系。我們從user＿profile.txt文件中提取了不同規(guī)模的節(jié)點(diǎn)數(shù)（節(jié)點(diǎn)數(shù)以100作為起點(diǎn)），并從user＿sns.txt文件中提取了不同規(guī)模節(jié)點(diǎn)對(duì)應(yīng)的邊關(guān)系。將本文算法與LMF算法在提取的數(shù)據(jù)集上做了測(cè)試，然后對(duì)測(cè)試的結(jié)果做了對(duì)比分析。如圖所示，其中圖6是算法的運(yùn)行時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系圖，橫坐標(biāo)為節(jié)點(diǎn)數(shù)，縱坐標(biāo)為運(yùn)行時(shí)間；圖7 是EQ 與節(jié)點(diǎn)數(shù)的關(guān)系圖，橫坐標(biāo)為節(jié)點(diǎn)數(shù)，縱坐標(biāo)為EQ 值。

圖6 時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系

圖7 EQ 與節(jié)點(diǎn)數(shù)的關(guān)系

由圖6可以得出，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模增大時(shí)，我們算法的運(yùn)行時(shí)間仍然比LMF算法的運(yùn)行時(shí)間增加得更多。由圖7可以看出，我們算法的EQ 值與LMF 算法的EQ 值在節(jié)點(diǎn)數(shù)增加時(shí)都有所下降，但我們算法在Bc取0.4 與0.5時(shí)，其EQ 值都比LMF算法的EQ 值高，這說(shuō)明我們算法劃分的社區(qū)結(jié)構(gòu)更加精確與明顯。而節(jié)點(diǎn)規(guī)模為1000 時(shí)，我們算法在Bc取0.4時(shí)的社區(qū)劃分結(jié)果比Bc取0.5時(shí)的社區(qū)劃分結(jié)果更準(zhǔn)確。

4 結(jié)束語(yǔ)

本文提出了基于引力度擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法。算法以引力度最大的節(jié)點(diǎn)為種子來(lái)尋找初始社區(qū)，再進(jìn)行擴(kuò)展得到最終社區(qū)。將算法在真實(shí)網(wǎng)絡(luò)上進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果顯示我們算法的時(shí)間復(fù)雜度比LMF算法的時(shí)間復(fù)雜度高。我們算法劃分的社區(qū)結(jié)構(gòu)的結(jié)果雖然受Bc取值的影響，但總體上獲得的EQ 值比LMF算法的EQ 值更高，即我們算法劃分的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)比LFM 算法劃分的社區(qū)結(jié)構(gòu)更精確，這說(shuō)明我們算法在發(fā)現(xiàn)網(wǎng)絡(luò)重疊社區(qū)上是可行與有效的。我們后續(xù)工作將提高算法的時(shí)間效率，并提高我們算法在大數(shù)據(jù)網(wǎng)絡(luò)上劃分的社區(qū)結(jié)構(gòu)質(zhì)量。

［1］Evans T，Lambiotte R.Line graphs，link partitions，and overlapping communities ［J］.Physical Review E，2009，80（1）：1－8.

［2］Ahn Y Y，Bagrow J P，Lehmann S.Link communities reveal multiscale complexity in networks ［J］.Nature，2010，466：761－764.

［3］Li H J，Zhang J H，Liu Z P，et al.Identifying overlapping communities in social networks using multi－scale local information expansion ［J］.The European Physical Journal B，2012，85 （6）：1－9.

［4］Zhang S，Wang R S，Zhang X.Identification of overlapping community structure in complex networks using fuzzy C－means clustering ［J］.Physica A：Statistical Mechanics and its Applications，2007，374 （1）：483－490.

［5］Zarei M，Izadi D，Samani K A.Detecting overlapping community structure of networks based on vertex－vertex correlations［J］.Journal of Statistical Mechanics：Theory and Experiment，2009 （11）：11013.

［6］Ball B，Karrer B，Newman M E J.An efficient and principled method for detecting communities in networks ［J］.Physical Review E，2011，84 （3）：1－14.

［7］Chen D，Shang M，Lv Z，et al.Detecting overlapping communities of weighted networks via a local algorithm ［J］.Physica A：Statistical Mechanics and its Applications，2010，389（19）：4177－4187.

［8］Lancichinetti A，F(xiàn)ortunato S，Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks［J］.New Journal of Physics，2009，11 （3）：1－18.

［9］LUO Zhigang，DING Fan，JIANG Xiaozhou，et al.New progress on community detection in complex networks ［J］.Journal of National University of Defense Technology，2011，33（1）：47－51 （in Chinese）.［駱志剛，丁凡，蔣曉舟，等.復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展 ［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2011，33 （1）：47－51.］

［10］Newman M E J.Modularity and community structure in networks［J］.Proceeding of the National Academy of Sciences of the United States of America，2006，103 （23）：8577－8582.

［11］Fortunato S，Barthélemy M.Resolution limit in community detection ［J］.Proceeding of the National Academy of Sciences of the United States of America，2007，104 （1）：36－41.

［12］Shen Hawei，Cheng Xueqi，Cai Kai，et al.Detect overlapping and hierarchical community structure in networks ［J］.Physica A，2009，388 （8）：1706－1712.