孫延維， 雷建軍， 楊進才

(1.華中師范大學(xué) 教育信息技術(shù)學(xué)院， 武漢 430079； 2.湖北第二師范學(xué)院 計算機學(xué)院， 湖北 武漢 430205)

基于聯(lián)合引力度擴展的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法

孫延維1，2， 雷建軍2， 楊進才1*

(1.華中師范大學(xué) 教育信息技術(shù)學(xué)院， 武漢 430079； 2.湖北第二師范學(xué)院 計算機學(xué)院， 湖北 武漢 430205)

基于引力度擴展的重疊社區(qū)發(fā)現(xiàn)算法(GDE)，主要用于挖掘無權(quán)社交網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu).真實社區(qū)更多是具有加權(quán)屬性的，本文根據(jù) GDE 算法的種子策略思想，并依據(jù)加權(quán)網(wǎng)絡(luò)的特征，以網(wǎng)絡(luò)節(jié)點的度與強度來綜合確定重疊社區(qū)的中心節(jié)點，提出基于聯(lián)合引力度擴展的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法(UGDE).算法的實驗檢測結(jié)果表明：該算法對劃分加權(quán)網(wǎng)絡(luò)中的重疊社區(qū)具有可行性與有效性.

重疊社區(qū)； 聯(lián)合度； 聯(lián)合引力度； 社區(qū)劃分； 加權(quán)網(wǎng)絡(luò)

復(fù)雜網(wǎng)絡(luò)解析[1-3]的一個重要研究問題就是社區(qū)結(jié)構(gòu)，而重疊社區(qū)結(jié)構(gòu)更能體現(xiàn)現(xiàn)實世界里人們可以自由加入多個團體的實際情況.因此，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)就成為社區(qū)研究的熱點，且這一研究的突破將會對探究人類社會交往方式的進展起到里程碑的推動作用.

如今，已有計算機科學(xué)、統(tǒng)計學(xué)、應(yīng)用數(shù)學(xué)、統(tǒng)計物理領(lǐng)域的科學(xué)工作者們在發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)上做了大量的科研工作，并產(chǎn)生了很多重疊社區(qū)發(fā)現(xiàn)方法.其中有基于適配標簽傳播的ALPA算法[4]，使用鏈路空間變換的LinkSCAN算法[5]，基于邊界非負矩陣三角分解的(BNMTF)方法[6]，邊密度聚類算法 (LDC)[7]，基于馬爾科夫隨機游走控制策略的UEOC方法[8]，通過多目標進化的MEA_CDP算法[9]等.

以上的方法都是針對無權(quán)網(wǎng)絡(luò)的，而真實社會中的個體往往是帶有很多社會交際信息的，這種信息可由復(fù)雜網(wǎng)絡(luò)的邊權(quán)重體現(xiàn)出來，即加權(quán)網(wǎng)絡(luò)更能確切的表達人們的日常活動信息.因此，研究加權(quán)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)具有更大的社會價值.目前，用于挖掘加權(quán)復(fù)雜網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)的算法較少，本文運用GDE算法[10]的種子策略，并根據(jù)加權(quán)網(wǎng)絡(luò)的特性，用節(jié)點的強度與度來聯(lián)合肯定重疊社區(qū)的中心節(jié)點，由此提出基于聯(lián)合引力度擴展的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法(UGDE).

1相關(guān)概念介紹

1.1加權(quán)網(wǎng)絡(luò)節(jié)點的聯(lián)合度

在社交加權(quán)網(wǎng)絡(luò)中，權(quán)值一般代表了節(jié)點聯(lián)系的密切度，節(jié)點間邊的權(quán)重值越大，說明兩個節(jié)點間的日常往來越親密，反之，交往則越稀少.而在加權(quán)網(wǎng)絡(luò)中，根據(jù)節(jié)點間邊的權(quán)值來判斷節(jié)點之間的相互影響力度是無可厚非的，但是節(jié)點與多少個節(jié)點之間有直接交往關(guān)系，也是不容忽略的.因此，衡量加權(quán)網(wǎng)絡(luò)中任意節(jié)點對網(wǎng)絡(luò)中其他節(jié)點的直接影響力的大小不能只單一從權(quán)值判斷，而應(yīng)該將節(jié)點的度與節(jié)點的強度聯(lián)合考慮.

