孫延維， 雷建軍*， 劉 倩

(1.湖北第二師范學(xué)院 基礎(chǔ)教育信息技術(shù)服務(wù)湖北省協(xié)同創(chuàng)新中心， 武漢 430205;2.重慶郵電大學(xué) 計算智能重慶市重點實驗室， 重慶 400065)

?

孫延維1， 雷建軍1*， 劉 倩2

(1.湖北第二師范學(xué)院 基礎(chǔ)教育信息技術(shù)服務(wù)湖北省協(xié)同創(chuàng)新中心， 武漢 430205;2.重慶郵電大學(xué) 計算智能重慶市重點實驗室， 重慶 400065)

社交網(wǎng)絡(luò)擁有社區(qū)結(jié)構(gòu)，而網(wǎng)絡(luò)中的一些節(jié)點又被兩個或更多社區(qū)共享，這就使網(wǎng)絡(luò)呈現(xiàn)出重疊社區(qū)結(jié)構(gòu).在前面對重疊社區(qū)劃分算法的研究中提出了基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法(GDE)，以引力度最大的節(jié)點為種子來擴展與發(fā)現(xiàn)重疊社區(qū).這里，提出基于h-域的局部引力度擴展的改進(jìn)算法(LGDE).改進(jìn)算法的實驗測試結(jié)果表明該算法的執(zhí)行效率獲得了極大的提高，并且是可行的.

重疊社區(qū)； 局部引力度；h-域； 社交網(wǎng)絡(luò)； 種子擴展

真實世界里的網(wǎng)絡(luò)擁有社區(qū)結(jié)構(gòu)這一重要特征，而在大多數(shù)實際的社交網(wǎng)絡(luò)[1]中，一些社交成員都是同時參與了多個社交圈子，那么社交網(wǎng)絡(luò)的重疊社區(qū)現(xiàn)象是顯而易見的.學(xué)術(shù)界對挖掘網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)的興趣與日俱增，目前已經(jīng)出現(xiàn)了許多重疊社區(qū)發(fā)現(xiàn)算法.其中包括基于快速派系過濾的SCP算法[2]，之后又有基于信息論編碼理論的InfoMap算法[3]，以及Blondel[4]等的層次快速展開算法等.

通過研究發(fā)現(xiàn)，現(xiàn)有的種子擴展類型的算法選取的種子具有隨機性或種子在網(wǎng)絡(luò)中的影響力較弱，這就可能使算法的社區(qū)發(fā)現(xiàn)效果不佳.針對此問題，在先前的研究中已提出了基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法[5]，其測試結(jié)果顯示算法劃分的社區(qū)結(jié)果的準(zhǔn)確率有所提高，但執(zhí)行效率較低，因此，本文提出改進(jìn)的局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法.

1 局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法

給定一個無向、無權(quán)網(wǎng)絡(luò)G(V，E)，其中V是網(wǎng)絡(luò)的節(jié)點集，E是網(wǎng)絡(luò)的邊集，節(jié)點數(shù)|V|=n，邊數(shù)|E|=m；將網(wǎng)絡(luò)中未被劃分到任意一個社區(qū)中的節(jié)點的劃分狀態(tài)標(biāo)記為‘F’，已經(jīng)被分配到社區(qū)里的節(jié)點的劃分狀態(tài)標(biāo)記為‘T’.首先，將網(wǎng)絡(luò)中所有節(jié)點的劃分狀態(tài)初始化為‘F’.

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

基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法[5]包含了有序的算法流程，其描述如下.

1)查找初始社區(qū)

步驟1：使用計算節(jié)點引力度的公式來計算網(wǎng)絡(luò)中未被劃分到社區(qū)里的節(jié)點的引力度值；

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

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

步驟4：對于社區(qū)c中的每一個節(jié)點u，計算其隸屬度B(u，c)的值，如果存在B(u，c)

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

2)擴展社區(qū)

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

