萬仁霞,張宇紅,苗奪謙

(1.北方民族大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,寧夏 銀川 750021;2.同濟(jì)大學(xué)計算機(jī)科學(xué)與技術(shù)系,上海 201804)

0 引言

在現(xiàn)實世界中存在著各種各樣的網(wǎng)絡(luò),如城市交通網(wǎng)絡(luò)[1]、社會網(wǎng)絡(luò)[2]、生物網(wǎng)絡(luò)[3]等,它們都可以抽象成復(fù)雜網(wǎng)絡(luò).而復(fù)雜網(wǎng)絡(luò)又是由若干個社團(tuán)構(gòu)成的,社團(tuán)的結(jié)構(gòu)性[4]主要表現(xiàn)為:在同一個社團(tuán)中的節(jié)點聯(lián)系較為緊密,在不同社團(tuán)間的節(jié)點聯(lián)系較為稀疏.研究網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)可以更加準(zhǔn)確地理解復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及其內(nèi)在原理.因此,如何有效地進(jìn)行社團(tuán)劃分是社團(tuán)研究者們的研究方向之一.

近年來,許多學(xué)者從不同角度對網(wǎng)絡(luò)的社團(tuán)劃分[5]算法進(jìn)行了研究.Newman快速算法(Newman fast algorithm,NFA)[6]依靠模塊度獲得最佳社團(tuán)結(jié)構(gòu);自包含GN算法[7](self-contained GN algorithm)給出了強(qiáng)社團(tuán)結(jié)構(gòu)和弱社團(tuán)結(jié)構(gòu)2種變量的定義,為社團(tuán)結(jié)構(gòu)的好壞提供了一種參考標(biāo)準(zhǔn);B.W. Kernighan等[8]提出了基于圖劃分的社團(tuán)劃分算法,該算法需要提前預(yù)知社團(tuán)劃分的數(shù)目才可以實現(xiàn)社團(tuán)劃分;U.N. Raghavan等[9]提出一種快速標(biāo)號傳播算法(label propagation algorithm,LPA),該算法利用網(wǎng)絡(luò)自身結(jié)構(gòu)來判定社團(tuán)結(jié)構(gòu),復(fù)雜度較低且收斂快,但缺點是比真實社團(tuán)結(jié)構(gòu)的精度略低.上述算法從不同角度和不同層面對復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分問題進(jìn)行研究,并取得了一定的研究成果.目前,社團(tuán)劃分算法大多數(shù)是非重疊的社團(tuán)劃分算法,其對于重疊部分的處理采用傳統(tǒng)的二支決策技術(shù),即根據(jù)已有的信息、社團(tuán)對節(jié)點的歸屬做出接受或拒絕的判決.然而,由于信息的模糊或不充分等因素,許多網(wǎng)絡(luò)存在重疊的社團(tuán)結(jié)構(gòu)[10],所以基于二支決策技術(shù)的社團(tuán)劃分會導(dǎo)致社團(tuán)劃分結(jié)果的不可靠問題.因此,如何對網(wǎng)絡(luò)中重疊部分的節(jié)點進(jìn)行有效地劃分,以便發(fā)現(xiàn)社團(tuán)潛在的規(guī)律,已引起了許多學(xué)者的關(guān)注.李敏毓等[11]提出一種社團(tuán)結(jié)構(gòu)特征研究,旨在處理在社交網(wǎng)絡(luò)中的重疊社團(tuán)并解決現(xiàn)有的社團(tuán)劃分算法結(jié)果分辨率低的問題.LFM(largest fitness measure)是基于局部優(yōu)化的適應(yīng)度函數(shù)的社團(tuán)發(fā)現(xiàn)算法[12],該算法在發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社團(tuán)和有關(guān)層次結(jié)構(gòu)的社團(tuán)方面具有較好的效果.郭娜等[13]提出了一種基于最大生成樹的重疊社團(tuán)發(fā)現(xiàn)算法,該算法對初始社團(tuán)劃分結(jié)果進(jìn)行優(yōu)化,且避免了社團(tuán)之間重疊的出現(xiàn).

