基于非回溯矩陣的有向網(wǎng)絡(luò)拆解方法

王士海卓新建王文璇李慧嘉

(北京郵電大學(xué)理學(xué)院,北京 100876)

0 引言

在復(fù)雜性科學(xué)中,一個(gè)網(wǎng)絡(luò)(圖論中表示為G＝(V,E))是由n個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)集V和m條節(jié)點(diǎn)間的邊組成的邊集E組成[1]。對(duì)于Internet、WWW、大型電力網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)和人際關(guān)系網(wǎng)絡(luò)等許多真實(shí)世界的網(wǎng)絡(luò)都可以由用這種簡(jiǎn)潔的方式來(lái)建模研究[2],通過(guò)這種方法可以將這些網(wǎng)絡(luò)看作是一個(gè)具有獨(dú)立特征又與其他個(gè)體相互連接的節(jié)點(diǎn)的集合,每個(gè)個(gè)體視為網(wǎng)絡(luò)中的節(jié)點(diǎn),節(jié)點(diǎn)間的連接視為網(wǎng)絡(luò)的邊,這種抽象的方法可以直觀地展示真實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),也為深入了解真實(shí)網(wǎng)絡(luò)的狀態(tài)和功能提供了一個(gè)有效研究手段。

但隨著科技與社會(huì)的不斷發(fā)展,流行病毒[3]、計(jì)算機(jī)病毒[4]、謠言傳播[5]或是貪污腐敗[6]在人類(lèi)世界中產(chǎn)生更加嚴(yán)重的負(fù)面效果。然而,移除或者停用一部分網(wǎng)絡(luò)中的點(diǎn)將網(wǎng)絡(luò)分解為幾個(gè)隔離的子部分就可以有效地保護(hù)網(wǎng)絡(luò)的魯棒性和控制網(wǎng)絡(luò)中動(dòng)力學(xué)行為,對(duì)上述所說(shuō)的網(wǎng)絡(luò)中的負(fù)面影響加以遏制,已經(jīng)有實(shí)驗(yàn)證明這種方法可以有效地免疫人群中流行病的傳播[7],阻止社交網(wǎng)絡(luò)中謠言的傳播[8]和防止計(jì)算機(jī)網(wǎng)絡(luò)中病毒的擴(kuò)散[9]等。在復(fù)雜網(wǎng)絡(luò)科學(xué)中存在著一些研究,它們以某種最優(yōu)的方選擇網(wǎng)絡(luò)中的一組節(jié)點(diǎn)子集S,并探究移除S后對(duì)網(wǎng)絡(luò)特性的影響。例如探究移除S后會(huì)使網(wǎng)絡(luò)最大聯(lián)通(強(qiáng))子集怎么變化,在流行病傳播或網(wǎng)絡(luò)病毒傳播中,如果先將S隔離或者感染對(duì)病毒傳播速度有什么影響等。在實(shí)際情況中,選擇并移除網(wǎng)絡(luò)中的節(jié)點(diǎn)子集S往往會(huì)產(chǎn)生一定的成本耗費(fèi)C,在流行病傳播模型中對(duì)于節(jié)點(diǎn)的疫苗接種需要一定的社會(huì)經(jīng)濟(jì)花費(fèi),在計(jì)算機(jī)病毒或者輿論傳播網(wǎng)絡(luò)中移除不同的節(jié)點(diǎn)集在實(shí)際情況中耗費(fèi)的資源也不同。因此產(chǎn)生了一個(gè)組合優(yōu)化問(wèn)題:在約束移除節(jié)點(diǎn)子集S對(duì)網(wǎng)絡(luò)的影響下,使移除成本C最小化。并且移除節(jié)點(diǎn)會(huì)破壞網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)而影響網(wǎng)絡(luò)功能,因此我們需要盡可能少地移除節(jié)點(diǎn),找到一組移除成本C最小的節(jié)點(diǎn)即最小拆解集(在本文中我們考慮拆解成本為單位成本這種最普遍的情況,即最小拆解集為節(jié)點(diǎn)個(gè)數(shù)最少的集合)并移除后將網(wǎng)絡(luò)分解成不相通的多個(gè)子部分就是網(wǎng)絡(luò)拆解[10]。找到最小拆解集是一個(gè)NP-hard問(wèn)題[11],對(duì)于這種問(wèn)題,目前只能尋求有效的近似算法或啟發(fā)式算法,對(duì)于拆解問(wèn)題已經(jīng)有一些基于節(jié)點(diǎn)的度或中心性的遞歸算法,例如2015年提出了名為“集體”影響力(CI)[12]的啟發(fā)式算法,其根據(jù)節(jié)點(diǎn)的度數(shù)和局部鄰居節(jié)點(diǎn)的度決定無(wú)向隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)的歸屬;2016年Alfredo Braunstein提出了拆解大型隨機(jī)無(wú)向網(wǎng)絡(luò)的三段最小和(min-sum)算法[10],對(duì)于大型無(wú)向隨機(jī)網(wǎng)絡(luò),此方法是比較有效的拆解算法;2019年又有任曉龍?zhí)岢隽酸槍?duì)無(wú)向權(quán)重網(wǎng)絡(luò)的網(wǎng)絡(luò)通用拆解算法(gnd算法)[13],此方法考慮當(dāng)節(jié)點(diǎn)的拆除花費(fèi)等比于節(jié)點(diǎn)權(quán)重而為非單位費(fèi)用的情況,先對(duì)網(wǎng)絡(luò)進(jìn)行算子為節(jié)點(diǎn)權(quán)重拉普拉斯矩陣的譜劃分,劃分成功后對(duì)于連接不同劃分之間的邊應(yīng)用節(jié)點(diǎn)權(quán)重覆蓋算法找到可以劃分網(wǎng)絡(luò)的權(quán)重最小點(diǎn)集,從而找到最小花費(fèi)拆解集。gnd相比之前的算法更具有一般性和適用性,它考慮了無(wú)向網(wǎng)絡(luò)中節(jié)點(diǎn)權(quán)重對(duì)網(wǎng)絡(luò)拆解問(wèn)題的影響。但是gnd方法中的算子為點(diǎn)鄰接矩陣,應(yīng)用點(diǎn)鄰接矩陣的譜方法在分析有向網(wǎng)絡(luò)的時(shí)候大多數(shù)會(huì)對(duì)稱(chēng)化鄰接矩陣從而將網(wǎng)絡(luò)無(wú)向化處理[14],這種處理方法不可避免地會(huì)丟失網(wǎng)絡(luò)中的一些信息[15],導(dǎo)致在對(duì)于有向網(wǎng)絡(luò)拆解的最小節(jié)點(diǎn)集的尋找過(guò)程中會(huì)加入一些不必要的節(jié)點(diǎn)進(jìn)而會(huì)造成不必要的拆解。此外基于消息傳遞模型的拆解方法(2020年)[16]和鄰居連邊的敏感拆解算法(2020年)[17]等一些比較新的拆解方法和對(duì)拆解的分析[18,19]等工作。

