一種加權(quán)復雜網(wǎng)絡中社團發(fā)現(xiàn)的凝聚算法

張 昕,楚善增,姚友娟,張 瑜,李曉光

(遼寧大學 信息學院,沈陽 110036) E-mail:xgli@lnu.edu.cn

1 引 言

現(xiàn)實世界中的許多系統(tǒng)都是以復雜網(wǎng)絡的方式呈現(xiàn),如電力網(wǎng)絡、交通網(wǎng)絡、社會網(wǎng)絡以及互聯(lián)網(wǎng)等,它們不僅具有小世界與無標度等結(jié)構(gòu)復雜性,還表現(xiàn)出動態(tài)演化、連接多樣性以及節(jié)點多樣性等諸多復雜性質(zhì).社團結(jié)構(gòu)[1]是復雜網(wǎng)絡眾多重要特性之一,而根據(jù)網(wǎng)絡中所蘊含的信息解析出有價值的社團拓撲結(jié)構(gòu),即社團發(fā)現(xiàn)則是復雜網(wǎng)絡研究領(lǐng)域中的一個重要方面,不僅具有重要的理論價值,對于許多現(xiàn)實系統(tǒng)還有廣泛的應用前景[2-4].

社團發(fā)現(xiàn)算法一直備受眾多研究人員的關(guān)注,如GN算法[5]、譜分析算法[6]、層次聚類算法[7]以及一些綜合多種思想的算法[8,9]等.另外,還有部分工作重點針對重疊社區(qū)的發(fā)現(xiàn),如基于團滲理論的CPM算法[10]、基于局部擴展的LFM算法[11]、基于集成網(wǎng)絡的UEOC算法[12]以及基于連接劃分的邊社區(qū)發(fā)現(xiàn)算法[13]等.但現(xiàn)有研究大多是針對無權(quán)網(wǎng)絡,而相比于無權(quán)網(wǎng)絡,現(xiàn)實系統(tǒng)更適合抽象為加權(quán)網(wǎng)絡.例如交通網(wǎng)絡中,道路的運輸能力自然可以作為邊的權(quán)值;在人際關(guān)系網(wǎng)絡中,則可以將關(guān)系的緊密程度作為權(quán)值,能夠更為直觀、準確的反映網(wǎng)絡中人與人之間的聯(lián)系情況.而且,不同于機會網(wǎng)絡中的不確定連接[14],大多數(shù)現(xiàn)實系統(tǒng)中的節(jié)點關(guān)系普遍較為穩(wěn)定.因此,加權(quán)網(wǎng)絡相關(guān)研究顯然具有更好的應用價值.

目前針對加權(quán)網(wǎng)絡的社團結(jié)構(gòu)發(fā)現(xiàn)研究較少[15],典型的成果有CNM算法[16]、WGN算法[17]和Newman快速算法(FN算法)[18].CNM算法基于堆的數(shù)據(jù)結(jié)構(gòu)來計算和更新網(wǎng)絡的模塊性上提出的一種新的貪心算法,該算法雖然在模塊度增量矩陣△Q、最大堆H以及輔助變量a三種數(shù)據(jù)結(jié)構(gòu)的基礎上節(jié)省了存儲空間,使其時間復雜度接近于線性,但只適用于對準確度要求不是非常嚴格的復雜系統(tǒng)中.

WGN算法(加權(quán)的GN算法)是對GN算法的一種改進.由于該算法是通過不斷的計算網(wǎng)絡中每條邊的介數(shù),找出并刪除其中介數(shù)最大的邊之和,需要再重新計算各邊的介數(shù)值,以至于該算法的時間復雜度較高,最差情況下為O(m2n),其中m為邊數(shù),n為節(jié)點數(shù),因此該算法只適用于節(jié)點數(shù)量相對較少的中小規(guī)模的網(wǎng)絡中.

Newman快速算法(FN算法)基于貪婪算法的思想,首先將網(wǎng)絡中的每個節(jié)點看成是一個單獨的社團,在計算出的網(wǎng)絡中每個節(jié)點對的相似性的基礎上進行合并,其時間復雜度為O(n2).該算法對于大規(guī)模網(wǎng)絡下的社團劃分具有優(yōu)良的性能,但精確度略低于GN算法.