步驟2：找出Nc中隸屬度B(v，c)≥Bv(其中Bv表示節(jié)點v與社區(qū)c聯(lián)系緊密程度的門限值)的所有節(jié)點，用Nv={B(v，c)≥Bv}表示這個節(jié)點集合；

步驟3：如果|Nv|>0(|Nv|表示集合Nv中節(jié)點的個數(shù))，則添加Nv中的節(jié)點到社區(qū)c中，便形成了一個更大的社區(qū)c，返回步驟1；

步驟4：如果|Nv|=0，則挖掘出了一個最終的重疊社區(qū)c.

該算法在查找初始社區(qū)的步驟1中計算節(jié)點的全局引力度值時，要計算該節(jié)點與網(wǎng)絡(luò)中其他節(jié)點的最短路徑長度，而計算網(wǎng)絡(luò)中任意兩點間的最短路徑長度的時間復(fù)雜度是O(n3)，則發(fā)現(xiàn)網(wǎng)絡(luò)中所有重疊社區(qū)的時間復(fù)雜度就是O(n4)，這會使算法的執(zhí)行效率非常低下，而且通過實驗表明該算法運行所耗費的時間代價確實很大.

1.2 節(jié)點的h-域

網(wǎng)絡(luò)G的節(jié)點u的h-域表示的是包括所有通過節(jié)點u或者以節(jié)點u為起點的最短路徑長度不超過h的節(jié)點集.節(jié)點u的h-域的導(dǎo)出子圖的節(jié)點集[6]被定義為式(1)：

(1)

例如，圖1所示的網(wǎng)絡(luò)中，橢圓虛線圈畫范圍內(nèi)的子圖就是節(jié)點6的2-域?qū)С鲎訄D，而節(jié)點6的2-域?qū)С鲎訄D的節(jié)點集V6，2={1，2，3，4，5，7，8，9，10}.其中d(6，1)=2，d(2，2)=2，d(2，3)=1，d(2，4)=1，d(2，5)=1，d(2，7)=1，d(2，8)=1，d(2，9)=2，d(2，10)=2，都滿足d(6，v)≤2的條件.

圖1 簡單的網(wǎng)絡(luò)圖Fig.1 Illustration of a simple network

1.3 節(jié)點的局部引力度

節(jié)點u的引力度就是網(wǎng)絡(luò)中的節(jié)點u與其他節(jié)點的引力之和，這是一個全局引力度的概念，其定義為[5]：

(2)

為改善算法的執(zhí)行效率，我們引進(jìn)節(jié)點h-域的思想將全局引力度優(yōu)化為局部引力度的概念.而局部引力度的定義則為式2必須滿足附加約束條件式(1)，將局部引力度的公式表示為：

(3)

其中，Vu，h是節(jié)點u的h-域?qū)С鲎訄D的節(jié)點集合，Mu，Mv是網(wǎng)絡(luò)節(jié)點u、節(jié)點v的質(zhì)量，p(u，v)是節(jié)點u與節(jié)點v之間的最短距離.

1.4 局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法(LGDE)

本文提出了h-域局部引力度的概念，這就使得局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法在尋找初始社區(qū)時與基于引力度擴展算法在尋找初始社區(qū)的流程與思想有所不同.在此給出基于局部引力度思想下尋找初始社區(qū)的算法流程，其詳細(xì)描述如下：

1)確定社區(qū)種子

步驟1：指定h-域的h大小；

步驟2：查找標(biāo)記為‘F’的節(jié)點集合，將其記為VF；

步驟3：對?v∈VF，利用廣度優(yōu)先搜索查找節(jié)點v在h-域內(nèi)的節(jié)點集合，將其記為Vv，h；

步驟4：利用公式(3)計算?v∈VF的局部引力度值，并選局部引力度值最大的節(jié)點為社區(qū)的種子節(jié)點，將其記為u.

2)由種子源查找初始社區(qū)

步驟1：查找種子節(jié)點u的鄰居節(jié)點集，則這些鄰居節(jié)點就與節(jié)點u一起組成了初始社區(qū)c，并將社區(qū)c的節(jié)點集記為Vc；