現(xiàn)有的拆解算法多是在無(wú)向網(wǎng)絡(luò)中開(kāi)展,而針對(duì)有向網(wǎng)絡(luò)的拆解工作很少,但是在如今許多的真實(shí)世界網(wǎng)絡(luò)(如WWW 網(wǎng)絡(luò)、熟人關(guān)系、網(wǎng)絡(luò)電子郵件網(wǎng)絡(luò)、文字關(guān)聯(lián)網(wǎng)絡(luò)和文章引用網(wǎng)絡(luò)等)中的節(jié)點(diǎn)之間的連邊是單向連接的,并不存在無(wú)向網(wǎng)絡(luò)中的相互關(guān)系[20],現(xiàn)有的拆解方法有時(shí)會(huì)不適用于這些有向網(wǎng)絡(luò)的拆解。相對(duì)于無(wú)向網(wǎng)絡(luò)中的拆解,在有向網(wǎng)絡(luò)中的拆解需要考慮到網(wǎng)絡(luò)中節(jié)點(diǎn)連邊的方向。例如在輿論傳播網(wǎng)絡(luò)中一個(gè)有向邊e(圖論中也稱(chēng)之為弧)連接的入點(diǎn)(Innode)為傳播者時(shí),這條邊的出點(diǎn)(Outnode)沒(méi)有被該節(jié)點(diǎn)傳播的可能性,應(yīng)用基于無(wú)向網(wǎng)絡(luò)的拆解方法對(duì)網(wǎng)絡(luò)拆解時(shí)有時(shí)會(huì)忽略節(jié)點(diǎn)間的這種單向關(guān)系,導(dǎo)致會(huì)對(duì)這條邊e進(jìn)行移除,造成不必要的拆解導(dǎo)致對(duì)拆解效果產(chǎn)生影響。傳統(tǒng)的拆解方法忽視了這種網(wǎng)絡(luò)的內(nèi)在機(jī)理對(duì)拆解的影響,針對(duì)這個(gè)問(wèn)題本篇文章應(yīng)用表示邊鄰接關(guān)系的非回溯矩陣作為譜劃分的算子,保留節(jié)點(diǎn)關(guān)系的有向性,并將有向網(wǎng)絡(luò)的拆解和譜劃分方法相結(jié)合,提出了改進(jìn)后的有向網(wǎng)絡(luò)的譜拆解方法(后文簡(jiǎn)稱(chēng)dir方法):直接應(yīng)用有向網(wǎng)絡(luò)中的邊作為拆解單位,將有向網(wǎng)絡(luò)的極大強(qiáng)連通子圖作為拆解主體,在極大強(qiáng)連通子集中應(yīng)用邊鄰接矩陣(非回溯矩陣)的譜特性來(lái)進(jìn)行邊模塊的二劃分,進(jìn)而找到連接兩個(gè)邊模塊的節(jié)點(diǎn)集的重疊點(diǎn)集作為最小拆解集來(lái)拆解網(wǎng)絡(luò),直到拆解到網(wǎng)絡(luò)的指定拆解規(guī)模(最大強(qiáng)連通子圖的節(jié)點(diǎn)個(gè)數(shù))。這種拆解方法可以充分利用非回溯矩陣的優(yōu)良特性,在拆解過(guò)程中可以極大程度地保護(hù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),進(jìn)而通過(guò)實(shí)驗(yàn)驗(yàn)證本文方法適用于有向網(wǎng)絡(luò)的拆解。最后,本文中通過(guò)分析拆解過(guò)程中網(wǎng)絡(luò)的聚類(lèi)系數(shù)、同配性系數(shù)、模塊度函數(shù)等網(wǎng)絡(luò)指標(biāo)的變化,來(lái)分析不同拆解方法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響,并通過(guò)在網(wǎng)絡(luò)中實(shí)驗(yàn)驗(yàn)證了應(yīng)用邊模塊劃分來(lái)拆解網(wǎng)絡(luò)可以極大程度地保留網(wǎng)絡(luò)中的結(jié)構(gòu)信息。