現(xiàn)有加權(quán)網(wǎng)絡社團發(fā)現(xiàn)算法基本上是對無權(quán)網(wǎng)絡社團結(jié)構(gòu)發(fā)現(xiàn)算法的一種調(diào)整或修改,這種細微的改變對加權(quán)網(wǎng)絡社團結(jié)構(gòu)的刻畫較為淺顯,對應的社團發(fā)現(xiàn)能力也十分有限.本文在現(xiàn)有研究工作基礎上,提出一種改進的加權(quán)網(wǎng)絡社團結(jié)構(gòu)定義,更為符合現(xiàn)實網(wǎng)絡中社團的實際情況,并進一步提出了一種新的加權(quán)網(wǎng)絡社團發(fā)現(xiàn)算法,能夠更為準確有效的發(fā)現(xiàn)加權(quán)網(wǎng)絡中的社團結(jié)構(gòu).

2 加權(quán)網(wǎng)絡社團結(jié)構(gòu)定義

合理準確的社團結(jié)構(gòu)定義對于網(wǎng)絡建模、社團結(jié)構(gòu)評價以及社團發(fā)現(xiàn)算法來說,都是必要的前提,更是進一步研究工作的基礎.現(xiàn)有的研究工作中,基于相對連接頻數(shù)的強/弱社團定義是一種比較普遍的形式.本節(jié)分析該類定義在無權(quán)網(wǎng)絡與加權(quán)網(wǎng)絡上的對比差異,并給出改進的加權(quán)網(wǎng)絡強/弱社團定義.

2.1 目前加權(quán)網(wǎng)絡社團結(jié)構(gòu)定義

圖1為無權(quán)網(wǎng)絡中的強弱社團示意圖,圖中左部空心節(jié)點構(gòu)成的子圖為強社團,而在右部實心節(jié)點構(gòu)成的子圖中,節(jié)點v1與節(jié)點v2不滿足強社團條件,因此右部子圖為弱社團.

圖1 無權(quán)網(wǎng)絡中強/弱社團Fig.1 Strong/weak community in unweighted network

圖2 加權(quán)網(wǎng)絡中強/弱社團Fig.2 Strong/weak community in weighted network

圖2為加權(quán)網(wǎng)絡中的強弱社團示意圖,左部空心節(jié)點構(gòu)成的子圖與右部實心節(jié)點構(gòu)成的子圖均為強社團.該結(jié)論和無權(quán)網(wǎng)絡情況下的社團結(jié)構(gòu)劃分存在差別.

考慮社團的本質(zhì)含義,即社團內(nèi)節(jié)點間連接緊密而社團間的連接稀疏,顯然節(jié)點的度是決定社團結(jié)構(gòu)及性質(zhì)的主導因素,而節(jié)點間連接的權(quán)重是次要因素.由于加權(quán)網(wǎng)絡中綜合考查了連接權(quán)重,其社團形成條件較之無權(quán)網(wǎng)絡更為嚴格,因此同結(jié)構(gòu)的加權(quán)網(wǎng)絡與無權(quán)網(wǎng)絡中社團發(fā)現(xiàn)的結(jié)果應一致,或無權(quán)網(wǎng)絡中的強社團由于權(quán)重的影響退化為弱社團.因此可以看出,上述加權(quán)網(wǎng)絡社團劃分條件過度強調(diào)了權(quán)重對社團的影響,弱化了節(jié)點度的影響,使得結(jié)果與社團本質(zhì)含義存在偏差.

2.2 改進的加權(quán)網(wǎng)絡社團結(jié)構(gòu)定義

(1)

綜合考慮連接權(quán)重以及節(jié)點度對社團的影響,給出改進后的加權(quán)網(wǎng)絡中強/弱社團定義如下:

圖2所示加權(quán)網(wǎng)絡,按上述定義進行社團劃分,則圖中左部社團為強社團,右部社團為弱社團結(jié)構(gòu),與無權(quán)網(wǎng)絡中的劃分結(jié)果一致.由此可見,本文定義利用節(jié)點度和權(quán)重同時對社團結(jié)構(gòu)進行約束,較原有加權(quán)網(wǎng)絡社團發(fā)現(xiàn)條件更為合理.