設(shè)定加權(quán)網(wǎng)絡(luò)Gw(Vw，Ew)，其中網(wǎng)絡(luò)節(jié)點集合的數(shù)學(xué)表示為Vw，網(wǎng)絡(luò)邊集合的數(shù)學(xué)表示為Ew.設(shè)定任意節(jié)點a∈Vw，節(jié)點a的聯(lián)合度定義參考文獻[11]，將其定義為：

(1)

式中，ka是節(jié)點a的度，sa是節(jié)點a的強度，β是一個為正數(shù)的調(diào)節(jié)參數(shù)，它將節(jié)點a的度與a的強度聯(lián)合了起來，且β∈[0，1].

1.2加權(quán)網(wǎng)絡(luò)節(jié)點的聯(lián)合隸屬度

設(shè)定一個加權(quán)網(wǎng)絡(luò)Gw(Vw，Ew)，以及Gw中的一個重疊社區(qū)cw∈Cw，Cw是Gw的一個重疊社團劃分，且?a∈Vw，則將節(jié)點a對重疊社區(qū)cw的聯(lián)合隸屬度Bw(a，cw)定義為：

(2)

其中，k(cw)a是節(jié)點a對重疊社區(qū)cw的連接度，s(cw)a是節(jié)點a對重疊社區(qū)cw的連接強度.

1.3加權(quán)網(wǎng)絡(luò)節(jié)點間的最短路徑

一個無向、無權(quán)網(wǎng)絡(luò)G(V，E)，及?a，b∈V，則節(jié)點u與節(jié)點v之間的最短路徑[11]定義為：

d(a，b)=min(Aai+…+Aib)，i∈V,

(3)

其中，i表示a可達b通過的所有中間節(jié)點，Aai是網(wǎng)絡(luò)G的鄰接矩陣A里的元素.

在加權(quán)社會網(wǎng)絡(luò)中，節(jié)點間邊的權(quán)重值一般表示的是節(jié)點間訊息交流的親近程度，而不是節(jié)點間的路徑長度，從理論意義上講，當權(quán)值越大，節(jié)點間消息的互動應(yīng)該更加頻繁，通過彼此影響感染網(wǎng)絡(luò)中的其他節(jié)點的可能性更高，他們的理論路徑應(yīng)該更短.一個加權(quán)網(wǎng)絡(luò)Gw(Vw，Ew)，及?a，p∈Vw，則將節(jié)點a與節(jié)點p之間的加權(quán)最短路徑[11]定義為：

(4)

圖1 簡單的加權(quán)網(wǎng)絡(luò)圖Fig.1 A simple weighted network

1.4加權(quán)網(wǎng)絡(luò)節(jié)點的聯(lián)合引力度

一個加權(quán)網(wǎng)絡(luò)Gw(Vw，Ew)，?a∈Vw，則節(jié)點a的聯(lián)合引力度定義為：

(5)

其中，mw(a)、mw(p) 分別是節(jié)點a、節(jié)點b的加權(quán)質(zhì)量，由文獻[10]可知，mw(a)=Ua，mw(p)=Up.

2基于聯(lián)合引力度擴展的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法

加權(quán)網(wǎng)絡(luò)Gw(Vw，Ew)，對加權(quán)網(wǎng)絡(luò)節(jié)點的歸屬狀態(tài)進行初始化，給?a∈Vw一個原始劃分標記“N”，即節(jié)點a未被指定到重疊社區(qū)里，當節(jié)點a被分派到某個重疊社區(qū)里時，將其節(jié)點的劃分標記更新為“J”.

2.1算法描述

1) 挖掘中心社區(qū)

步驟1：?a∈Vw，且a的劃分標記是‘N’，由式(1)計算出節(jié)點a的聯(lián)合度，式(4)計算出節(jié)點a與其他節(jié)點間的加權(quán)最短路徑，再由式(5)計算出節(jié)點a的聯(lián)合引力度；

步驟2∶Gw中聯(lián)合引力度最大的節(jié)點被指定為一個重疊社區(qū)的種子節(jié)點s；

步驟3：將與種子s是鄰居關(guān)系的節(jié)點集記為VL，?b∈VL，且b的社區(qū)歸屬狀態(tài)為‘N’，則將b加入種子s的社區(qū)里，最終，此類節(jié)點就和s構(gòu)成了中心社區(qū)ch，ch的節(jié)點集記作Vh；