1 模型與方法

如圖1所示本文將邊模塊劃分與網(wǎng)絡(luò)拆解相結(jié)合構(gòu)造了有向網(wǎng)絡(luò)中的網(wǎng)絡(luò)拆解算法,先對(duì)網(wǎng)絡(luò)進(jìn)行邊模塊劃分:采用非回溯矩陣儲(chǔ)存邊的鄰接信息,并以非回溯矩陣作為算子構(gòu)建了最小邊數(shù)拆解函數(shù),通過(guò)對(duì)函數(shù)矩陣近似第二特征向量的求解對(duì)邊模塊進(jìn)行劃分;劃分后找到連接不同邊模塊的最小數(shù)量的邊集,找到邊集中模塊重疊的節(jié)點(diǎn)集,通過(guò)移除這個(gè)節(jié)點(diǎn)集破壞不同模塊之間的連接最終完成拆解。

圖1 有向網(wǎng)絡(luò)拆解流程圖

應(yīng)用本文方法對(duì)上述有向網(wǎng)絡(luò)進(jìn)行拆解:根據(jù)非回溯矩陣的譜特性對(duì)有向網(wǎng)絡(luò)的邊二劃分為左右兩個(gè)紅藍(lán)不同模塊;找到連接這兩個(gè)不同邊模塊的重疊節(jié)點(diǎn)5和6,對(duì)節(jié)點(diǎn)5和6進(jìn)行移除并斷開(kāi)與之相連的邊就可以將該有向網(wǎng)絡(luò)分為兩個(gè)互不相連的子部分。這種移除邊模塊重疊節(jié)點(diǎn)的拆解方法相對(duì)于之前的拆解方法所需拆解步驟更少,不需要找最小節(jié)點(diǎn)覆蓋集,并且對(duì)應(yīng)的拆解花費(fèi)更少(應(yīng)用傳統(tǒng)分解方法找到的點(diǎn)為5、6、7、12),更適用于有向網(wǎng)絡(luò)。

1.1 非回溯矩陣

在有向網(wǎng)絡(luò)G中,i、j、k、l都為V中的節(jié)點(diǎn),根據(jù)非回溯隨機(jī)游走的定義,只有當(dāng)j＝k,并且i≠l,有向邊i→j與另一條有向邊k→l相連。在有向網(wǎng)絡(luò)中B是一個(gè)m?m的非回溯矩陣,本文用這個(gè)非回溯矩陣來(lái)表示有向網(wǎng)絡(luò)中的邊的鄰接關(guān)系,定義為