三支決策(three-way decisions,3WD)理論[14]的思想是由決策粗糙集理論(decision-theoretic rough sets,DTRS)[15]產(chǎn)生的,旨在解決在現(xiàn)實世界中的不確定信息的決策問題,為模糊信息處理[16]提供一種新的解決思路.由于三支決策符合人類思維和認(rèn)知特點,能較好地處理在實際決策過程中出現(xiàn)的不確定性問題,所以它一經(jīng)提出便得到國內(nèi)外學(xué)者的廣泛關(guān)注.楊雪潔等[17]提出了一種基于子模優(yōu)化的邊界域處理社團(tuán)發(fā)現(xiàn)算法,旨在用三支決策模型及子模優(yōu)化思想來劃分社團(tuán)結(jié)構(gòu).方蓮娣等[18]提出一種基于三支決策的非重疊社團(tuán)劃分算法,該方法將初始聚類形成的重疊社團(tuán)進(jìn)行2次劃分以形成最終的非重疊社團(tuán).

本文通過節(jié)點的重要度來刻畫節(jié)點間的關(guān)系,采用三支決策思想來解決社團(tuán)節(jié)點重疊問題,提出了一種基于吸收度的三支決策社團(tuán)劃分算法,即根據(jù)不同節(jié)點歸入不同社團(tuán)域的動作參數(shù)所產(chǎn)生的損失函數(shù)來定義吸收度,并依據(jù)吸收度對已獲取的重疊節(jié)點進(jìn)行劃分,不僅較好地體現(xiàn)了節(jié)點的真實歸屬,還可以獲取更好地接近全局最優(yōu)社團(tuán).本文采用3個真實的網(wǎng)絡(luò)數(shù)據(jù)集對3WD-PPOC算法進(jìn)行了驗證,實驗結(jié)果表明本文所提算法對在社團(tuán)中的節(jié)點處理可行且有效.

1 相關(guān)概念

1.1 節(jié)點屬性重要度

在一個無向無權(quán)網(wǎng)絡(luò)G=〈V,E〉中,節(jié)點集合為V,邊集合為E,在節(jié)點集合V中一對點即對應(yīng)邊集合E中的一條邊.

定義1[19]設(shè)節(jié)點集合V={e1,e2,…,en},令(ei,ej)表示節(jié)點ei與節(jié)點ej之間的邊,若ei和ej相連,則邊存在;若ei和ej不相連,則邊不存在.邊集E={(ei,ej):ei,ej∈V;1≤i,j≤n},則節(jié)點ei的度Di表示ei的鄰居節(jié)點的數(shù)目,即與該節(jié)點連接的其他節(jié)點的數(shù)目,Di的表達(dá)式為

Di=|{(ei,ej):ei,ej∈V;(ei,ej)∈E}|.

定義2[20]設(shè)節(jié)點集為V={e1,e2,…,en},那么在節(jié)點集中所有節(jié)點的平均度為〈k〉,〈k〉的表達(dá)式為

由于ei、ej屬于同一網(wǎng)絡(luò),且Di表示節(jié)點ei的鄰居節(jié)點數(shù)目,于是可得到如下節(jié)點平均度的結(jié)論.

定義3[21]鄰接矩陣Wn×n表示在網(wǎng)絡(luò)中節(jié)點ei與節(jié)點ej之間的連接關(guān)系,其中wij為在鄰接矩陣中對應(yīng)的元素,取值為0或1,n為節(jié)點總數(shù),即若節(jié)點ei和ej之間有連接關(guān)系,則wij=1;若節(jié)點ei和ej之間沒有連接關(guān)系,則wij=0.

定義4[22]節(jié)點重要度矩陣H的定義為

其中將矩陣對角線上的元素全部置為1,它表示在網(wǎng)絡(luò)中每個節(jié)點對于自身的重要度貢獻(xiàn)比值為1.由定理1知,在網(wǎng)絡(luò)中的節(jié)點重要度矩陣H是網(wǎng)絡(luò)鄰接矩陣的映射.當(dāng)i≠j時,wij映射為wijDj/〈k〉2;當(dāng)i=j時,wij映射為1.

1.2 三支決策