以圖3所示Zachary空手道俱樂部網(wǎng)絡[19]為例,進一步驗證本文定義的合理性.該網(wǎng)絡體現(xiàn)了美國某大學的空手道俱樂部會員之間的社交關(guān)系,包含34個節(jié)點以及78條邊,劃分為2個社團,是復雜網(wǎng)絡社團劃分算法準確性衡量的一個代表性數(shù)據(jù)集.圖3中包含兩個已知的社團,節(jié)點顏色的深淺代表其社團歸屬,節(jié)點間連線上的數(shù)字表示權(quán)重.

圖3 空手道俱樂部網(wǎng)絡Fig.3 Zachary network

根據(jù)社團所屬情況以及連接的權(quán)重信息,可以得出各項統(tǒng)計值如表1所示.

表1 空手道俱樂部網(wǎng)絡社團統(tǒng)計量
Table 1 Community statistic in Zachary network

統(tǒng)計量∑kin∑kout∑sin∑soutwinwout社團166101992632.6社團26910219223.22.2

首先忽略連接的權(quán)重信息,按無權(quán)網(wǎng)絡對圖3進行分析.圖中節(jié)點3的kin=kout=5,因此社團1不滿足強社團條件,但從社團1整體來看,有∑kin=66>∑kout=10,因此社團1為弱社團.圖中節(jié)點10的kin=kout=1,因此社團2不滿足強社團條件,但從社團2整體來看,有∑kin=69>∑kout=10,因此社團2也為弱社團.

然后依據(jù)原有加權(quán)網(wǎng)絡強/弱社團劃分條件,按加權(quán)網(wǎng)絡對圖3進行分析.顯然,社團1與社團2中每個節(jié)點均有sin>sout,因此二者均為強社團,與無權(quán)網(wǎng)絡分析所得結(jié)論矛盾.由此可以看出,原有加權(quán)網(wǎng)絡強/弱社團劃分條件中權(quán)重的影響力過大,弱化了節(jié)點度作為社團結(jié)構(gòu)的主要影響因素的作用,因此其合理性不足.

3 加權(quán)網(wǎng)絡中社團發(fā)現(xiàn)算法

結(jié)合現(xiàn)有社團層次凝聚思想,以本文給出的加權(quán)網(wǎng)絡社團定義為基礎,給出相關(guān)度量指標,并進一步提出一種新的社團發(fā)現(xiàn)算法(ER-NE算法),能夠更為準確的發(fā)現(xiàn)加權(quán)網(wǎng)絡中的強/弱社團結(jié)構(gòu).

3.1 關(guān)聯(lián)性及有效性指標

層次凝聚思想中,典型的社團歸屬判定條件具有傳遞性,即節(jié)點1與節(jié)點2歸屬同一社團,且節(jié)點2與節(jié)點3歸屬同一社團,則節(jié)點1與節(jié)點3也歸屬同一社團.這種傳遞性并不嚴謹,特別是對于大多具有社團重疊特征的實際網(wǎng)絡來說,多個節(jié)點是否屬于同一社團需要分別判定.為避免傳遞性質(zhì)出現(xiàn),并充分體現(xiàn)本文社團定義中對連接權(quán)重及節(jié)點度的綜合考慮,給出ER-NE算法中相關(guān)指標的定義如下:

定義3.(邊社團關(guān)聯(lián)性ER)邊社團關(guān)聯(lián)性表示邊在其兩端點各自鄰域內(nèi)權(quán)重比例的均值,節(jié)點vi與vj間的關(guān)聯(lián)性大小記作ERij,具體計算方法如式(2)所示:

重視培養(yǎng)學生的能力，一直是我國基礎教育改革與發(fā)展的重要目標。對于能力的培養(yǎng)，既有一般目標，也有各自學科的特殊要求和特殊問題。教育不能只滿足知識的傳遞，而是應該將重點放在提高學生能力的培養(yǎng)上，才能將“知識”轉(zhuǎn)變?yōu)椤爸腔邸?，才是素質(zhì)教育的應有之義。

(2)

式(2)中Ni與Nj分別表示節(jié)點vi與節(jié)點vj的鄰域,wij表示連邊權(quán)重,若節(jié)點vi與vj不相鄰,則ERij=0.