步驟2：對于?v∈Vc，計算其隸屬度B(v，c)的值，如果存在B(v，c)

步驟3：返回步驟2，直到?v∈Vc，B(v，c)≥Bc，則獲得了確定的初始社區(qū)c.

1.5 局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法的流程圖

圖2是局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法的流程圖，該圖清楚的描述了算法如何確定社區(qū)種子，并通過種子節(jié)點尋找初始社區(qū)，然后擴展初始社區(qū)，直到最終挖掘出網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu).

圖2 算法流程圖Fig.2 Illustration of the algorithm process

2 實驗分析

為了測試基于h-域的局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法的可行性與有效性，將算法運用在真實網(wǎng)絡(luò)上進(jìn)行了測試，并與LFM算法[7]、基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法做性能上的對比.

本文提出的算法中的h為一個設(shè)置參數(shù)，在進(jìn)行算法實驗時，將選取h=2與h=3[6]來計算節(jié)點的h-域引力度值.

2.1 算法評價指標(biāo)

2.1.1時間復(fù)雜度 時間復(fù)雜度是評價算法的時間花費代價的一個性能指標(biāo)，是指執(zhí)行算法所需要的計算工作，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率.本文首先從理論上加以分析本算法時間復(fù)雜度，然后以本算法程序的運行時間為標(biāo)準(zhǔn)，來評估算法的執(zhí)行效率.

2.1.2評價重疊社區(qū)劃分質(zhì)量的模塊度 本文算法測試的真實社交網(wǎng)絡(luò)數(shù)據(jù)集基本都屬于無先驗知識、無元數(shù)據(jù)、無類標(biāo)的網(wǎng)絡(luò)數(shù)據(jù)集.為了衡量本文算法對一個網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)劃分質(zhì)量的好壞，仍然采用文獻(xiàn)[8]中提出的擴展模塊度函數(shù)EQ(Extend Modularity)來衡量算法劃分的重疊社區(qū)結(jié)構(gòu)的質(zhì)量.

2.2 真實網(wǎng)絡(luò)數(shù)據(jù)集介紹

本文算法測試的網(wǎng)絡(luò)數(shù)據(jù)集為Zachary’s karate clubshe社交網(wǎng)絡(luò)[9]、Dolphins’s social network[10]、American College football社會網(wǎng)絡(luò)[9]、Email網(wǎng)絡(luò)數(shù)據(jù)集[11]與KDD Cup2012部分?jǐn)?shù)據(jù)集[5].其中Karate club包括34個節(jié)點與78條邊；Dolphin擁有62個節(jié)點、159條邊；football包含115個節(jié)點與615條邊；Email有1133個節(jié)點與5451條邊.KDD Cup2012部分?jǐn)?shù)據(jù)集是以一定規(guī)模增長提取的數(shù)據(jù)集，節(jié)點個數(shù)的起點為100.

2.3 社交網(wǎng)絡(luò)的算法性能分析

2.3.1算法時間復(fù)雜度的理論分析 局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法(LGDE)在計算網(wǎng)絡(luò)節(jié)點的h-域引力度值的時間復(fù)雜度受參數(shù)h的影響，而1≤h≤n-1，其中n表示網(wǎng)絡(luò)的規(guī)模.LGDE算法在計算網(wǎng)絡(luò)中任意兩點間的最短路徑長度的時間復(fù)雜度在最優(yōu)情況下是O(n2)，最差情況下為O(n2(n-1))，因此，發(fā)現(xiàn)網(wǎng)絡(luò)中所有重疊社區(qū)的時間復(fù)雜度在最優(yōu)情況下就是O(n3)，最差情況下為O(n3(n-1)).由此可見，LGDE算法的時間復(fù)雜度在最優(yōu)與最差情況下都比GDE算法的時間復(fù)雜度O(n4)獲得了良好的改善.

2.3.2Karate club、Dolphin、Football、Email的運行效率分析 對Karate club、Dolphin、Football、Email社交網(wǎng)進(jìn)行了算法的真實運行時間分析，其算法的執(zhí)行效率分析如表1.