步驟4：?a∈Vh，計算出節(jié)點a的Bw(a，ch)值，若BT>Bw(a，ch)(BT是重疊社區(qū)聯(lián)合隸屬度的門限值)，則在Vh中減除節(jié)點a；

步驟5：回溯至第4步驟，直至?a∈Vh，都滿足BT≤Bw(a，ch)，此時中心社區(qū)ch被明確.

2) 中心社區(qū)的擴展

步驟1：將社區(qū)ch的鄰舍節(jié)點集記作VJ，?b∈VJ，計算其Bw(b，ch)值；

步驟2：設(shè)定一個節(jié)點集VF=?，?b∈VJ，若BT≤Bw(b，ch)，將節(jié)點b加入到VF中，即VF=VF+；

步驟3：若VF≠?，則社團ch里就增加VF中的節(jié)點集，這樣就組成了一個具有更多成員的社區(qū)ch，回溯至第1步驟；

步驟4：若VF=?，一個加權(quán)網(wǎng)絡(luò)重疊社區(qū)ch就被確定與發(fā)現(xiàn).

2.2UGDE算法流程

圖2是基于聯(lián)合引力度擴展的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法的流程圖，該圖詮釋了UGDE算法怎樣劃分出加權(quán)網(wǎng)絡(luò)中的一個重疊社區(qū)，并直到整個加權(quán)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)被發(fā)現(xiàn).

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

3實驗分析

將基于聯(lián)合引力度擴展的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法在實際的加權(quán)網(wǎng)絡(luò)上進行實驗，以檢測該算法的有效性與可行性.本文還將該算法與EM-BOAD算法[12]、LOC算法[13]做了執(zhí)行效率與重疊社區(qū)結(jié)構(gòu)劃分質(zhì)量上的比較.

3.1算法執(zhí)行效率的理論分析與比較

本文的UGDE算法計算加權(quán)網(wǎng)絡(luò)任意節(jié)點對之間的帶權(quán)最短路徑長度的時間復(fù)雜度是O(n3)，導(dǎo)致算法執(zhí)行性能較差，因而UGDE算法的時間復(fù)雜度在最優(yōu)情況，即網(wǎng)絡(luò)中只存在一個社區(qū)時，是O(n3)；而最差情況，即每個節(jié)點自成一個社區(qū)時，是O(n4)，n是網(wǎng)絡(luò)的節(jié)點個數(shù).EM-BOAD算法的時間復(fù)雜度最優(yōu)情況是O(n)，最差情況是O(n2).LOC算法的時間復(fù)雜度最優(yōu)情況是O(n2)，最差情況是O(n3).

從以上分析可知，UGDE算法的時間復(fù)雜度是三者中最高的.因此，本文借鑒六度分割理論[14]的思想(地球上任意兩個人之間要產(chǎn)生聯(lián)系，平均中間只需要通過5個人就可以了)對該算法進行優(yōu)化.文中將網(wǎng)絡(luò)中任意節(jié)點的全局加權(quán)引力度優(yōu)化為計算以該節(jié)點為起始節(jié)點，并通過5個節(jié)點內(nèi)可達的全部節(jié)點的局部加權(quán)引力度.則UGDE算法的時間復(fù)雜度在最好情況，就變?yōu)镺(n2)；而最差情況則變?yōu)镺(n3).

3.2加權(quán)網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)質(zhì)量函數(shù)模塊度

當在不知曉一個網(wǎng)絡(luò)的實際社區(qū)結(jié)構(gòu)的情形下，通常采用模塊度函數(shù)來判斷實驗環(huán)境下獲得的社區(qū)結(jié)構(gòu)的質(zhì)量如何.本文采用文獻[13]中的模塊度Qo，該指標是專門針對評估加權(quán)網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)質(zhì)量的優(yōu)劣而提出的模塊度函數(shù).Qo的定義為：

(6)

其中,w表示加權(quán)網(wǎng)絡(luò)的連接邊的權(quán)重總和，wab表示加權(quán)矩陣W的元素,

(7)

3.3實際加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集