三支決策[23]理論對于在信息處理中不確定決策問題的解決具有高效性,尤其是對信息不精確、條件不充分的情況.其核心思想是將決策項分成3 種決策規(guī)則,分別是正域決策、負(fù)域決策和邊界域決策.當(dāng)證據(jù)不完整、不充足時,可以采用邊界域決策;當(dāng)證據(jù)精準(zhǔn)、完善時,可以采用正域決策或者負(fù)域決策.正域決策和負(fù)域決策是明確的,即三支決策主要圍繞邊界域的處理展開研究.

三支決策的研究主要基于決策粗糙集,整個論域被劃分為3個部分,即正域(POS)、負(fù)域(NEG)和邊界域(BND),分別代表接受、拒絕和不承諾3種決策結(jié)果.決策粗糙集模型理論[24]將概率粗糙集和最小風(fēng)險貝葉斯決策結(jié)合起來,通過計算各類決策風(fēng)險損失值,對正域(POS)、負(fù)域(NEG)和邊界域(BND)進(jìn)行劃分.

文獻(xiàn)[24]對三支決策給出了具體解釋:假設(shè)有3種狀態(tài)的集合Ω={X1,X2,X3},對應(yīng)于概率粗糙集上的正域、負(fù)域、邊界域.由分類結(jié)果的3個域構(gòu)造出一個決策動作集D={αP,αN,αB},其中αP、αN、αB分別代表將一個對象分類到概率粗糙集上的正域、負(fù)域、邊界域的決策動作,且不同的決策動作代表不同的分類結(jié)果.

2 基于吸收度的三支決策社團(tuán)劃分算法

三支決策模型根據(jù)對象的正域、負(fù)域、邊界域采取不同的決策規(guī)則,尤其在處理不確定性問題時,可以通過信息量的增多,做出更為準(zhǔn)確的判決.

2.1 社團(tuán)中的3個域

基于三支決策的思想,實現(xiàn)對網(wǎng)絡(luò)重疊社團(tuán)結(jié)構(gòu)的劃分.對于初始社團(tuán)劃分后獲得的重疊社團(tuán)結(jié)構(gòu)的定義如下:

(i)正域(POS)表示被考察社團(tuán)的非重疊節(jié)點;

(ii)邊界域(BNG)表示重疊部分的節(jié)點;

(iii)負(fù)域(NEG)表示除正域及邊界域外的節(jié)點.

如圖1所示,左右2個橢圓分別代表2個社團(tuán)結(jié)構(gòu),且這2個社團(tuán)之間存在社團(tuán)重疊結(jié)構(gòu),即節(jié)點5、節(jié)點6以及節(jié)點7.網(wǎng)絡(luò)節(jié)點集為V={1,2,3,4,5,6,7,8,9,10,11},社團(tuán)X={1,2,3,4,5,6,7},依據(jù)三支決策思想,正域QPOS(X)={1,2,3,4},邊界域QBND(X)={5,6,7},負(fù)域QNEG(X)={8,9,10,11}.

圖1 重疊社團(tuán)3個域的劃分

顯然,社團(tuán)結(jié)構(gòu)滿足如下性質(zhì).

性質(zhì)1在網(wǎng)絡(luò)G=〈V,E〉中,對于任意社團(tuán)X,有:(i)QPOS(X)∪QBND(X)∪QNEG(X)=V;(ii)QPOS(X)、QBND(X)、QNEG(X)兩兩相交為空.

這表明:社團(tuán)的正域、邊界域、負(fù)域是網(wǎng)絡(luò)節(jié)點的一個劃分,且當(dāng)在社團(tuán)中的2個域明確后,其余1個域也是確定的.因此,在本文中,僅討論社團(tuán)的正域、邊界域的構(gòu)成,不對負(fù)域贅敘.

2.2 吸收度

借鑒三支決策閾值[25]的概念,本文給出社團(tuán)劃分的吸收度定義.