表1 算法的執(zhí)行效率對比表

對表1進(jìn)行分析可知，LFM算法、基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法、h-域引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法在Karate club、Dolphin、Football、Email網(wǎng)絡(luò)數(shù)據(jù)集上的運行時間隨著網(wǎng)絡(luò)規(guī)模的增大都在不斷的增加.其中h-域引力度擴展算法的運行時間比LFM算法、引力度擴展算法的運行時間增加更慢，即h-域引力度擴展算法的執(zhí)行效率比引力度擴展算法的執(zhí)行效率獲得了顯著的提高.

2.3.3Karate club、Dolphin、Football、Email重疊社區(qū)劃分的準(zhǔn)確率分析 算法劃分的重疊社區(qū)結(jié)構(gòu)的質(zhì)量優(yōu)劣分析如圖3.圖3是算法的EQ值與Social network的關(guān)系圖，橫坐標(biāo)表示社交網(wǎng)絡(luò)，縱坐標(biāo)表示EQ取值.

圖3 Social network與EQ的關(guān)系圖Fig.3 Statistics of the EQ for four social network

對圖3進(jìn)行分析，由圖中的(a)可知，在Karate網(wǎng)絡(luò)中，引力度擴展算法、h=2與h=3時的h-域引力度擴展算法的EQ值是相同的，且都比LFM算法的EQ值稍低.因此，LFM算法對Karate網(wǎng)絡(luò)劃分的重疊社區(qū)結(jié)構(gòu)比引力度擴展算法、h-域引力度擴展算法在Bc=0.4時劃分的重疊社區(qū)結(jié)構(gòu)更好，且h-域引力度擴展算法劃分的重疊社區(qū)結(jié)構(gòu)與引力度擴展算法劃分的重疊社區(qū)結(jié)構(gòu)效果一樣.在Dolphin、Football、Email網(wǎng)絡(luò)中，引力度擴展算法、h=2與h=3時的h-域引力度擴展算法的EQ值基本上相同，且都比LFM算法的EQ值高.因此，LFM算法對Dolphin、Football、Email網(wǎng)絡(luò)劃分的重疊社區(qū)結(jié)構(gòu)比引力度擴展算法、h-域引力度擴展算法在Bc=0.4時劃分的重疊社區(qū)結(jié)構(gòu)弱，且h-域引力度擴展算法劃分的重疊社區(qū)結(jié)構(gòu)與引力度擴展算法劃分的重疊社區(qū)結(jié)構(gòu)效果基本上一致.

從圖3的(b)可以得出，在Karate、Email網(wǎng)絡(luò)中，引力度擴展算法、h=2與h=3時的h-域引力度擴展算法的EQ值一樣，且都比LFM算法的EQ略低.因此，LFM算法對Karate、Email網(wǎng)絡(luò)劃分的重疊社區(qū)結(jié)構(gòu)比引力度擴展算法、h-域引力度擴展算法在Bc=0.5時劃分的重疊社區(qū)結(jié)構(gòu)質(zhì)量稍微高一些，且h-域引力度擴展算法劃分的重疊社區(qū)結(jié)構(gòu)與引力度擴展算法劃分的重疊社區(qū)結(jié)構(gòu)一樣準(zhǔn)確.在Dolphin、Football網(wǎng)絡(luò)中，引力度擴展算法、h=2與h=3時的h-域引力度擴展算法的EQ值都比LFM算法的EQ值大，即引力度擴展算法、h-域引力度擴展算法在Bc=0.5時對Dolphin、Football網(wǎng)絡(luò)劃分的重疊社區(qū)結(jié)構(gòu)比LFM算法劃分的重疊社區(qū)結(jié)構(gòu)更加明顯.