本文實驗的實際數(shù)據(jù)集有Zachary’skarateclub[15]，lesmis[16]，netscience[17]，astro-ph.其中l(wèi)esmis是法國大作家維克多·雨果在1862年發(fā)表的小說《悲慘世界》中人物之間的關(guān)系網(wǎng)絡(luò)，該網(wǎng)絡(luò)含有77個人物節(jié)點，254條帶權(quán)人物關(guān)系邊，邊上的權(quán)值表示了某對人物在小說同一章節(jié)出現(xiàn)的次數(shù).netscience是科學(xué)家在網(wǎng)絡(luò)理論與實驗研究這一領(lǐng)域的合作關(guān)系網(wǎng)絡(luò)，其中有1 600個研究者節(jié)點，2 743條賦權(quán)關(guān)系邊，邊權(quán)重表明某兩位學(xué)者共同合作研究的頻率大小.astro-ph是學(xué)者在天體物理學(xué)這一領(lǐng)域的協(xié)作關(guān)系網(wǎng)絡(luò).

3.3.1參數(shù)β取值討論 本文算法中的正數(shù)調(diào)節(jié)參數(shù)β值的設(shè)置參考文獻[11]，將β的值定為0.5，重疊社區(qū)歸屬閥值BT仍采用文獻[10]中的取值.

為了驗證β取0.5時，本文算法是否能得到最優(yōu)結(jié)果，我們在實驗中做了檢驗，且β的增加步長設(shè)置為0.1，其測試結(jié)果如圖3所示.

圖3為參數(shù)β與加權(quán)網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)質(zhì)量評價指標Qo之間的關(guān)系圖.解析圖3可知，當β為0.5時，Qo值最大，此時UGDE算法在Karate、lesmis、netscience網(wǎng)絡(luò)上獲得的加權(quán)重疊社區(qū)結(jié)構(gòu)的質(zhì)量最佳，結(jié)構(gòu)性最強.因此，β應(yīng)該設(shè)定為0.5.

圖3 β與Qo的關(guān)系圖Fig.3 The relationship between β and weighted modularity Qo

3.3.2算法對karateclub的重疊社區(qū)劃分 由于karateclub只有34個成員節(jié)點，78條有權(quán)關(guān)系邊，它的網(wǎng)絡(luò)規(guī)模就比較小，可顯而易見的從網(wǎng)絡(luò)可視化角度來清楚的分析其重疊社區(qū)劃分結(jié)果.karateclub的帶權(quán)重疊社區(qū)結(jié)構(gòu)如圖4.圖4為Zachary’skarateclub的加權(quán)重疊社區(qū)劃分結(jié)構(gòu)圖，其中的(1)、(2)子圖分別是閥門參數(shù)BT=0.5與BT=0.4的重疊社區(qū)結(jié)構(gòu)圖.由圖中可知，本文算法將karate club劃分成2個加權(quán)重疊社區(qū)，兩個子圖中重疊社區(qū)的種子都是節(jié)點1與節(jié)點34，而(1)子圖中的重疊節(jié)點是3，(2)子圖中的重疊節(jié)點是9、3、14.該俱樂部實際也是以節(jié)點1與節(jié)點34為核心領(lǐng)導(dǎo)人物被劃分成了兩個團體，由此可知本文算法在karate club上劃分的加權(quán)重疊社區(qū)結(jié)構(gòu)具有較好的準確性.

圖4 Karate club加權(quán)社交網(wǎng)絡(luò)的重疊社區(qū)劃分圖Fig.4 The overlapping community structure of karate club weighted network

3.3.3算法在karate club、lesmis、netscience上的運行效率分析與對比

表1 EM-BOAD、LOC、UGDE的運行效率對比表

表1是算法的運行效率對比表，對其進行解析，將EM-BOAD算法、LOC算法、UGDE算法在加權(quán)網(wǎng)絡(luò)karate、lesmis、netscience上測試時，所耗費的運行時間都與網(wǎng)絡(luò)的規(guī)模成正比關(guān)系，即網(wǎng)絡(luò)規(guī)模擴大，運行時間也加增.其中，EM-BOAD算法的時間花費代價最小，而本文提出的UGDE算法的運行時間相對最多，即該算法的運行效率是三者中最差的.

3.3.4算法在karate club、lesmis、netscience上的加權(quán)模塊度對比

表2 EM-BOAD、LOC、UGDE的Qo對比表