邊社團關(guān)聯(lián)性描述了兩個相連節(jié)點之間關(guān)聯(lián)性的大小.根據(jù)本文給出的加權(quán)網(wǎng)絡中的社團定義,社團內(nèi)部節(jié)點間連邊的數(shù)量與權(quán)重之和都要大于社團內(nèi)部節(jié)點與外部節(jié)點的連邊.由式(2)可以看出,節(jié)點間連邊的權(quán)重越大,節(jié)點的度值越小,則相連的兩節(jié)點之間的關(guān)聯(lián)性就越大,體現(xiàn)了權(quán)重與節(jié)點度的雙重因素.若節(jié)點v與社團C內(nèi)節(jié)點的累積關(guān)聯(lián)性越大,則節(jié)點v屬于社團C的可能性越高,由此定義節(jié)點社團有效性如下:

(3)

節(jié)點社團有效性表示一個節(jié)點加入社團后,該社團仍然成立的可能性.由式(3)可以看出,節(jié)點社團有效性取決于該節(jié)點對社團內(nèi)節(jié)點的累計關(guān)聯(lián)性占該節(jié)點整個鄰域內(nèi)的累積關(guān)聯(lián)性之比,即社團有效性的值越大,則節(jié)點與社團內(nèi)部節(jié)點的關(guān)聯(lián)性越高.同時,這種關(guān)聯(lián)性是由式(3)定義的,既符合社團內(nèi)部連接緊密的基本要求,又滿足本文對權(quán)重與節(jié)點度的雙重考慮,能夠有效的刻畫節(jié)點屬于符合本文定義社團的可能性.

3.2 算法描述

本節(jié)給出在網(wǎng)絡中發(fā)現(xiàn)符合本文定義社團結(jié)構(gòu)的算法——ER-NE算法.在進行社團劃分之前,可能已知部分相關(guān)信息,如網(wǎng)絡中社團數(shù)量、某對節(jié)點屬于同一社團等.這些信息稱作先驗信息集,若先驗信息集存在,則算法可以根據(jù)該信息集確定部分初始動作.算法具體描述如下,若先驗信息未知,則其中輸入信息k值為0,H為空.

輸入:原始加權(quán)網(wǎng)絡G,已知的社團數(shù)量k,已知節(jié)點對同屬信息H

輸出:劃分所得社團集合C

1 ifk==0

//flag標記k初始是否為0,其初始值為false

3 計算鄰接ER矩陣;

4C=?;

5 while |C|

6 選取剩余部分中ER值最大的節(jié)點對→C;

//剩余部分是指不包含在社團中的部分

7 if 社團之間存在重疊節(jié)點

8 合并重疊社團;

9 for 所有社團Ci∈C

10 forCi所有鄰接點v

11 ifNE(v,Ci)>0.5

12v→Ci;

13 ifflag

14 for 所有社團Ci∈C

15 if 社團之間存在重疊節(jié)點&&合并后符合本文定義

16 合并重疊社團;

17 ifH≠?

18 forH中所有節(jié)點對

19 ifvi(或vj)已存在于某社團

20vj→vi所在社團(或vi→vj所在社團)

21 for 所有剩余節(jié)點v

22 forv所有鄰接社團Ci

23 計算NE(v,Ci)

24v→Cmax;

//Cmax為NE(v,Ci)值最大的社團

25 ifv∈H

26v的關(guān)聯(lián)節(jié)點→Cmax;

//v的關(guān)聯(lián)節(jié)點為H中已知與v屬于同一社團的節(jié)點

27 if 存在剩余節(jié)點

28 goto 步驟21

29 returnC

算法中步驟1-2判斷社團數(shù)量是否已知,并設置標志位,若社團數(shù)量未知,則置初始社團數(shù)量為網(wǎng)絡中節(jié)點數(shù)量的平方根.步驟3-4初始化社團集合為空,并根據(jù)輸入的網(wǎng)絡數(shù)據(jù)計算鄰接ER矩陣.

步驟5-8以ER值最大的節(jié)點對為基礎構(gòu)建初始社團,若這些節(jié)點對直接相連,則將其合并,并依據(jù)ER值排序補充新的初始社團.