非回溯矩陣B不同于鄰接矩陣A,B將每條有向邊作為元素,在矩陣中表示邊之間的相互鄰接關(guān)系,所以又被叫做邊鄰接矩陣,在文章[21]中已經(jīng)表明非回溯算子的優(yōu)秀特性,它的譜特性與點(diǎn)鄰接矩陣A或者其他矩陣相比在網(wǎng)絡(luò)中都有更好的性能表現(xiàn),特別是它的第二特征向量對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)劃分所表現(xiàn)出的強(qiáng)分離性;與此同時(shí),真實(shí)世界中的有向網(wǎng)絡(luò)往往具有比較稀疏的結(jié)構(gòu)和較大的規(guī)模,本文中我們所應(yīng)用的非回溯矩陣B相比于點(diǎn)鄰接矩陣A在稀疏網(wǎng)絡(luò)中也具有良好的表現(xiàn)。B作為邊的鄰接矩陣,矩陣中存放的是網(wǎng)絡(luò)中邊之間的聯(lián)系,對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)的信息并不敏感,從而避免了拆解時(shí)傾向于移除度比較大的節(jié)點(diǎn)從而造成破壞網(wǎng)絡(luò)的連通子集的情況[22],從而最大限度地保留了有向網(wǎng)絡(luò)中的結(jié)構(gòu)信息。并且通過(guò)實(shí)驗(yàn)證明了應(yīng)用非回溯矩陣進(jìn)行拆解保存有向網(wǎng)絡(luò)中邊的單向連接關(guān)系,降低節(jié)點(diǎn)的拓?fù)湫畔?duì)所選拆解點(diǎn)集的擾動(dòng),有效避免直接使用有向網(wǎng)絡(luò)鄰接矩陣來(lái)做譜算法算子時(shí)的網(wǎng)絡(luò)信息丟失問(wèn)題。

1.2 拆解目標(biāo)函數(shù)

在這部分我們考慮將網(wǎng)絡(luò)按照邊的性質(zhì)劃分為兩個(gè)相等規(guī)模模塊的一般情況下,最小化兩個(gè)不同模塊間的邊的數(shù)量。我們已經(jīng)應(yīng)用非回溯矩陣儲(chǔ)存有向網(wǎng)絡(luò)中邊鄰接信息,因?yàn)樵诓鸾鈫?wèn)題中我們所最終要移除的是不同邊模塊上所有重疊的節(jié)點(diǎn),邊的權(quán)重對(duì)最小節(jié)點(diǎn)集的選取不造成影響,所以我們?cè)O(shè)定每條邊的權(quán)重為單位權(quán)重。我們將邊網(wǎng)絡(luò)中的m條邊根據(jù)對(duì)應(yīng)的特性二劃分為兩個(gè)相等規(guī)模m/2模塊。我們對(duì)于網(wǎng)絡(luò)中任意一條有向邊i→j,i,j∈N定義一個(gè)指標(biāo)變量s i→j∈R m,并假設(shè)如果這條邊i→j屬于劃分模塊1,則s i→j＝1;如果邊屬于劃分模塊2,則s i→j＝－1。所以我們得到

1.3 劃分向量

由于大規(guī)模網(wǎng)絡(luò)連邊很多,它對(duì)應(yīng)的B的第二特征向量很難精確得到[24],本文中我們應(yīng)用傳統(tǒng)的冪律迭代模型來(lái)進(jìn)行對(duì)第二小特征值的簡(jiǎn)單精煉的近似算法。對(duì)于矩陣B′,B′有m個(gè)實(shí)非負(fù)特征值0≤λm～＝2dmax－λm≤…≤λ2～ ,其對(duì)應(yīng)的特征向量為v(1),v(2),…,v(m),是R m空間上的正交基,我們定義矩陣B中元素的最大度為dmax,x,y代表矩陣的行列,通過(guò)計(jì)算1-范式我們得到譜上界。

算法1 近似特征向量算法輸入:非回溯矩陣B,網(wǎng)絡(luò)邊數(shù)m,v 1 ＝(1,1,…,1)T輸出:近似第二特征向量v 1:隨機(jī)在單位球面上選取向量v;2:v ←v－v T v v T v 1·v 1;3:For i＝1 toτ(m);4: v ←B～v||B～v||;5:End for;6:返回v。

算法2 有向網(wǎng)絡(luò)拆解算法(dir方法)輸入:網(wǎng)絡(luò)G輸出:最小拆解集L S,最小拆解費(fèi)用c 1:選取網(wǎng)絡(luò)中最大強(qiáng)連通子圖GSC 并根據(jù)式(1)計(jì)算其非回溯矩陣B GSC;2:初始化L S、c 為0;3:利用公式(3)計(jì)算B GSC對(duì)應(yīng)的B′;4:利用算法1獲得劃分向量v(2)并二劃分最大強(qiáng)連通子圖為兩個(gè)邊模塊;5:找到連接兩個(gè)邊模塊的邊集,創(chuàng)建劃分子圖;6:找到劃分子圖中重疊點(diǎn)集S;7:將S 從網(wǎng)絡(luò)G 中移除,并更新網(wǎng)絡(luò)G;8:將S 并入L S,并更新L S、c 以及B GSC;9:如果最大強(qiáng)連通子圖的規(guī)模GSCsize＜目標(biāo)拆解規(guī)模C,返回L S和c;否則,回到步驟3。