圖3的(c)是h-域算法在h=2與h=3的EQ比較，h=3，Bc=0.4與h=3，Bc=0.5時，算法在Karate、Dolphin、Football、Email網(wǎng)絡(luò)上獲得的EQ值基本上分別都比h=2，Bc=0.4與h=2，Bc=0.5時獲得的EQ值高；因此，h-域算法在h=3時劃分的重疊社區(qū)結(jié)構(gòu)比h=2時劃分的重疊社區(qū)結(jié)構(gòu)更加準(zhǔn)確，質(zhì)量更高，結(jié)構(gòu)性更強.

2.4 KDD Cup2012數(shù)據(jù)集算法性能分析

圖4是算法的運行時間Time與節(jié)點數(shù)n的關(guān)系圖，橫坐標(biāo)為節(jié)點數(shù)，縱坐標(biāo)為運行時間.

圖4 節(jié)點數(shù)與執(zhí)行時間的關(guān)系圖Fig.4 The execution time of different nodes

由圖4可以看出，隨著同一網(wǎng)絡(luò)節(jié)點數(shù)的增多，LFM算法、引力度擴展算法、h-域引力度擴展算法的運行時間都在增長.其中h-域引力度擴展算法在h=2與h=3時的運行時間比LFM算法、引力度擴展算法的運行時間增加得更緩慢，尤其比引力度擴展算法的運行時間有了數(shù)量級的減少.因此，h-域引力度擴展算法的執(zhí)行效率相對于引力度擴展算法的執(zhí)行效率有了極大的改善.

圖5是算法實驗獲得的EQ值與網(wǎng)絡(luò)節(jié)點數(shù)n的關(guān)系圖，橫坐標(biāo)為節(jié)點數(shù)，縱坐標(biāo)為EQ值.

圖5 節(jié)點數(shù)與EQ的關(guān)系圖Fig.5 The EQ on different nodes

在圖5的(a)中可以看出，引力度擴展算法、h=2與h=3的h-域引力度擴展算法在Bc=0.4時獲得的EQ值總體上比LFM算法的EQ值高，表明引力度擴展算法、h-域引力度擴展算法在Bc取0.4時劃分的重疊社區(qū)結(jié)構(gòu)比LFM算法劃分的重疊社區(qū)結(jié)構(gòu)更具有結(jié)構(gòu)性，質(zhì)量更高.但是，在網(wǎng)絡(luò)規(guī)模為1000時，引力度擴展算法的EQ值比h=2與h=3的h-域引力度擴展算法的EQ值略高，說明此時h-域引力度擴展算法所劃分的重疊社區(qū)結(jié)構(gòu)的準(zhǔn)確度稍微有點降低.

在圖5的(b)中可以看出，引力度擴展算法、h=2與h=3的h-域引力度擴展算法在Bc=0.5時獲得的EQ值總體上比LFM算法的EQ值高，表明引力度擴展算法、h-域引力度擴展算法在Bc取0.5時劃分的重疊社區(qū)結(jié)構(gòu)比LFM算法劃分的重疊社區(qū)結(jié)構(gòu)更加精確.但是，在網(wǎng)絡(luò)規(guī)模為1000時，引力度算法的EQ值比h=2與h=3的h-域引力度算法的EQ值略高，說明此時h-域引力度算法所劃分的重疊社區(qū)結(jié)構(gòu)的結(jié)構(gòu)性仍然有所減弱.

圖5的(c)是h-域引力度擴展算法在同一網(wǎng)絡(luò)中h=2與h=3的算法EQ比較圖，當(dāng)h=2與h=3，在Bc取0.5比Bc取0.4在總體上獲得的EQ值稍高，但在節(jié)點規(guī)模為1000時，Bc取0.4卻比Bc取0.5時的EQ值高，此時h-域算法在Bc=0.4比Bc=0.5劃分的重疊社區(qū)結(jié)構(gòu)質(zhì)量高些.當(dāng)h=3時h-域算法獲得的EQ值基本上比h=2取得的EQ值高，說明h-域算法在h=3時劃分的重疊社區(qū)結(jié)構(gòu)比h=2時劃分的重疊社區(qū)結(jié)構(gòu)更強，結(jié)果更加精準(zhǔn).

3 總結(jié)