表2是算法的Qo對比表，由對表2的剖析可得，在加權(quán)網(wǎng)絡(luò)karate、lesmis、netscience上實驗獲取的加權(quán)模塊度函數(shù)值中，EM-BOAD算法的Qo表現(xiàn)最差，即劃分的重疊社區(qū)結(jié)構(gòu)的結(jié)構(gòu)化程度是三個算法中最低的；在karate、lesmis網(wǎng)絡(luò)中，UGDE算法的Qo值都優(yōu)于LOC算法的Qo值，此時UGDE發(fā)現(xiàn)的重疊社區(qū)結(jié)構(gòu)的質(zhì)量比LOC要好；而在netscience網(wǎng)絡(luò)中，UGDE算法的加權(quán)模塊度函數(shù)Qo值卻微小于LOC算法的Qo值，即此時UGDE算法劃分的重疊社區(qū)結(jié)構(gòu)的模塊化水平低于LOC.

3.3.5算法在astro-ph加權(quán)網(wǎng)絡(luò)上的性能分析 本文在astro-ph這個大型的加權(quán)關(guān)系網(wǎng)絡(luò)中獲取不同規(guī)模的數(shù)據(jù)集進行測試，仍將UGDE算法與EM-BOAD算法、LOC算法的實驗結(jié)果作比較，從而更加確切地解析本文算法的性能.圖5是網(wǎng)絡(luò)規(guī)模與算法運行時間的關(guān)系圖；圖6是網(wǎng)絡(luò)規(guī)模與加權(quán)模塊度的關(guān)系圖，其中網(wǎng)絡(luò)規(guī)模由橫坐標表示，加權(quán)模塊度由縱坐標表示.

圖5 網(wǎng)絡(luò)規(guī)模與運行時間的關(guān)系圖Fig.5 The relationship between network size and runtime

圖6 網(wǎng)絡(luò)規(guī)模與加權(quán)模塊度Qo的關(guān)系圖Fig.6 The relationship between network size and weighted modularity Qo

對圖5進行解析，當astro-ph加權(quán)網(wǎng)絡(luò)被用于實驗測試的數(shù)據(jù)量按固定規(guī)模逐漸增加，EM-BOAD算法、LOC算法、UGDE算法的運行時間同時呈現(xiàn)出逐漸上升趨勢，但本文的UGDE算法的時間遞增相對速度最快，消耗的時間最多，執(zhí)行效率相對較低.

對圖6進行剖析可知， EM-BOAD算法、LOC算法、UGDE算法獲得的加權(quán)模塊度值與網(wǎng)絡(luò)規(guī)模成反比關(guān)系，即隨著astro-ph加權(quán)網(wǎng)絡(luò)的節(jié)點個數(shù)遞增，算法的Qo值卻呈現(xiàn)出遞減趨勢.其中EM-BOAD的Qo值變小的速率最高，其劃分效果最差，本文UGDE算法在節(jié)點數(shù)量從1 000按1 000節(jié)點的規(guī)模遞增至5 000獲得的Qo值都是三個算法中最良好的，但網(wǎng)絡(luò)節(jié)點個數(shù)在5 000以上，UGDE算法的Qo值相對比LOC的Qo值略小.由此可知，UGDE算法劃分的加權(quán)網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)具有較好的結(jié)構(gòu)性與準確性，但在達到一定規(guī)模以上的大型網(wǎng)絡(luò)中，其劃分的重疊社區(qū)結(jié)構(gòu)的結(jié)構(gòu)性相對稍弱于LOC算法.

4總結(jié)

本文提出了基于聯(lián)合引力度擴展的加權(quán)網(wǎng)絡(luò)重疊社區(qū)劃分算法，將帶權(quán)節(jié)點的度與強度聯(lián)合起來決定節(jié)點在加權(quán)網(wǎng)絡(luò)中的影響力.在具體的加權(quán)網(wǎng)絡(luò)上將算法做了運用測試，測試結(jié)果闡明UGDE算法花費的時間代價相對較高，該算法在實驗的各個加權(quán)網(wǎng)絡(luò)中獲得的Qo值總體上大于EM-BOAD、LOC算法的Qo值，但仍有稍小于LOC算法的加權(quán)模塊度值的情形，從而表明本文算法在劃分加權(quán)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)上是有效可行的.我們后期研究工作將致力于進一步降低UGDE算法的運行時間，并改善本文算法在大型加權(quán)網(wǎng)絡(luò)上發(fā)現(xiàn)的重疊社區(qū)結(jié)構(gòu)的質(zhì)量.