步驟9-12在現(xiàn)有社團的鄰域內(nèi)選擇NE大于0.5的節(jié)點,將其劃分至對應社團.按式(3)給出的節(jié)點社團有效性定義來看,節(jié)點的NE值大于0.5意味著其社團內(nèi)部關(guān)聯(lián)性大于外部關(guān)聯(lián)性,該節(jié)點的社團歸屬已經(jīng)確定.可能存在對于多個社團的NE值均超過0.5的節(jié)點,這部分節(jié)點為社團間重疊節(jié)點.

步驟13-16考慮社團數(shù)量未知的情況下,初始社團數(shù)量設置較大,因此根據(jù)之前步驟所得重疊節(jié)點信息,將符合本文定義的重疊社團合并.

步驟17-20考慮先驗信息中的節(jié)點對同屬信息,若同屬節(jié)點對中,存在已確定歸屬社團的節(jié)點,則節(jié)點對中另一節(jié)點也劃分至該社團.

步驟21-28處理剩余無社團歸屬的節(jié)點.步驟21-26遍歷這部分節(jié)點,計算每個節(jié)點與相鄰社團的NE值,將該節(jié)點劃分至NE值最大的社團中.若存在節(jié)點對同屬信息,則劃分操作時需考慮該節(jié)點的關(guān)聯(lián)節(jié)點,將其一并劃分至該社團.步驟27-28判斷是否仍存在無社團歸屬的節(jié)點,對其進行再次遍歷,直至無剩余節(jié)點.

最后步驟29返回所得社團劃分結(jié)果.

4 實驗分析

4.1 ER-NE算法有效性驗證

本節(jié)通過對Zachary 空手道俱樂部網(wǎng)絡進行社團劃分驗證ER-NE算法的有效性.算法首先計算Zachary 空手道俱樂部網(wǎng)絡的鄰接ER矩陣,如表2所示,計算結(jié)果保留兩位小數(shù).

表2 空手道俱樂部網(wǎng)絡鄰接ER矩陣
Table 2 AdjacentERmatrix of Zachary network

算法對空手道俱樂部網(wǎng)絡的劃分結(jié)果為2個社團,其中社團1包含的節(jié)點集為:

(1,2,3,4,5,6,7,8,9,11,12,13,14,17,18,20,22,31)

社團2包含的節(jié)點集為:

(3,9,10,15,16,19,21,23,24,25,26,27,28,29,30,31,32,33,34)

該劃分結(jié)果無剩余節(jié)點,所得社團數(shù)量與實際社團數(shù)量相同.與實際社團所包含節(jié)點集相比,社團1中多了節(jié)點9和節(jié)點31,社團2中多了節(jié)點3,且這3個節(jié)點在2個社團中均有出現(xiàn),為劃分社團所得重疊節(jié)點.在實際社團劃分中,并未考慮重疊節(jié)點,而通過對實際網(wǎng)絡的觀察,可以發(fā)現(xiàn)節(jié)點3、節(jié)點9以及節(jié)點31與2個社團聯(lián)系均較緊密,可見ER-NE算法對重疊節(jié)點的判斷比較準確.同時,算法所得社團中的非重疊部分與實際社團一致,因此說明ER-NE算法在考慮節(jié)點重疊的同時,保證了社團劃分的準確性.

4.2 ER-NE算法優(yōu)越性驗證

本文進一步對比ER-NE算法和其他經(jīng)典算法在典型數(shù)據(jù)集上的實驗結(jié)果,驗證ER-NE算法的優(yōu)越性.現(xiàn)有加權(quán)網(wǎng)絡研究采用的典型數(shù)據(jù)集主要有科學家合作網(wǎng)SCN[20]、PSB數(shù)據(jù)集[21]、News數(shù)據(jù)集[22]以及Zachary空手道俱樂部網(wǎng)絡.這些數(shù)據(jù)集中僅PSB數(shù)據(jù)集和Zachary空手道俱樂部網(wǎng)絡具有原始分類信息,因此本文選取這2個數(shù)據(jù)集作為實驗對象.其中PSB數(shù)據(jù)集為依據(jù)三維模型檢索系統(tǒng)獲得的反饋信息構(gòu)建的三維模型間的語義關(guān)系圖,本文具體采用的實驗數(shù)據(jù)集為PSB數(shù)據(jù)集的一個子集,該子集中含有10個社團.

表3 算法對比結(jié)果
Table 3 Comparison result of algorithms