本文提出了基于h-域的局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法，將計算節(jié)點的全局引力度值優(yōu)化為計算節(jié)點的h-域引力度值.然后將該算法在實際網(wǎng)絡(luò)上進(jìn)行了測試，并與基于引力度擴展算法、LFM算法做了性能上的對比分析，實驗結(jié)果表明該算法在執(zhí)行效率上比基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法的執(zhí)行效率有了顯著的提高，而且該算法獲得的EQ值總體上并沒降低.因此，局部引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法是有效與可行的.

[1]LESKOVEJ，LANGKL，DASGUPTAA，etal.Communitystructureinlargenetworks:naturalclustersizesandtheabsenceoflargewell-definedclusters[J].InternetMathematics， 2008， 6(1): 29-123．

[2]KUMPULAJM，KIVELAM，KASKIK，etal.Asequentialalgorithmforfastcliquepercolation[J].PhysicalReviewE， 2008， 2(61): 1-9．

[3]ROSVALLM，AXELSSOND，BERGSTROMCT.Themapequation[J].TheEuropeanPhysicalJournal-SpecialTopics， 2009， 178(1): 13-23．

[4]BLONDELVD，GUILLAUMEJL，LAMBIOTTER,etal.Fastunfoldingofcommunitiesinlargenetworks[J].JournalofStatisticalMechanics:TheoryandExperiment， 2008， 10(10): 1-8．

[5] 劉 倩， 劉 群. 基于引力度擴展的疊社區(qū)發(fā)現(xiàn)算法[J]. 計算機工程與設(shè)計， 2014， 35(3): 110-113

[6]GREGORYS.Afastalgorithmtofindoverlappingcommunitiesinnetworks[J].EuropeanConference，ECMLPKDD， 2008， 52(11): 408-423．

[7]LANCICHINETTIA，F(xiàn)ORTUNATOS，KERTESZJ.Detectingtheoverlappingandhierarchicalcommunitystructureincomplexnetworks[J].NewJournalofPhysics， 2009， 11(33): 1-15．

[8]SHENH，CHENGX，CAIK，etal.Detectoverlappingandhierarchicalcommunitystructureinnetworks[J].PhysicaA， 2009， 388(8): 1706-1712．

[9]CHEND，SHANGM，LVZ，etal.Detectingoverlappingcommunitiesofweightednetworksviaalocalalgorithm[J].PhysicaA:StatisticalMechanicsanditsApplications， 2010， 389(19): 4177-4187．

[10] 潘 磊， 金 杰， 王崇駿， 等. 社會網(wǎng)絡(luò)中基于局部信息的邊社區(qū)挖掘[J]. 電子學(xué)報， 2012， 40(11): 2255-2263．

[11] 武志昊， 林友芳， 田盛豐， 等. 高度重疊社區(qū)的社區(qū)合并優(yōu)化算法[J]. 北京交通大學(xué)學(xué)報， 2011， 35(3): 116-122．

Detecting overlapping community by local gravitational degree expansion

SUN Yanwei1， LEI Jianjun1， LIU Qian2

(1.Collaborative Innovation Center in Hubei Province on Basic Education and IT Services，Hubei University of Education， Wuhan 430205; 2.Chongqing Key Laboratory of Computational Intelligence，Chongqing University of Posts and Telecommunications， Chongqing 400065)

Social network has community structure, with some nodes shared by two or more communities, which generates overlapping community structure. In previous work algorithms of overlapping community detection was proposed based on expansion of gravitational degree(GDE), which expanding and finding overlapping communities according to a node with maximal gravitational degree. Here we present an improved algorithm by local gravitational degree expansion based onh-region (LGDE). The experimental results demonstrated that this algrorithm is feasible and its execution efficiency has been raised.

overlapping community; local gravitational degree;h-region; social network; seed expansion

2015-04-22.

湖北省教育廳科學(xué)研究中青年人才項目(Q20153001).

1000-1190(2015)06-0851-06

TP393.0

A

*通訊聯(lián)系人. E-mail: 756652665@qq.com.