基于吸收度的三支決策社團劃分算法

萬仁霞,張宇紅,苗奪謙

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

0 引言

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

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

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

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

1 相關(guān)概念

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

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

定義1[19]設節(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的表達式為

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

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

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

定義3[21]鄰接矩陣Wn×n表示在網(wǎng)絡中節(jié)點ei與節(jié)點ej之間的連接關(guān)系,其中wij為在鄰接矩陣中對應的元素,取值為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)絡中每個節(jié)點對于自身的重要度貢獻比值為1.由定理1知,在網(wǎng)絡中的節(jié)點重要度矩陣H是網(wǎng)絡鄰接矩陣的映射.當i≠j時,wij映射為wijDj/〈k〉2;當i=j時,wij映射為1.

1.2 三支決策

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

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

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

2 基于吸收度的三支決策社團劃分算法

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

2.1 社團中的3個域

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

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

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

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

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

圖1 重疊社團3個域的劃分

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

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

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

2.2 吸收度

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

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

表1 損失函數(shù)

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

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

(1)

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

(2)

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

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

性質(zhì)20≤P

2.3 PPC算法流程

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

算法1PPC算法.

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

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

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

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

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

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

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

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

2.4 3WD-PPOC算法流程

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

算法23WD-PPOC算法.

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

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

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

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

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

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

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

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

(vii)構(gòu)建社團正域: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)輸出社團正域QPOS(Ai)(i=1,2,…,k).

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

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

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

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

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

3 算法驗證及分析

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

為了驗證本文所提算法的有效性和可行性,本文采用了3個典型的社交網(wǎng)絡數(shù)據(jù)集作為實驗數(shù)據(jù)集,分別是著名的空手道俱樂部成員網(wǎng)絡(Zachary′s karate club)、足球聯(lián)盟網(wǎng)絡(American college football)和海豚社會關(guān)系網(wǎng)絡(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 評價指標

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

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

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

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

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

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

其中X表示原社團結(jié)構(gòu)的集合;Y表示使用本算法得到的社團結(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來影響社團劃分的效果,圖2直觀展示了本文算法(3WD-PPOC)的吸收度F、P對模塊度Q的影響.從圖2可以看出,對于Zachary數(shù)據(jù)集,當損失函數(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ù)集,當損失函數(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ù)集,當損失函數(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)絡實驗.Zachary空手道俱樂部網(wǎng)絡[30]是美國某大學空手道俱樂部的關(guān)系網(wǎng)絡,該網(wǎng)絡包含34個節(jié)點及78條邊,其中節(jié)點表示俱樂部成員,邊表示成員之間存在的關(guān)系.Zachary空手道俱樂部成員關(guān)系網(wǎng)絡是復雜網(wǎng)絡、社團發(fā)現(xiàn)技術(shù)等領(lǐng)域的典型測試網(wǎng)絡數(shù)據(jù)集,在網(wǎng)絡中的人物關(guān)系因某種原因而被分成若干個小社團,該網(wǎng)絡的原始結(jié)構(gòu)如圖3所示.

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

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

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

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

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

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

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

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

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

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

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

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

3.4 模塊度、NMI值、時間復雜度分析

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

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

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

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

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

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

表6 算法時間復雜度對比

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

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

4 結(jié)束語

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