定義5假設(shè)一個社團(tuán)可以劃分為Ω={Y1,Y2,Y3},即對應(yīng)于社團(tuán)的正域、負(fù)域、邊界域.當(dāng)在社團(tuán)中的節(jié)點歸到不同的社團(tuán)域中時,可以得到不同的動作參數(shù)L={αP,αN,αB},其中αP、αN、αB分別代表節(jié)點歸入不同社團(tuán)域的動作參數(shù),且不同的動作參數(shù)代表不同的社團(tuán)域劃分結(jié)果,可能出現(xiàn)9種損失函數(shù)(見表1).其中第1列函數(shù)表示當(dāng)節(jié)點歸入社團(tuán)Y1,動作參數(shù)為αP、αN、αB時帶來的損失函數(shù),記為λPY1、λNY1、λBY1;第2列函數(shù)表示當(dāng)節(jié)點歸入社團(tuán)Y2,動作參數(shù)為αP、αN、αB時帶來的損失函數(shù),記為λPY2、λNY2、λBY2;第3列函數(shù)表示當(dāng)節(jié)點歸入社團(tuán)Y3,動作參數(shù)為αP、αN、αB時帶來的損失函數(shù),記為λPY3、λNY3、λBY3.

表1 損失函數(shù)

節(jié)點歸入不同社團(tuán)域可以得到不同的損失函數(shù),因此不同節(jié)點在不同的情況下會歸入不同的域.本文將根據(jù)吸收度的不同職能,將吸收度區(qū)分為F吸收度和P吸收度:

F=(λPY3-λBY3)/((λPY3-λBY3)+(λBY1-λPY1)),

(1)

P=(λBY3-λNY3)/((λBY3-λNY3)+(λNY1-λBY1)),

(2)

其中F吸收度用來控制社團(tuán)邊界域的形成,P吸收度用來控制社團(tuán)邊界域節(jié)點的再劃分.

可以證明,F、P吸收度滿足如下性質(zhì).

性質(zhì)20≤P

2.3 PPC算法流程

本文首先根據(jù)重要度矩陣,給出非重疊的社團(tuán)劃分算法,該算法在不引入吸收度時形成了初始社團(tuán)結(jié)構(gòu).主要實現(xiàn)步驟如算法1所示.

算法1PPC算法.

輸入:無向無權(quán)網(wǎng)絡(luò)G=〈V,E〉及重要度矩陣H.

輸出:網(wǎng)絡(luò)社團(tuán)Aj(j=1,2,…,k).

(i)計算網(wǎng)絡(luò)的節(jié)點重要度矩陣H;

(ii)隨機(jī)選擇k個節(jié)點z1,z2,…,zk,作為初始社團(tuán)的中心,令A(yù)j={zj}(j=1,2,…,k);

(iv)計算各社團(tuán)中心,若各中心未發(fā)生變化,則轉(zhuǎn)入步驟(v),否則,轉(zhuǎn)向步驟(iii);

(v)輸出社團(tuán)Aj(j=1,2,…,k).

在步驟(iii)中的HZ代表在社團(tuán)中所有需要被考察節(jié)點Z的重要度值.

算法1實際上是一種典型的非重疊社團(tuán)劃分的算法,為重疊社團(tuán)劃分創(chuàng)造了初始社團(tuán)結(jié)構(gòu).不同于一般社團(tuán)構(gòu)建的算法,本文的算法采用節(jié)點重要度來劃分節(jié)點的社團(tuán)歸屬.

2.4 3WD-PPOC算法流程

本文結(jié)合三支決策思想,引入吸收度的概念,在上述算法產(chǎn)生的初始社團(tuán)結(jié)構(gòu)的基礎(chǔ)上進(jìn)行局部再劃分處理,從而達(dá)到對重疊社團(tuán)節(jié)點的更精細(xì)劃分,其主要實現(xiàn)步驟如下.

算法23WD-PPOC算法.

輸入:無向無權(quán)網(wǎng)絡(luò)G=〈V,E〉、重要度矩陣H及λPY1、λNY1、λBY1、λPY2、λNY2、λBY2、λPY3、λNY3、λBY3值.

輸出:無重疊網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu).

(i)計算網(wǎng)絡(luò)的節(jié)點重要度矩陣H;

考慮到人們在工廠工作而Milk-run在生產(chǎn)供應(yīng)路線上行駛的事實，必須解決某些安全問題。首先，火車必須可以自由進(jìn)出Milk-run運(yùn)輸車道，并且路線上不應(yīng)放置任何物料，因為這些因素可能對司機(jī)構(gòu)成威脅并導(dǎo)致延誤。為了使員工關(guān)注工廠內(nèi)的交通情況，必須對車道進(jìn)行清晰的標(biāo)識，并且培訓(xùn)員工如何應(yīng)對車輛的流通，Milk-run火車必須擁有絕對的優(yōu)先通行權(quán)。