1.4 有向網(wǎng)絡(luò)拆解

算法2提供了一個(gè)可以將網(wǎng)絡(luò)重復(fù)地拆解到指定規(guī)模的遞歸解法。我們將拆解規(guī)模規(guī)定為極大強(qiáng)連通子集GSC中點(diǎn)的個(gè)數(shù),在這個(gè)算法中我們意圖將有向網(wǎng)絡(luò)拆解至拆解規(guī)模小于目標(biāo)規(guī)模C,根據(jù)此思想我們定義上述算法。算法輸入是有向網(wǎng)絡(luò)的點(diǎn)邊拓?fù)浣Y(jié)構(gòu),最后的輸出是將此有向網(wǎng)絡(luò)拆解到指定規(guī)模時(shí)的最小節(jié)點(diǎn)拆解集和所需要的拆解花費(fèi);算法的第1步先將網(wǎng)絡(luò)的極大強(qiáng)連通子集作為有向網(wǎng)絡(luò)的拆解主體,這樣可以過(guò)濾掉網(wǎng)絡(luò)中與網(wǎng)絡(luò)拆解無(wú)關(guān)緊要的節(jié)點(diǎn)及邊,提高有向網(wǎng)絡(luò)的拆解效率,并且選取強(qiáng)連通子集作為拆解主體可以直接與常用的無(wú)向網(wǎng)絡(luò)的連通子集形成對(duì)比,可以避免將網(wǎng)絡(luò)無(wú)向化來(lái)滿足無(wú)向網(wǎng)絡(luò)拆解條件從而造成多余拆解;通過(guò)判斷網(wǎng)絡(luò)的極大強(qiáng)連通子集的規(guī)模來(lái)控制流程的進(jìn)行;第2步將最小拆解集和拆解花費(fèi)初始化為0算法的第3步生成最大強(qiáng)連通子圖的非回溯矩陣的拉普拉斯矩陣以便對(duì)邊模塊的下一步劃分;第4步通過(guò)計(jì)算＝2dmax－B′,并應(yīng)用特征向量近似算法求得第二特征值所對(duì)應(yīng)的特征向量,用來(lái)對(duì)邊模塊進(jìn)行劃分;5、6找到邊模塊間重合的節(jié)點(diǎn)集并在整個(gè)網(wǎng)絡(luò)G中進(jìn)行移除,第7步將要移除的節(jié)點(diǎn)加入拆解集并更新網(wǎng)絡(luò)最大強(qiáng)連連通子集和拆解集;第八步更新最小拆解集以及拆解花費(fèi);第9步判斷網(wǎng)絡(luò)的最大強(qiáng)連通子集規(guī)模是否達(dá)到目標(biāo)拆解規(guī)模。此遞歸算法可以得到把有向網(wǎng)絡(luò)拆解到指定規(guī)模的一組最少的不同邊模塊之間連接的節(jié)點(diǎn)集。

1.5 算法復(fù)雜度

本文應(yīng)用的近似特征向量的時(shí)間復(fù)雜度等于迭代次數(shù)τ(m)乘以矩陣B～與向量v之積的復(fù)雜度,即O(τ(m)m2),其中m為網(wǎng)絡(luò)邊數(shù)。

2 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文提出的dir方法在有向網(wǎng)絡(luò)中的適用性,我們將其應(yīng)用在人工有向ER 網(wǎng)絡(luò)和BA 網(wǎng)絡(luò)以及真實(shí)網(wǎng)絡(luò)中,并將拆解結(jié)果與兩種比較常用的方法(gnd算法和min-sum 方法)進(jìn)行比較,實(shí)驗(yàn)選取了表1的數(shù)據(jù)集,在不同的人工有向網(wǎng)絡(luò)和大規(guī)模的真實(shí)網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)對(duì)比(為了方便比較,文中的拆解規(guī)模和拆解花費(fèi)均為所占比例)。

表1 網(wǎng)絡(luò)數(shù)據(jù)集

任曉龍等學(xué)者[13]在之前的文章中已經(jīng)證明了在無(wú)向網(wǎng)絡(luò)中當(dāng)網(wǎng)絡(luò)拆解花費(fèi)為單位花費(fèi)(節(jié)點(diǎn)個(gè)數(shù))和非單位花費(fèi)(基于節(jié)點(diǎn)度)時(shí)gnd方法相比與min-sum 和信息傳遞等其他算法都有較高的拆解效率,當(dāng)拆解規(guī)模相同時(shí)gnd方法比其他算法有更低的拆解花費(fèi),gnd可以以更小的拆解花費(fèi)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行更大的破壞,該方法在無(wú)向網(wǎng)絡(luò)的拆解中相對(duì)其他算法有著比較好的表現(xiàn),本文將dir方法與gnd方法和min-sum 方法進(jìn)行實(shí)驗(yàn)比較。

