局部引力度擴展的重疊社區發現算法

孫延維， 雷建軍*， 劉 倩

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

?

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

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

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

重疊社區； 局部引力度；h-域； 社交網絡； 種子擴展

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

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

1 局部引力度擴展的重疊社區發現算法

給定一個無向、無權網絡G(V，E)，其中V是網絡的節點集，E是網絡的邊集，節點數|V|=n，邊數|E|=m；將網絡中未被劃分到任意一個社區中的節點的劃分狀態標記為‘F’，已經被分配到社區里的節點的劃分狀態標記為‘T’.首先，將網絡中所有節點的劃分狀態初始化為‘F’.

1.1 基于引力度擴展的重疊社區發現算法(GDE)

基于引力度擴展的重疊社區發現算法[5]包含了有序的算法流程，其描述如下.

1)查找初始社區

步驟1：使用計算節點引力度的公式來計算網絡中未被劃分到社區里的節點的引力度值；

步驟2：選取引力度值最大的節點作為發現一個社區的種子；

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

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

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

2)擴展社區

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

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

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

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

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

1.2 節點的h-域

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

(1)

例如，圖1所示的網絡中，橢圓虛線圈畫范圍內的子圖就是節點6的2-域導出子圖，而節點6的2-域導出子圖的節點集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 簡單的網絡圖Fig.1 Illustration of a simple network

1.3 節點的局部引力度

節點u的引力度就是網絡中的節點u與其他節點的引力之和，這是一個全局引力度的概念，其定義為[5]：

(2)

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

(3)

其中，Vu，h是節點u的h-域導出子圖的節點集合，Mu，Mv是網絡節點u、節點v的質量，p(u，v)是節點u與節點v之間的最短距離.

1.4 局部引力度擴展的重疊社區發現算法(LGDE)

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

1)確定社區種子

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

步驟2：查找標記為‘F’的節點集合，將其記為VF；

步驟3：對?v∈VF，利用廣度優先搜索查找節點v在h-域內的節點集合，將其記為Vv，h；

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

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

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

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

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

1.5 局部引力度擴展的重疊社區發現算法的流程圖

圖2是局部引力度擴展的重疊社區發現算法的流程圖，該圖清楚的描述了算法如何確定社區種子，并通過種子節點尋找初始社區，然后擴展初始社區，直到最終挖掘出網絡的重疊社區結構.

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

2 實驗分析

為了測試基于h-域的局部引力度擴展的重疊社區發現算法的可行性與有效性，將算法運用在真實網絡上進行了測試，并與LFM算法[7]、基于引力度擴展的重疊社區發現算法做性能上的對比.

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

2.1 算法評價指標

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

2.1.2評價重疊社區劃分質量的模塊度 本文算法測試的真實社交網絡數據集基本都屬于無先驗知識、無元數據、無類標的網絡數據集.為了衡量本文算法對一個網絡重疊社區結構劃分質量的好壞，仍然采用文獻[8]中提出的擴展模塊度函數EQ(Extend Modularity)來衡量算法劃分的重疊社區結構的質量.

2.2 真實網絡數據集介紹

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

2.3 社交網絡的算法性能分析

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

2.3.2Karate club、Dolphin、Football、Email的運行效率分析 對Karate club、Dolphin、Football、Email社交網進行了算法的真實運行時間分析，其算法的執行效率分析如表1.

表1 算法的執行效率對比表

對表1進行分析可知，LFM算法、基于引力度擴展的重疊社區發現算法、h-域引力度擴展的重疊社區發現算法在Karate club、Dolphin、Football、Email網絡數據集上的運行時間隨著網絡規模的增大都在不斷的增加.其中h-域引力度擴展算法的運行時間比LFM算法、引力度擴展算法的運行時間增加更慢，即h-域引力度擴展算法的執行效率比引力度擴展算法的執行效率獲得了顯著的提高.

2.3.3Karate club、Dolphin、Football、Email重疊社區劃分的準確率分析 算法劃分的重疊社區結構的質量優劣分析如圖3.圖3是算法的EQ值與Social network的關系圖，橫坐標表示社交網絡，縱坐標表示EQ取值.

圖3 Social network與EQ的關系圖Fig.3 Statistics of the EQ for four social network

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

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

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

2.4 KDD Cup2012數據集算法性能分析

圖4是算法的運行時間Time與節點數n的關系圖，橫坐標為節點數，縱坐標為運行時間.

圖4 節點數與執行時間的關系圖Fig.4 The execution time of different nodes

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

圖5是算法實驗獲得的EQ值與網絡節點數n的關系圖，橫坐標為節點數，縱坐標為EQ值.

圖5 節點數與EQ的關系圖Fig.5 The EQ on different nodes

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

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

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

3 總結

本文提出了基于h-域的局部引力度擴展的重疊社區發現算法，將計算節點的全局引力度值優化為計算節點的h-域引力度值.然后將該算法在實際網絡上進行了測試，并與基于引力度擴展算法、LFM算法做了性能上的對比分析，實驗結果表明該算法在執行效率上比基于引力度擴展的重疊社區發現算法的執行效率有了顯著的提高，而且該算法獲得的EQ值總體上并沒降低.因此，局部引力度擴展的重疊社區發現算法是有效與可行的.

[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] 劉 倩， 劉 群. 基于引力度擴展的疊社區發現算法[J]. 計算機工程與設計， 2014， 35(3): 110-113

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

[7]LANCICHINETTIA，FORTUNATOS，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] 潘 磊， 金 杰， 王崇駿， 等. 社會網絡中基于局部信息的邊社區挖掘[J]. 電子學報， 2012， 40(11): 2255-2263．

[11] 武志昊， 林友芳， 田盛豐， 等. 高度重疊社區的社區合并優化算法[J]. 北京交通大學學報， 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.

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

1000-1190(2015)06-0851-06

TP393.0

A

*通訊聯系人. E-mail: 756652665@qq.com.