(ii)隨機(jī)選擇k個節(jié)點z1,z2,…,zk,作為初始社團(tuán)的中心,令A(yù)j={zj}(j=1,2,…,k);

(iv)計算各社團(tuán)中心,若各中心未發(fā)生變化,則轉(zhuǎn)入步驟(v),否則,轉(zhuǎn)向步驟(iii);

(v)通過式(1)～(2)計算F吸收度和P吸收度;

(vi)對于任意網(wǎng)絡(luò)節(jié)點Z,若存在社團(tuán)Al、Am,有||HZ-Hzi|-|HZ-Hzk||≤F,則將節(jié)點Z歸入社團(tuán)Al、Am的邊界QBND(Al)、QBND(Am),即Z為社團(tuán)Al、Am的共同邊界點(社團(tuán)重疊節(jié)點);

(vii)構(gòu)建社團(tuán)正域:QPOS(Ai)=Ai-QBND(Ai)

(i=1,2,…,k);

(x)更新QPOS(Aj0)的中心rj0;

(xi)更新邊界域:QBND(Aj)=QBND(Aj)-{Z}

(j=i1,i2,…,il);

(xii)若QBND(Al)≠?(l=1,2,…,k),則轉(zhuǎn)步驟(ix),否則,轉(zhuǎn)步驟(xiii);

(xiii)輸出社團(tuán)正域QPOS(Ai)(i=1,2,…,k).

算法2的步驟(i)～(iii)實際上執(zhí)行的是算法1的內(nèi)容,對重疊社團(tuán)的劃分起到初始化的作用.即算法2是算法1引入吸收度概念后的改進(jìn),從而能更好地處理重疊社團(tuán)節(jié)點的劃分.其中,在步驟(vi)中的F吸收度用于形成社團(tuán)邊界域,可以刻畫社團(tuán)的重疊區(qū).步驟(ix)是對社團(tuán)重疊區(qū)的節(jié)點(即邊界域中的節(jié)點)進(jìn)行最終的社團(tuán)歸屬判決,P吸收度用于刻畫邊界域中節(jié)點的劃分.F吸收度作用于邊界粗社團(tuán)的形成過程,即若F吸收度值越大,則所構(gòu)成的社團(tuán)結(jié)構(gòu)就越粗糙;P吸收度作用于區(qū)分邊界域中社團(tuán)節(jié)點的細(xì)化過程,即若P吸收度越小,則邊界社團(tuán)中節(jié)點的劃分就越精細(xì).由于算法的邊界域是基于多個社團(tuán)的共同邊界點而產(chǎn)生的(即步驟(vi)),不同于一般的三支決策處理類似問題(如三支聚類[26])的結(jié)果,所以在本文算法的邊界域中的節(jié)點同時為多個社團(tuán)潛在的節(jié)點,這為步驟(ix)～(xii)在多社團(tuán)邊界域上開展更新提供了必要條件.

算法輸出為社團(tuán)正域,可以證明這些社團(tuán)正域滿足如下的性質(zhì).

性質(zhì)3在無向無權(quán)網(wǎng)絡(luò)G=〈V,E〉中,經(jīng)過算法2產(chǎn)生的社團(tuán)正域QPOS(Ai)(i=1,2,…,k)滿足:

(ii)QPOS(Ai)∩QPOS(Aj)=?(1≤i,j≤k,且i≠j).

即經(jīng)過算法2后輸出的所有社團(tuán)正域是整個網(wǎng)絡(luò)節(jié)點的一個有效劃分.

3 算法驗證及分析

3.1 實驗數(shù)據(jù)與實驗環(huán)境