圖2和圖3是不同方法在不同有向網(wǎng)絡(luò)中的拆解結(jié)果,給出了拆解規(guī)模和拆解花費(fèi)的對(duì)應(yīng)曲線圖,縱坐標(biāo)拆解規(guī)模為最大(強(qiáng))連通子圖的節(jié)點(diǎn)數(shù)占比,橫坐標(biāo)拆解花費(fèi)為拆解到縱坐標(biāo)所示規(guī)模時(shí)最小拆解集的節(jié)點(diǎn)數(shù)量占比。如圖2所示,在比較稠密的ER 隨機(jī)網(wǎng)絡(luò)中,當(dāng)所需拆解規(guī)模小于0.25時(shí),dir方法拆解花費(fèi)比gnd與min-sum 方法所需的拆解花費(fèi)都要小;在平均度為10的人工BA 有向網(wǎng)絡(luò)中dir方法拆解花費(fèi)則明顯小于其他兩個(gè)方法。并且在比較稀疏的真實(shí)有向網(wǎng)絡(luò)中(圖2)進(jìn)行拆解實(shí)驗(yàn)時(shí),將網(wǎng)絡(luò)拆解到同一指定規(guī)模時(shí)本篇文章所提出的方法所需要的花費(fèi)要少于其他方法,產(chǎn)生區(qū)別的原因是gnd與min-sum 等方法將網(wǎng)絡(luò)中的最大連通子圖作為拆解主體,本文所提出的方法將網(wǎng)絡(luò)的最大強(qiáng)連通子集作為拆解主體,當(dāng)網(wǎng)絡(luò)足夠稠密時(shí)應(yīng)用有向網(wǎng)絡(luò)中的最大強(qiáng)連通子圖和連通子圖的規(guī)模差別不大,但在比較稀疏的網(wǎng)絡(luò)(比如WEKI網(wǎng)絡(luò))中時(shí),應(yīng)用有向網(wǎng)絡(luò)的最大強(qiáng)連通子圖進(jìn)行拆解的花費(fèi)要明顯低于gnd與dir方法。實(shí)驗(yàn)表明了本方法在有向網(wǎng)絡(luò)中進(jìn)行拆解的花費(fèi)少的優(yōu)越性,說(shuō)明本文提出的方法在有向網(wǎng)絡(luò)的網(wǎng)絡(luò)拆解的高效性。

圖2 有向ER 隨機(jī)網(wǎng)絡(luò)和有向BA 隨機(jī)網(wǎng)絡(luò)拆解花費(fèi)與拆解規(guī)模對(duì)應(yīng)曲線圖

圖3 有向真實(shí)網(wǎng)絡(luò)拆解花費(fèi)與拆解規(guī)模對(duì)應(yīng)曲線圖

接下來(lái)探究本文中所提出的不同拆解方法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響,通過(guò)將不同拆解方法應(yīng)用到不同網(wǎng)絡(luò)中,并通過(guò)比較拆解過(guò)程網(wǎng)絡(luò)的聚類(lèi)系數(shù)[25]和同配性系數(shù)[26]來(lái)證明本文方法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)信息可以極大限度保留的優(yōu)越性。

圖論中聚類(lèi)系數(shù)用于衡量節(jié)點(diǎn)聚集的程度。有證據(jù)表明,大多數(shù)現(xiàn)實(shí)世界的網(wǎng)絡(luò)中,特別是在社交網(wǎng)絡(luò)中,節(jié)點(diǎn)傾向于創(chuàng)建相對(duì)緊密聯(lián)系的群體;這種可能性往往大于在兩個(gè)節(jié)點(diǎn)之間隨機(jī)建立關(guān)系的平均概率,對(duì)于一個(gè)網(wǎng)絡(luò)G＝(V,E),形式上由一組節(jié)點(diǎn)和節(jié)點(diǎn)之間的連邊組成,邊連接節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)v i的鄰域N i被定義為其緊鄰的節(jié)點(diǎn),N i＝{v j:e ij∈E∨e ji∈E}。有向網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的局部聚類(lèi)系數(shù)C i為

作為全局聚類(lèi)系數(shù)的代替,Watt和Strogatz[20]將所有頂點(diǎn)局部聚類(lèi)系數(shù)的平均值作為網(wǎng)絡(luò)整體聚類(lèi)水平

