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

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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

統(tǒng)計(jì)量∑kin∑kout∑sin∑soutwinwout社團(tuán)166101992632.6社團(tuán)26910219223.22.2

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

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

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

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

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

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

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

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

(2)

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

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

(3)

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

3.2 算法描述

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

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

輸出:劃分所得社團(tuán)集合C

1 ifk==0

//flag標(biāo)記k初始是否為0,其初始值為false

3 計(jì)算鄰接ER矩陣;

4C=?;

5 while |C|

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

//剩余部分是指不包含在社團(tuán)中的部分

7 if 社團(tuán)之間存在重疊節(jié)點(diǎn)

8 合并重疊社團(tuán);

9 for 所有社團(tuán)Ci∈C

10 forCi所有鄰接點(diǎn)v

11 ifNE(v,Ci)>0.5

12v→Ci;

13 ifflag

14 for 所有社團(tuán)Ci∈C

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

16 合并重疊社團(tuán);

17 ifH≠?

18 forH中所有節(jié)點(diǎn)對(duì)

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

20vj→vi所在社團(tuán)(或vi→vj所在社團(tuán))

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

22 forv所有鄰接社團(tuán)Ci

23 計(jì)算NE(v,Ci)

24v→Cmax;

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

25 ifv∈H

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

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

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

28 goto 步驟21

29 returnC

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

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

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

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

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

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

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

4 實(shí)驗(yàn)分析

4.1 ER-NE算法有效性驗(yàn)證

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

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

算法對(duì)空手道俱樂部網(wǎng)絡(luò)的劃分結(jié)果為2個(gè)社團(tuán),其中社團(tuán)1包含的節(jié)點(diǎn)集為:

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

社團(tuán)2包含的節(jié)點(diǎn)集為:

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

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

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

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

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

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

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

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

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

5 總 結(jié)

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

附中文參考文獻(xiàn)：

[2] 李慧嘉,李愛華,李慧穎.社團(tuán)結(jié)構(gòu)迭代快速探測(cè)算法[J].計(jì)算機(jī)學(xué)報(bào),2017,40(4):970-984.

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

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

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

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