為了驗證本文所提算法的有效性和可行性,本文采用了3個典型的社交網(wǎng)絡(luò)數(shù)據(jù)集作為實驗數(shù)據(jù)集,分別是著名的空手道俱樂部成員網(wǎng)絡(luò)(Zachary′s karate club)、足球聯(lián)盟網(wǎng)絡(luò)(American college football)和海豚社會關(guān)系網(wǎng)絡(luò)(Dolphins).數(shù)據(jù)集可在網(wǎng)上(http://www-personal.Umich.edu/～mejn/netdata)的數(shù)據(jù)集中獲取.數(shù)據(jù)集的基本信息如表2所示.

實驗環(huán)境為英特爾酷睿雙核P8500處理器,內(nèi)存8 GB,64位Windows10操作系統(tǒng).主要編程語言為Matlab、R語言編程工具.

表2 實驗數(shù)據(jù)集

3.2 評價指標(biāo)

衡量社交網(wǎng)絡(luò)中社團(tuán)劃分質(zhì)量的標(biāo)準(zhǔn)主要有內(nèi)部評價指標(biāo)和外部評價指標(biāo)[27-29].

3.2.1 內(nèi)部評價指標(biāo) 在社交網(wǎng)絡(luò)中,模塊度函數(shù)作為社團(tuán)劃分好壞的量化標(biāo)準(zhǔn)已經(jīng)被廣泛使用.

模塊度函數(shù)Q[28]定義如下:

若社團(tuán)內(nèi)部邊的比例不大于在任意連接時的期望值,則有Q=0,且Q的上限為1.若社團(tuán)結(jié)構(gòu)越明顯,則越接近1.在實際的網(wǎng)絡(luò)中,Q的取值范圍一般為0.3～0.7.

3.2.2 外部評價指標(biāo)NMI指標(biāo)[29]可以用來估計具有已知分區(qū)的真實社團(tuán)結(jié)構(gòu)與社團(tuán)劃分結(jié)果之間的相似性.NMI反映了劃分的社團(tuán)結(jié)構(gòu)與真實社團(tuán)結(jié)構(gòu)非常相似,若NMI值為1,則2個社團(tuán)結(jié)構(gòu)完全相同,若NMI值為0,則2個社團(tuán)結(jié)構(gòu)完全不同.其計算公式為

NMI(X|Y)=1-(H(X|Y)+H(Y|X))/2,

其中X表示原社團(tuán)結(jié)構(gòu)的集合;Y表示使用本算法得到的社團(tuán)結(jié)構(gòu)的集合;H(X|Y)表示X在Y上的規(guī)范化條件熵;H(Y|X)表示Y在X上的規(guī)范化條件熵.

3.3 實驗與結(jié)果分析

3.3.1 吸收度與模塊度的關(guān)系 從3WD-PPOC的算法描述可以看出,損失函數(shù)通過吸收度F、P來影響社團(tuán)劃分的效果,圖2直觀展示了本文算法(3WD-PPOC)的吸收度F、P對模塊度Q的影響.從圖2可以看出,對于Zachary數(shù)據(jù)集,當(dāng)損失函數(shù)為λPY1=0、λPY3=6.4、λNY1=13.6、λNY3=0、λBY1=4、λBY3=0.4時,F、P吸收度為(F,P)=(0.60,0.40),此時模塊度參數(shù)最優(yōu)值為0.417;對于Football數(shù)據(jù)集,當(dāng)損失函數(shù)為λPY1=0、λPY3=5.6、λNY1=15.6、λNY3=0、λBY1=4.5、λBY3=0.1時,F、P吸收度為(F,P)=(0.550,0.005),模塊度參數(shù)最大值為0.604;對于Dolphins數(shù)據(jù)集,當(dāng)損失函數(shù)為λPY1=0、λPY3=5.6、λNY1=15.6、λNY3=0、λBY1=4.5、λBY3=0.1時,F、P吸收度為(F,P)=(0.550,0.005),此時模塊度參數(shù)最佳值為0.546.

圖2 基于實驗數(shù)據(jù)集吸收度與模塊度的關(guān)系圖

3.3.2 基于典型數(shù)據(jù)集的劃分效果 (i)基于Zachary 空手道俱樂部網(wǎng)絡(luò)實驗.Zachary空手道俱樂部網(wǎng)絡(luò)[30]是美國某大學(xué)空手道俱樂部的關(guān)系網(wǎng)絡(luò),該網(wǎng)絡(luò)包含34個節(jié)點及78條邊,其中節(jié)點表示俱樂部成員,邊表示成員之間存在的關(guān)系.Zachary空手道俱樂部成員關(guān)系網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)、社團(tuán)發(fā)現(xiàn)技術(shù)等領(lǐng)域的典型測試網(wǎng)絡(luò)數(shù)據(jù)集,在網(wǎng)絡(luò)中的人物關(guān)系因某種原因而被分成若干個小社團(tuán),該網(wǎng)絡(luò)的原始結(jié)構(gòu)如圖3所示.