在這里我們通過(guò)觀察拆解過(guò)程中網(wǎng)絡(luò)全局聚類(lèi)系數(shù)的變化來(lái)比較dir與其他兩個(gè)拆解方法對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)連接程度的影響進(jìn)而探究對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響。

實(shí)驗(yàn)首先對(duì)人工ER 隨機(jī)網(wǎng)絡(luò)和BA 網(wǎng)絡(luò)進(jìn)行拆解,拆解花費(fèi)與聚類(lèi)系數(shù)關(guān)系圖由上圖4所示,在人工ER隨機(jī)網(wǎng)絡(luò)中當(dāng)拆解花費(fèi)小于0.7時(shí),本文所提dir方法所對(duì)應(yīng)的平均聚類(lèi)系數(shù)的曲線相對(duì)于gnd和minsum 的曲線更為平穩(wěn),并且在BA 網(wǎng)絡(luò)中也是先到達(dá)一個(gè)平穩(wěn)狀態(tài)。本文提出的拆解方法對(duì)于整個(gè)網(wǎng)絡(luò)的聚類(lèi)系數(shù)的擾動(dòng)相對(duì)于gnd和min-sum 更小,這體現(xiàn)了本文所通過(guò)邊模塊劃分來(lái)移除模塊間重疊節(jié)點(diǎn)的優(yōu)越性,dir對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響相對(duì)于直接刪除網(wǎng)絡(luò)中節(jié)點(diǎn)的方法更小;在ER 隨機(jī)網(wǎng)絡(luò)中三種方法都會(huì)在一定時(shí)間內(nèi)隨著拆解的進(jìn)行網(wǎng)絡(luò)聚類(lèi)系數(shù)不斷上升,這是因?yàn)榇藭r(shí)拆解已經(jīng)讓網(wǎng)絡(luò)中的節(jié)點(diǎn)開(kāi)始出現(xiàn)越來(lái)越多成團(tuán)現(xiàn)象。在真實(shí)網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)得到的結(jié)果圖5,可以看到在真實(shí)世界的有向網(wǎng)絡(luò)中隨著拆解花費(fèi)的提高兩種拆解方法都會(huì)使得網(wǎng)絡(luò)中的聚類(lèi)系數(shù)下降,這與真實(shí)網(wǎng)絡(luò)的稀疏性有關(guān),對(duì)真實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)的拆解會(huì)使得節(jié)點(diǎn)間的集聚現(xiàn)象變少,群體間的連接變得稀疏,但依然可以從圖中看出本文方法所對(duì)應(yīng)的曲線比gnd與min-sum 方法更為平緩,在拆解過(guò)程中對(duì)真實(shí)網(wǎng)絡(luò)的這種聚集現(xiàn)象的影響比這兩種方法方法更小;并且相對(duì)而言min-sum 方法會(huì)對(duì)的網(wǎng)絡(luò)的這種聚集現(xiàn)象影響更為明顯,因?yàn)閙in-sum 方法傾會(huì)向于移除網(wǎng)絡(luò)中度比較大的節(jié)點(diǎn),對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)信息保護(hù)能力較小。

圖4 有向ER 隨機(jī)網(wǎng)絡(luò)和有向BA 隨機(jī)網(wǎng)絡(luò)拆解花費(fèi)與聚類(lèi)系數(shù)對(duì)應(yīng)曲線圖

圖5 真實(shí)網(wǎng)絡(luò)拆解花費(fèi)與聚類(lèi)系數(shù)對(duì)應(yīng)曲線圖

同配性系數(shù)是用來(lái)衡量網(wǎng)絡(luò)是同配還是異配的指標(biāo),用來(lái)考察網(wǎng)絡(luò)中度值相近的節(jié)點(diǎn)是否傾向于和它近似的節(jié)點(diǎn)相連互相連接,可以用皮爾森系數(shù)r(度-度相關(guān)性)來(lái)刻畫(huà),r＞0表示整個(gè)網(wǎng)絡(luò)呈現(xiàn)同配性結(jié)構(gòu),度大的節(jié)點(diǎn)傾向于和度大的節(jié)點(diǎn)相連,r＜0表示整個(gè)網(wǎng)絡(luò)呈現(xiàn)異配性,r＝0表示網(wǎng)絡(luò)結(jié)構(gòu)不存在相關(guān)性。實(shí)驗(yàn)中通過(guò)觀察拆解過(guò)程中對(duì)網(wǎng)絡(luò)同配性指標(biāo)的影響來(lái)分析本算法的拆解對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的改變。