[1] JIERUI X， STEPHEN K， BOLESLAW K. Overlapping community detection in networks: the state-of-the-art and comparative study[J]. ACM Computing Surveys， 2013， 45(4): 1-43.

[2] BOSCHLOO L， SCHOEVER R， BORKULO C， et al. The network structure of psychopathology in a community sample of preadolescents[J]. Journal of Abnormal Psychology， 2016， 125(4): 599-606.

[3] PREM K， DAVID M. Efficient discovery of overlapping communities in massive network[J]. Proceeding of the National Academy of Sciences of the United States of America， 2013， 110(36): 4534-4539．

[4] CHUNYING L， YONGHANG H， ZHIKANG T， et al. Adaptive label propagation algorithm to detect overlapping community in complex networks[J]. International Journal of Future Generation Communication and Networking， 2016， 9(8): 317-326．

[5] SUNGSU L， SEUNGWOO R， SEJEONG K， et al. LinkSCAN: Overlapping community detection Using the link-space transformation[J]. ICDE， 2014， 30: 292-303．

[6] YU Z， DIY-YAN Y. Overlapping community detection via bounded nonnegative matrix tri-factorization[J]. ACM New York， 2012， 12(8): 606-614.

[7] HUANG L， GUISHEN W， WEI P， et al. A link density clustering algorithm based on automatically selecting density peaks for overlapping community detection[J]. International Journal of Modern Physics， 2016， 30(8): 1-15.

[8] DI J， BO Y， CARLOS B， et al. Markov random walk under constraint for discovering overlapping communities in complex networks[J]. Journal of Statistical Mechanics: Theory and Experiment， 2011， 31(5): 1-22．

[9] JING L， WEICAI Z， HUSSEIN A， et al. Separated and overlapping community detection in complex networks using multi-objective evolutionary algorithms[J]. IEEE Congress on Evolutionary Computation， 2010， 8: 1-7.

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

[11] OPSAHL T， AGNEESSENS F， SKVORETZ J. Node centrality in weighted networks: generalizing degree and shortest paths[J]. Social Networks， 2010， 32(3): 245-251．

[12] JUNQIU L， XINGYUAN W， JUSTINE E. Detecting overlapping communities by seed community in weighted complex networks[J]. Physica A， 2013， 23(392): 6125-6134．

[13] CHEN D， SHANG M， LYU 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．

[14] 喬秀全， 楊 春， 李曉峰， 等. 社交網(wǎng)絡(luò)服務(wù)中一種基于用戶上下文的信任度計算方法[J]. 計算機學(xué)報， 2011， 34(12): 2403-2413.

[15] 鹿 靜， 徐 勇， 安麗平. 基于節(jié)點相似度的加權(quán)網(wǎng)絡(luò)社團結(jié)構(gòu)劃分算法[J]. 信息與控制， 2012， 4(41): 504-508．

[16] 呂天陽， 謝文艷， 鄭偉民， 等. 加權(quán)復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)的評價指標及其發(fā)現(xiàn)算法分析[J].物理學(xué)報， 2012， 21(61): 1-10．

[17] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E， 2006， 74(3): 1-22．

Overlapping community detection algorithm based on expansion of union gravitational degree in weighted networks

SUN Yanwei1，2， LEI Jianjun2， YANG Jincai1

(1.School of Education Information Technology, Central China Normal University, Wuhan 430079; 2.School of Computer Science， Hubei University of Education， Wuhan 430205)

The overlapping community detection algorithm based on expansion of gravitational degree, which is mainly used to excavate overlapping community structure in social networks, is applied to un-weighted networks. Real community is more with weighted attributes, according to the seed strategy of GDE, and based on the characteristics of the weighted network, the core node of a community is able to be determined by its degree and strength. Here the over overlapping community detection algorithm based on expansion of union gravitational degree in weighted networks (UGDE) is proposed. According to experimental results, it demonstrates that the algorithm is efficient and feasible for detecting overlapping communities in weighted networks.

overlapping community; union degree; union gravitational degree; community detection; weighted network

2016-11-12.

國家社會科學(xué)基金項目(14BYY093).

10.19603/j.cnki.1000-1190.2017.04.004

1000-1190(2017)04-0435-06

TP393

A

*通訊聯(lián)系人. E-mail: jcyang@mail.ccnu.edu.cn.