圖3 Zachary網(wǎng)絡(luò)初始社團(tuán)結(jié)構(gòu)

據(jù)上述“吸收度與模塊度的關(guān)系”實驗,得到社團(tuán)劃分結(jié)構(gòu),即將Zachary網(wǎng)絡(luò)劃分為4個社團(tuán),如圖4所示.

圖4 3WD-PPOC算法對Zachary網(wǎng)絡(luò)的社團(tuán)劃分結(jié)果

(ii)基于Football足球聯(lián)盟網(wǎng)絡(luò)實驗.Football數(shù)據(jù)集是經(jīng)典的社團(tuán)研究數(shù)據(jù)集之一,該網(wǎng)絡(luò)由115個球隊的613場比賽抽象而成,如何根據(jù)不同球隊之間的實力合理劃分球隊,并合理安排相應(yīng)的賽事是該實驗關(guān)注的重點,該網(wǎng)絡(luò)的原始結(jié)構(gòu)如圖5所示.

圖5 Football 網(wǎng)絡(luò)初始社團(tuán)結(jié)構(gòu)

根據(jù)上述“吸收度與模塊度的關(guān)系”實驗,得到社團(tuán)劃分結(jié)構(gòu),將Football網(wǎng)絡(luò)劃分為6個社團(tuán),社團(tuán)劃分的結(jié)果如圖6所示.

圖6 3WD-PPOC算法對Football網(wǎng)絡(luò)的社團(tuán)劃分結(jié)果

(iii)基于Dolphins海豚社會關(guān)系網(wǎng)絡(luò)實驗.Dolphin海豚數(shù)據(jù)集是D. Lusseau等使用長達(dá)7 a的時間觀察新西蘭Doubtful Sound海峽62只海豚群體的交流情況而得到的海豚社會關(guān)系網(wǎng)絡(luò).這個網(wǎng)絡(luò)具有62個節(jié)點及159 條邊,節(jié)點表示海豚,而邊表示海豚間的接觸的頻率,該網(wǎng)絡(luò)的原始結(jié)構(gòu)如圖7所示.

圖7 Dolphins網(wǎng)絡(luò)初始社團(tuán)結(jié)構(gòu)

根據(jù)上述“吸收度與模塊度的關(guān)系”實驗,得到社團(tuán)劃分結(jié)構(gòu),將Dolphins網(wǎng)絡(luò)劃分為4個社團(tuán),社團(tuán)劃分的結(jié)果如圖8所示.

圖8 3WD-PPOC算法對Dolphins網(wǎng)絡(luò)社團(tuán)劃分結(jié)果

從圖4、圖6和圖8可以看出,劃分后3個數(shù)據(jù)集的社團(tuán)結(jié)構(gòu)比較緊密,這說明本文的算法對邊界域的節(jié)點得到了合理的劃分.

3.4 模塊度、NMI值、時間復(fù)雜度分析

為驗證本算法的有效性,本文首先將PPC算法(本文算法1)和3WD-PPOC算法進(jìn)行模塊度Q值對比,結(jié)果如表3所示.

表3 基于實驗數(shù)據(jù)集的PPC算法和3WD-PPOC的模塊度Q值對比

從表3可以看出,在引入吸收度后,Zachary網(wǎng)絡(luò)社團(tuán)、Football網(wǎng)絡(luò)社團(tuán)及Dolphins 網(wǎng)絡(luò)社團(tuán)的模塊度均大于沒有引入吸收度的模塊度,即吸收度的引入可以使延遲決策劃分到邊界域的重疊節(jié)點做出2次決策,使劃分后的社團(tuán)結(jié)構(gòu)更加緊密.基于吸收度的決策結(jié)果,對重疊社團(tuán)的劃分好壞有較顯著的影響,邊界域中的重疊節(jié)點的劃分更為合理和穩(wěn)定.