數(shù)據(jù)集算法NANFNWSCPSBWGNFNER-NE10850.631270.6712110.79ZacharyWGNFNER-NE2220.97210.97220.91

在已知的加權(quán)網(wǎng)絡社團發(fā)現(xiàn)算法中,選擇經(jīng)典的WGN算法和FN算法作為對比算法,實驗結(jié)果如表3所示.表3中NA表示原始數(shù)據(jù)集中實際社團數(shù)量,NF表示算法發(fā)現(xiàn)的社團個數(shù),NW表示算法發(fā)現(xiàn)的社團中滿足弱社團定義的社團數(shù)量,SC表示正確劃分率.其中正確劃分率是將算法所得社團中,不在真實社團中的節(jié)點作為錯誤劃分,其余正確劃分節(jié)點占節(jié)點總數(shù)的比例.該度量作為衡量算法劃分效果的常用方法,適用于社團結(jié)構(gòu)已知的網(wǎng)絡.由于ER-NE算法基于本文提出的改進加權(quán)網(wǎng)絡社團結(jié)構(gòu)定義,因此模塊度等常用度量不適合衡量算法的劃分效果,所以本文選取正確劃分率作為算法對比的衡量指標.

從表3可以看出,ER-NE算法所發(fā)現(xiàn)的社團數(shù)量與數(shù)據(jù)集中實際社團數(shù)量較為接近,并且所發(fā)現(xiàn)的社團符合本文弱社團結(jié)構(gòu)定義的比例更高.由于ER-NE算法的正確劃分率的統(tǒng)計考慮了社團間的重疊節(jié)點,可能對部分數(shù)據(jù)集的劃分結(jié)果正確率數(shù)值稍低.若不考慮重疊節(jié)點,則算法在PSB以及Zachary數(shù)據(jù)集上的正確劃分率分別為0.87與1.00,與經(jīng)典算法對比優(yōu)越性更為明顯.

ER-NE算法的社團劃分結(jié)果中,可能包含若干重疊節(jié)點.由3.2小節(jié)算法描述可知,步驟9-12中可能存在節(jié)點對多個社團的有效性NE均大于0.5,即該節(jié)點屬于多個社團,但有2種情況會造成這些社團之間不發(fā)生合并:一是社團數(shù)量為已知的固定值,初始社團間不再合并;二是步驟13-16中所示,社團數(shù)量未知,但社團間合并后不滿足本文定義,因此使得最終劃分結(jié)果中存在重疊節(jié)點.與非重疊社團發(fā)現(xiàn)算法相比,ER-NE算法對社團歸屬較為模糊的節(jié)點采取了穩(wěn)妥的處理,將其看作重疊節(jié)點,而不是生硬的將其歸屬于有效性NE最大的社團.同時,這種處理策略與典型的重疊社團發(fā)現(xiàn)算法相比,也存在較大的差異:一是重疊節(jié)點的含義不同,ER-NE算法將社團歸屬較為模糊的節(jié)點看作重疊節(jié)點,而重疊社團發(fā)現(xiàn)算法通常考慮明確同屬于多個社團的節(jié)點;二是處理對象不同,重疊社團發(fā)現(xiàn)研究大多針對無權(quán)網(wǎng)絡,而ER-NE算法針對加權(quán)網(wǎng)絡.因此,本文不進一步做二者的具體對比.

5 總 結(jié)

本文首先在現(xiàn)有復雜網(wǎng)絡社團結(jié)構(gòu)定義的基礎上,提出了一種新的加權(quán)網(wǎng)絡中社團結(jié)構(gòu)定義,在考慮了權(quán)重對社團結(jié)構(gòu)影響的同時,綜合考慮了節(jié)點度對社團結(jié)構(gòu)的作用,并通過在現(xiàn)實網(wǎng)絡上的應用,驗證了該定義的合理性.然后在本文定義的基礎上,結(jié)合傳統(tǒng)凝聚算法的思想,進一步定義邊社團關(guān)聯(lián)性與節(jié)點社團有效性指標,提出了一種新的加權(quán)網(wǎng)絡中社團發(fā)現(xiàn)算法(ER-NE算法).該算法利用本文定義的新指標,一方面避免凝聚過程中傳遞性質(zhì)出現(xiàn),另一方面充分體現(xiàn)本文社團定義中對連接權(quán)重及節(jié)點度的綜合考慮.最后選擇PSB數(shù)據(jù)集和Zachary空手道俱樂部網(wǎng)絡作為實驗數(shù)據(jù),與經(jīng)典WGN算法和FN算法進行了對比實驗,實驗結(jié)果驗證了本文算法的有效性和優(yōu)越性.

