(平頂山學(xué)院計算機學(xué)院,平頂山467000)
自然界與現(xiàn)實世界中的許多系統(tǒng)都可以用由節(jié)點和邊組成的網(wǎng)絡(luò)抽象地來表示,如社會關(guān)系網(wǎng)、流行病傳播網(wǎng)、蛋白質(zhì)交互網(wǎng)、Internet網(wǎng)絡(luò)等,這些網(wǎng)絡(luò)因其具有高復(fù)雜性被稱為“復(fù)雜網(wǎng)絡(luò)”。復(fù)雜網(wǎng)絡(luò)通常具有小世界效應(yīng)和無標(biāo)度特性這兩個統(tǒng)計特性。其中,“小世界效應(yīng)”是指復(fù)雜網(wǎng)絡(luò)具有短路徑長度和高聚類系數(shù)的特點[1];“無標(biāo)度特性”則是指復(fù)雜網(wǎng)絡(luò)中的結(jié)點的度服從冪率分布特征[2]?!吧鐖F(tuán)結(jié)構(gòu)”是復(fù)雜網(wǎng)絡(luò)的一種重要結(jié)構(gòu)特性,指的是社團(tuán)中的點相互連接緊密,而這些點同社團(tuán)外的點連接較為松散[3]。社團(tuán)的發(fā)現(xiàn)和劃分對于分析網(wǎng)絡(luò)的組織結(jié)構(gòu)、功能劃分和成員關(guān)系等有著重要的理論意義和實際價值。
近年來,隨著社團(tuán)結(jié)構(gòu)研究不斷深入,社團(tuán)挖掘算法被主要分為全局社團(tuán)挖掘算法和局部社團(tuán)挖掘算法。全局社團(tuán)挖掘算法基于全網(wǎng)信息進(jìn)行分析,如譜聚類算法[4]、GN 算法[5]、快速 Newman 算法[6],但目前復(fù)雜網(wǎng)絡(luò)的規(guī)模愈來愈大、動態(tài)性愈來愈強,導(dǎo)致算法的普適性、復(fù)雜度和效率等有待改進(jìn)。局部社團(tuán)挖掘算法基于網(wǎng)絡(luò)的局部信息進(jìn)行挖掘,如Clauset等提出的基于局部模塊度R(R是社團(tuán)內(nèi)部總邊數(shù)與社團(tuán)內(nèi)外邊數(shù)之和的比值)的算法,它是通過最大化局部模塊度增量來進(jìn)行局部社團(tuán)搜索[7];Luo等提出的另一種評價局部模塊度的指標(biāo)M(M是社團(tuán)內(nèi)部總邊數(shù)與社團(tuán)外部節(jié)點和邊界節(jié)點連邊數(shù)之比)的算法[8],其中,局部社團(tuán)的規(guī)模、初始節(jié)點的位置等均會影響到社團(tuán)最終的劃分結(jié)果。評價社團(tuán)劃分算法的優(yōu)劣,一個通常的做法是對每個劃分給出一個度量,較合理的劃分有較高的度量,優(yōu)化該度量以得到最優(yōu)或次優(yōu)的社團(tuán)結(jié)構(gòu)。第一個 (也是目前最有效的)度量是“模塊優(yōu)度”(modularity),是由 Newman 在 2004 年提出的[9],其值越大說明社團(tuán)結(jié)構(gòu)越明顯,在實際網(wǎng)絡(luò)中,該值通常位于0.3~0.7之間。
本文結(jié)合復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的相關(guān)研究,提出了一種基于中心節(jié)點和局部優(yōu)化的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分方法。該算法首先通過多個節(jié)點中心性指標(biāo)對復(fù)雜網(wǎng)絡(luò)中節(jié)點的中心性進(jìn)行綜合判斷,找出網(wǎng)絡(luò)的中心節(jié)點集,接著使用局部優(yōu)化思想基于每個中心節(jié)點進(jìn)行社團(tuán)擴(kuò)張,從而形成多個社團(tuán),然后再對一些特殊節(jié)點進(jìn)行處理,最終實現(xiàn)整個復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分。
Reihaneh等人首次提出了基于中心節(jié)點的社團(tuán)定義,即將社團(tuán)看作由一個領(lǐng)導(dǎo)者和聚集在其周圍的跟隨者組成,其中領(lǐng)導(dǎo)者就是社團(tuán)的中心節(jié)點[10]。因此,在復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分中,首先要做的就是尋找網(wǎng)絡(luò)的中心節(jié)點,然后再根據(jù)中心節(jié)點選取適當(dāng)?shù)姆椒ㄟM(jìn)行社團(tuán)挖掘。
節(jié)點的中心性評價指標(biāo)較多,下面僅對新算法需要用到的度中心性、介數(shù)中心性、接近中心性三項指標(biāo)展開介紹。
(1)度中心性
度中心性(degree centrality,DC)是描述無標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)的基本參數(shù)[11]。為了適應(yīng)不同規(guī)模的網(wǎng)絡(luò),這里進(jìn)行歸一化處理,定義度中心性為節(jié)點實際關(guān)聯(lián)的邊數(shù)與可能關(guān)聯(lián)的最大邊數(shù)之比。節(jié)點v的度中心性DCv表達(dá)式為:
其中,n為網(wǎng)絡(luò)中節(jié)點的個數(shù),d(v)是節(jié)點v的度,指其實際所關(guān)聯(lián)的邊的數(shù)目。
度中心性表明了節(jié)點在網(wǎng)絡(luò)中的直接影響力,其值越大,節(jié)點屬于局部中心點(即社團(tuán)中心點)的可能性越大。
(2)介數(shù)中心性
介數(shù)中心性(betweenness centrality,BC)用途經(jīng)節(jié)點的任意節(jié)點對間最短路徑的多少來衡量該節(jié)點在網(wǎng)絡(luò)中的地位。節(jié)點v的介數(shù)中心性BCv表達(dá)式為:
其中,V為網(wǎng)絡(luò)中節(jié)點的集合,gxy(v)表示節(jié)點x和y之間途經(jīng)節(jié)點v的最短路徑的條數(shù),gxy為節(jié)點x和y之間最短路徑的總數(shù)。
若一個節(jié)點是網(wǎng)絡(luò)中其他節(jié)點對之間通信的必經(jīng)之路,則其在網(wǎng)絡(luò)中必有重要地位,因此,節(jié)點的BC值越大,說明在網(wǎng)絡(luò)傳輸信息、物質(zhì)或能量時,其負(fù)載越重,可以被認(rèn)為是網(wǎng)絡(luò)的中心節(jié)點之一[11]。
(3)接近中心性
接近中心性(closeness centrality,CC)用節(jié)點到網(wǎng)絡(luò)中其它節(jié)點的距離來衡量該節(jié)點是否處于中心地位。節(jié)點v的接近中心性CCv表達(dá)式為:
其中,n為網(wǎng)絡(luò)中節(jié)點的個數(shù),d(v ,u)表示節(jié)點v到u的距離,即兩節(jié)點之間最短路中邊的數(shù)量。
一個節(jié)點到網(wǎng)絡(luò)中其它節(jié)點的距離越短,節(jié)點的接近中心性的值就越大,表明節(jié)點居于網(wǎng)絡(luò)中心位置的可能性越大。
由上述節(jié)點中心性指標(biāo)的定義可以看出,不同的指標(biāo)從不同的角度描述了節(jié)點在復(fù)雜網(wǎng)絡(luò)中的中心程度。由于只利用單一中心性指標(biāo)來計算節(jié)點在網(wǎng)絡(luò)中的中心性可能存在偏差,故此提出一種基于多屬性判別的節(jié)點中心性計算方法。該方法將網(wǎng)絡(luò)中的每一個節(jié)點作為一個方案,將節(jié)點的多個中心性指標(biāo)作為方案的屬性,則節(jié)點的中心性計算就轉(zhuǎn)化為一個多屬性判別問題[12]。
設(shè)網(wǎng)絡(luò)中有n個節(jié)點,則對應(yīng)的方案集合可以表示為P={P1,P2,…,Pn},若節(jié)點的中心性指標(biāo)有m個,則對應(yīng)的方案屬性集合I={I1,I2,…,In},第i個節(jié)點的第j個指標(biāo)的值記為Pi=(Ij)(i=1,2,…,n;j=1,2,…,m。下同),構(gòu)成判別矩陣:
由于各指標(biāo)的量綱不同,為了便于比較,對上述矩陣做如下標(biāo)準(zhǔn)化處理:
標(biāo)準(zhǔn)化處理后的矩陣記為 R=(rij)n×m。
設(shè)第j個指標(biāo)的權(quán)重為ωj(j=1,2,…,m;則加權(quán)標(biāo)準(zhǔn)化判別矩陣為:
由上,計算第i個節(jié)點的綜合中心性Ci為:
采用度中心性DC、介數(shù)中心性BC、接近中心性CC這三個指標(biāo)對節(jié)點的中心性進(jìn)行綜合判斷,各指標(biāo)的權(quán)重按照文獻(xiàn)[12]中使用的層次分析法進(jìn)行計算,得到 ωDC=0.5493,ωBC=0.2616,ωCC=0.1891。
基于不同社團(tuán)的中心點之間應(yīng)當(dāng)保持一定距離的思想,還需要對節(jié)點之間的相似性進(jìn)行計算,在選取綜合中心性值大的節(jié)點時,將相似度極高的節(jié)點去掉。
(1)節(jié)點相似性
節(jié)點相似性用兩個節(jié)點的共有鄰居節(jié)點的數(shù)目來描述節(jié)點間的緊密程度,節(jié)點u和v的相似性Suv的表達(dá)式為:
其中,Nu表示節(jié)點u的鄰居節(jié)點集(且包含u點自身)表示節(jié)點u和v的共有鄰居節(jié)點的數(shù)目表示節(jié)點u和v包含自身在內(nèi)的所有鄰居節(jié)點的數(shù)目。
一般情況下,兩個節(jié)點的相似度越高,即Suv值越大,則這兩個節(jié)點屬于同一個社團(tuán)的概率就越大。
(2)算法描述
至此,給出基于多屬性判別和相似性的社團(tuán)中心節(jié)點發(fā)現(xiàn)算法,首先根據(jù)綜合中心性值選取候選中心節(jié)點,然后計算候選節(jié)點之間的相似度,相似度大的話,就將相似的兩個節(jié)點中綜合中心性值較小的那個節(jié)點刪掉。算法流程如圖1所示。
圖1 復(fù)雜網(wǎng)絡(luò)中心節(jié)點發(fā)現(xiàn)算法流程圖
社團(tuán)往往是指一個內(nèi)部連接緊密、外部連接松散的子圖。在確定了網(wǎng)絡(luò)的中心節(jié)點集后,對每個中心節(jié)點利用局部優(yōu)化的思想,不斷地將鄰近節(jié)點歸入社團(tuán)以實現(xiàn)社團(tuán)規(guī)模的擴(kuò)大,從而形成多個局部社團(tuán)。下面先給出局部模塊優(yōu)度的定義,然后對基于局部優(yōu)化的社團(tuán)劃分算法展開描述。
用社團(tuán)的局部模塊優(yōu)度LC來衡量一個社團(tuán)劃分的優(yōu)劣,其表達(dá)式為:
其中,Ein是社團(tuán)內(nèi)部邊的數(shù)目,內(nèi)部邊指邊的兩個頂點都在社團(tuán)中;Eout是社團(tuán)外部邊的數(shù)目,外部邊指的則是邊的一個頂點在社團(tuán)內(nèi)部,另一個頂點在社團(tuán)外部。
加入鄰居節(jié)點后的社團(tuán)局部模塊優(yōu)度LC'的表達(dá)式為:
加入鄰居節(jié)點后,社團(tuán)的局部模塊優(yōu)度增量ΔLC的表達(dá)式為:
通過ΔLC可以衡量鄰居節(jié)點對社團(tuán)局部模塊優(yōu)度的影響,進(jìn)而判斷該鄰居節(jié)點是否要劃歸到社團(tuán)內(nèi)部。
基于局部優(yōu)化的社團(tuán)劃分算法,是逐個計算加入鄰居節(jié)點后的局部模塊優(yōu)度增量ΔLC,將增量大于設(shè)定閾值的鄰居節(jié)點加入候選節(jié)點集,然后從候選節(jié)點集中選擇與社團(tuán)具有最多共同鄰居節(jié)點的節(jié)點來更新社團(tuán),直到?jīng)]有大于設(shè)定的增量閾值的節(jié)點出現(xiàn)。以一個中心節(jié)點為例挖掘以該節(jié)點為中心節(jié)點的社團(tuán),算法流程如圖2所示。
在對所有的中心節(jié)點執(zhí)行完局部社團(tuán)挖掘后,需要對一些特殊節(jié)點進(jìn)行處理。一類是未被劃分至任何社團(tuán)的節(jié)點,另一類是被劃分至多個社團(tuán)的節(jié)點,這些節(jié)點最終均將被劃分至與其有最多鄰居節(jié)點的社團(tuán)。
主要的算法結(jié)果評價指標(biāo)包括以下三種:
(1)準(zhǔn)確率(Precision,P)
準(zhǔn)確率為劃分結(jié)果中正確節(jié)點數(shù)量與劃分結(jié)果中總節(jié)點數(shù)量之比,表達(dá)式為:
圖2 社團(tuán)劃分算法流程圖
(2)召回率(Recall,R)
召回率為劃分結(jié)果中正確節(jié)點數(shù)量與真實社團(tuán)中總節(jié)點數(shù)量之比,表達(dá)式為:
(3)綜合評價指標(biāo)
為防止過分割和欠分割的情況,用綜合評價指標(biāo)F來對社團(tuán)劃分進(jìn)行總體評價,表達(dá)式為:
為了驗證算法的準(zhǔn)確性,分別以空手道俱樂部成員關(guān)系網(wǎng)絡(luò)數(shù)據(jù)集Zachary[13]和海豚網(wǎng)絡(luò)數(shù)據(jù)集Dolphin[14]為例進(jìn)行了測試。經(jīng)驗證,中心節(jié)點相似度閾值和局部模塊優(yōu)度增量閾值分別為0.3和0.33時,最符合真實的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。
算法對Zachary的測試結(jié)果如圖3所示,其中,網(wǎng)絡(luò)被分成了兩個社團(tuán)。
圖3 Zachary社團(tuán)結(jié)構(gòu)圖
實驗中,針對上述定義的準(zhǔn)確率、召回率、綜合評價這三個算法評價指標(biāo),將此算法與引言中介紹的R算法及M算法進(jìn)行了對比。對比結(jié)果如表1所示,從中可以看出,在Zachary數(shù)據(jù)集的測試結(jié)果中,此算法明顯優(yōu)于其它算法,在Dolphin數(shù)據(jù)集的測試結(jié)果中,除了準(zhǔn)確率低于R算法,其它指標(biāo)均優(yōu)于所對比的算法。
表1 算法對比數(shù)據(jù)表
對復(fù)雜網(wǎng)絡(luò)中節(jié)點的度中心性、介數(shù)中心性、接近中心性、相似度、局部模塊優(yōu)度等指標(biāo)做了歸納、整理并適當(dāng)加以擴(kuò)展。分別應(yīng)用基于多屬性判別和相似性的社團(tuán)中心節(jié)點發(fā)現(xiàn)算法和基于局部優(yōu)化的社團(tuán)劃分方法對Zachary和Dolphin數(shù)據(jù)集進(jìn)行了測試,同時與R算法和M算法進(jìn)行了對比,結(jié)果表明新算法具有較好的社團(tuán)劃分能力,可以有效地挖掘出社團(tuán)結(jié)構(gòu)。在此基礎(chǔ)上,進(jìn)一步降低算法的時間復(fù)雜度和解決大規(guī)模真實網(wǎng)絡(luò)應(yīng)用中的優(yōu)化問題,將是下一步的研究重點。