為了進(jìn)一步驗證算法性能,本文將3WD-PPOC算法與經(jīng)典的Newman算法、GN算法、重疊社團(tuán)劃分算法LFM算法、重疊社團(tuán)劃分最新算法(文獻(xiàn)[13]、文獻(xiàn)[18])進(jìn)行模塊度值、NMI值比較,結(jié)果如表4和表5所示.各算法的時間復(fù)雜度如表6所示.

表4 各算法在實驗數(shù)據(jù)集上的Q值對比

表5 各算法在實驗數(shù)據(jù)集上的NMI值對比

表6 算法時間復(fù)雜度對比

從表4～表6可以看出:本文所提出的3WD-PPOC算法和Newman算法、文獻(xiàn)[18]算法的時間復(fù)雜度均為O(n2),其他算法的時間復(fù)雜度都高于O(n2),這表明3WD-PPOC具有良好的計算開銷.在Zachary網(wǎng)絡(luò)、Football網(wǎng)絡(luò)、Dolphins網(wǎng)絡(luò)中,3WD-PPOC都獲得了最高的模塊度值,3WD-PPOC的NMI值在3個實驗數(shù)據(jù)集上均在0.8以上,除了在Zachary網(wǎng)絡(luò)數(shù)據(jù)集上的NMI值略低于Newman算法外,在其他網(wǎng)絡(luò)數(shù)據(jù)集上均優(yōu)于其他比較算法.Newman算法屬于貪心算法的一種,它通過不斷迭代更新形成新的社團(tuán)結(jié)構(gòu),社團(tuán)劃分結(jié)果能較好地刻畫社團(tuán)間的關(guān)系.Newman算法與3WD-PPOC的時間復(fù)雜度相同,但在模塊度方面Newman算法低于3WD-PPOC.在實驗數(shù)據(jù)集上,3WD-PPOC的模塊度Q值比Newman算法、GN算法、LMF算法的分別提升了12.4%、10.6%、44.0%,這表明3WD-PPOC比Newman算法在刻畫社團(tuán)內(nèi)部節(jié)點連接穩(wěn)定性方面具有更好的優(yōu)勢.特別是在Dolphins網(wǎng)絡(luò)上,3WD-PPOC的NMI值為0.935,遠(yuǎn)高于其他比較算法,這說明3WD-PPOC算法對該數(shù)據(jù)集的社團(tuán)劃分精度已達(dá)到相當(dāng)高的程度,劃分結(jié)構(gòu)的質(zhì)量優(yōu)良.

綜上所述,本文所提出的3WD-PPOC算法在處理社團(tuán)網(wǎng)絡(luò)劃分問題上具有一定優(yōu)勢,在保持較好的處理時間開銷下還能有效地對復(fù)雜網(wǎng)絡(luò)節(jié)點進(jìn)行社團(tuán)劃分,且劃分出來的社團(tuán)內(nèi)部節(jié)點具有較好的連接穩(wěn)定性.

4 結(jié)束語

本文將三支決策的思想應(yīng)用于重疊區(qū)域的社團(tuán)劃分,提出了一種基于吸收度的三支決策社團(tuán)劃分算法.該算法根據(jù)社團(tuán)的重要度矩陣和吸收度產(chǎn)生社團(tuán)重疊區(qū),再通過三支決策建立社團(tuán)節(jié)點與邊的界域、正域、負(fù)域的對應(yīng)關(guān)系.三支決策思想的引入,有效提高了社團(tuán)劃分的質(zhì)量.基于真實數(shù)據(jù)的實驗結(jié)果表明:本文所提算法能夠有效地進(jìn)行社團(tuán)劃分,F吸收度刻畫了社團(tuán)邊界的細(xì)節(jié),P吸收度的引入則可以增加邊界域重疊節(jié)點的歸屬程度,即提高了社團(tuán)的模塊度.對比其他社團(tuán)劃分算法,本文所提算法在實驗網(wǎng)絡(luò)中能取得較高的劃分質(zhì)量.劃分后的各社團(tuán)結(jié)構(gòu)緊密,這表明該算法對社團(tuán)重疊節(jié)點的劃分具有較好的穩(wěn)定性.下一步將考慮以提高社團(tuán)的NMI值為目標(biāo)改進(jìn)初始重疊社團(tuán)的劃分方法.