如圖6圖7所示本文所提dir方法在對(duì)網(wǎng)絡(luò)的同配性的改變也比其他兩種方法更小,無(wú)論是在ER 隨機(jī)網(wǎng)絡(luò)還是在真實(shí)網(wǎng)絡(luò)中當(dāng)拆解費(fèi)用小于0.7時(shí),藍(lán)色曲線都更為平緩,對(duì)網(wǎng)絡(luò)全局的同配性的改變更小,移除邊模塊間重疊節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)同配性的影響相對(duì)gnd和min-sum 方法也更小。

圖6 有向ER 隨機(jī)網(wǎng)絡(luò)和有向BA 隨機(jī)網(wǎng)絡(luò)拆解花費(fèi)與同配性系數(shù)對(duì)應(yīng)曲線圖

圖7 真實(shí)網(wǎng)絡(luò)拆解花費(fèi)與同配性系數(shù)對(duì)應(yīng)曲線圖

圖8 真實(shí)網(wǎng)絡(luò)拆解花費(fèi)與模塊度Q 對(duì)應(yīng)曲線圖

應(yīng)用本方法拆解過(guò)程中的模塊度Q的計(jì)算如圖7所示,可以看到兩張圖片中當(dāng)拆費(fèi)用小于0.8的時(shí)候模塊度Q隨著拆解花費(fèi)的變大而變大,說(shuō)明拆解過(guò)程中移除點(diǎn)的同時(shí)也隨之刪掉了不同社團(tuán)間的團(tuán)間邊,對(duì)于有效地社團(tuán)劃分有著一定的促進(jìn)作用,當(dāng)花費(fèi)大于0.88時(shí)拆解會(huì)破壞掉社團(tuán)內(nèi)部的團(tuán)間邊導(dǎo)致模塊度Q急劇下降。

綜上所有實(shí)驗(yàn)我們提出的有向網(wǎng)絡(luò)拆解(dir)方法無(wú)論在人工有向網(wǎng)絡(luò)還是在真實(shí)有向網(wǎng)絡(luò)中都有相對(duì)于gnd和min-sum 算法都有較高的拆解效率,把網(wǎng)絡(luò)拆解到相同規(guī)模時(shí)dir法所需花費(fèi)最少;同時(shí)通過(guò)比較拆解過(guò)程中的聚類(lèi)系數(shù)和同配性系數(shù)也證明了本文方法可以在拆解過(guò)程中降低拆解對(duì)網(wǎng)絡(luò)聚類(lèi)系數(shù)和同配性系數(shù)的影響,有效地保留網(wǎng)絡(luò)中的信息;也通過(guò)實(shí)驗(yàn)探究本文方法對(duì)網(wǎng)絡(luò)模塊度的影響,當(dāng)拆解規(guī)模小于一個(gè)閾值時(shí)本文拆解方法對(duì)網(wǎng)絡(luò)社團(tuán)劃分有一定促進(jìn)作用。

3 結(jié)論

本篇文章針對(duì)有向網(wǎng)絡(luò)的拆解問(wèn)題提出了一個(gè)有效的拆解方法:將邊模塊劃分與網(wǎng)絡(luò)拆解相結(jié)合,利用非回溯矩陣構(gòu)建邊拆解最小拆解邊數(shù)函數(shù),通過(guò)對(duì)花費(fèi)函數(shù)的特征向量近似求解找到邊模塊間重疊的節(jié)點(diǎn)進(jìn)行拆解移除。本方法不同于傳統(tǒng)的無(wú)向網(wǎng)絡(luò)拆解方法,考慮了有向網(wǎng)絡(luò)中的節(jié)點(diǎn)間的單向關(guān)系,充分利用非回溯矩陣優(yōu)秀的譜特性對(duì)有向網(wǎng)絡(luò)進(jìn)行劃分,在網(wǎng)絡(luò)拆解過(guò)程中移除邊模塊間重疊的點(diǎn)也保證了拆解的效率和降低了拆解對(duì)網(wǎng)絡(luò)總體結(jié)構(gòu)的影響。并且通過(guò)將本文dir方法在不同的人工有向網(wǎng)絡(luò)和真實(shí)有向網(wǎng)絡(luò)中與其他方法進(jìn)行實(shí)驗(yàn)比較,證明了dir方法在有向網(wǎng)絡(luò)的網(wǎng)絡(luò)拆解的高效性,同時(shí)也驗(yàn)證了將邊模塊劃分應(yīng)用到網(wǎng)絡(luò)拆解中非回溯算子的應(yīng)用對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的低擾動(dòng)。實(shí)驗(yàn)結(jié)果表明應(yīng)用本方法對(duì)網(wǎng)絡(luò)進(jìn)行拆解可以達(dá)到較低小耗費(fèi)的同時(shí)極大程度的保護(hù)有向網(wǎng)絡(luò)中的結(jié)構(gòu)信息。