[1] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[2] Li Hui-jia,Li Ai-hua,Li Hui-ying.Fast community detection algorithm via dynamical iteration[J].Chinese Journal of Computers,2017,40 (4):970-984.

[3] Xie Yi,Sun Yu-qing,Shen Lei.Theme and community evolution in complex social network[J].Journal of Chinese Computer Systems,2016,37(11):2402-2408.

[4] Sun Da-ming,Zhang Bin,Zhang Shu-bo,et al.A popularity versus similarity query recommendation strategy[J].Journal of Chinese Computer Systems,2016,37(6):1121-1125.

[5] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2001,99(12):7821-7826.

[6] Capocci A,Servedio V D P,Caldarelli G,et al.Detecting communities in large networks[J].Physica A Statistical Mechanics & Its Applications,2004,352(2-4):669-676.

[7] Boccaletti S,Latora V,Moreno Y,et al.Complex networks:structure and dynamics[J].Physics Reports,2006,424(4):175-308.

[8] Pujol J M,Béjar J,Delgado J.Clustering algorithm for determining community structure in large networks[J].Physical Review E,2006,74(1):016107.

[9] Zhang S,Wang R S,Zhang X S.Identification of overlapping community structure in complex networks using fuzzy c-means clustering[J].Physica A,2007,374(1):483-490.

[10] Palla G,Derenyi I,Farkas I,et al.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[11] Lancichinetti A,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2008,11(3):19-44.

[12] Jin D,Yang B,Baquero C,et al.Markov random walk under constraint for discovering overlapping communities in complex networks[J].Journal of Statistical Mechanics Theory and Experiment,2011(5):1-11.

[13] Evans T S,Lambiotte R.Line graphs,link partitions,and overlapping communities[J].Physical Review E,2009,80(2):016105.

[14] Xu Gang,Jin Hai-he,Liu Jing.Community detection based on the opportunistic networks uncertain social[J].Journal of Chinese Computer Systems,2016,37(11):2473-2477.

[15] Lv Tian-yang,Xie Wen-yan,Zheng Wei-min,et al.Analysis of community evaluation criterion and discovery algorithm of weighted complex network[J].Acta Physica,Sinica,2012,61(21):145-154.

[16] Clauset A,Newman M E,Moore C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.

[17] Newman M E J.Analysis of weighted networks[J].Physical Review E,2004,70(5):056131.

[18] Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.

[19] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.

[20] Newman M E J.Finding community strcuture in networks using the eigenvectors of matrics[J].Physical Review E,2006,74(3):036104.

[21] Lü T,Huang S,Wu P,et al.Researches on semantic annotation and retrieval of 3D models based on user feedback[C].Proceedings of the 6th International Conference on Semantics Knowledge and Grid.IEEE,2010:211-218.

[22] Dooley K,Corman S.Dynamic analysis of news streams:institutional versus environmental effects[J].Nonlinear Dynamics Psychology and Life Sciences,2004,8(3):259-284.

附中文參考文獻：

[2] 李慧嘉,李愛華,李慧穎.社團結(jié)構(gòu)迭代快速探測算法[J].計算機學報,2017,40(4):970-984.

[3] 謝 翌,孫宇清,沈 雷.復雜社會網(wǎng)絡中主題驅(qū)動的社團演化[J].小型微型計算機系統(tǒng),2016,37(11):2402-2408.

[4] 孫達明,張 斌,張書波,等.一種流行性與相似性結(jié)合查詢推薦策略[J].小型微型計算機系統(tǒng),2016,37(6):1121-1125.

[14] 許 崗,金海和,劉 靖.機會網(wǎng)絡的不確定社會關(guān)系社團發(fā)現(xiàn)[J].小型微型計算機系統(tǒng),2016,37(11):2473-2477.

[15] 呂天陽,謝文艷,鄭緯民,等.加權(quán)復雜網(wǎng)絡社團的評價指標及其發(fā)現(xiàn)算法分析[J].物理學報,2012,61(21):145-154.