吳 濤,任淑霞,張書博

(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,天津 300387)

0 概述

目前,復(fù)雜網(wǎng)絡(luò)的規(guī)模逐漸增大,有些網(wǎng)絡(luò)包含數(shù)百萬(wàn)甚至數(shù)十億的節(jié)點(diǎn)和邊,這給復(fù)雜網(wǎng)絡(luò)的理解和分析帶來(lái)極大挑戰(zhàn),若不進(jìn)行壓縮,網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊將會(huì)非常密集,人們很難從中獲取有用信息。因此,學(xué)者們開始關(guān)注復(fù)雜網(wǎng)絡(luò)的壓縮問(wèn)題[1],并從不同的角度設(shè)計(jì)基于節(jié)點(diǎn)、基于社區(qū)和基于邊的壓縮方法。

文獻(xiàn)[2]提出一種基于節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)的壓縮算法,該算法通過(guò)刪除非重要性節(jié)點(diǎn)和與之相連的邊來(lái)壓縮網(wǎng)絡(luò),但其采用keep-One和keep-All策略來(lái)補(bǔ)充重要節(jié)點(diǎn)及邊,這會(huì)引入新的節(jié)點(diǎn)和邊,不滿足原網(wǎng)絡(luò)結(jié)構(gòu)的要求。文獻(xiàn)[3]利用k-core的概念提出CABK算法,該算法去掉網(wǎng)絡(luò)中的k-殼節(jié)點(diǎn),將剩下節(jié)點(diǎn)集合中具有相同k-core值的核節(jié)點(diǎn)作為相似節(jié)點(diǎn)進(jìn)行合并,從而達(dá)到壓縮網(wǎng)絡(luò)的目的。文獻(xiàn)[4]從隨機(jī)中心性、度中心性、相對(duì)節(jié)點(diǎn)重要性、PageRank、中介中心性這5個(gè)方面提出5種壓縮方案。但是,上述方案的缺點(diǎn)是刪除節(jié)點(diǎn)和邊后未補(bǔ)充網(wǎng)絡(luò),造成網(wǎng)絡(luò)信息丟失。

文獻(xiàn)[5]提出一種以網(wǎng)絡(luò)社區(qū)為壓縮對(duì)象的SNC算法,該算法在保證社區(qū)間關(guān)聯(lián)的前提下,以保留社區(qū)中重要節(jié)點(diǎn)的方式來(lái)壓縮網(wǎng)絡(luò)。文獻(xiàn)[6]提出一種基于非重要節(jié)點(diǎn)拆分融合的網(wǎng)絡(luò)層次壓縮算法,該算法將網(wǎng)絡(luò)中的非重要性節(jié)點(diǎn)塊拆分融合到相鄰的節(jié)點(diǎn)塊中,實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的快速壓縮。

文獻(xiàn)[7]提出一種基于邊的壓縮算法,其將原始網(wǎng)絡(luò)劃分成2個(gè)團(tuán)體,每個(gè)團(tuán)體只由一棵樹來(lái)保存路徑結(jié)構(gòu),這大幅減少了網(wǎng)絡(luò)中的邊數(shù)量,但缺點(diǎn)是只對(duì)網(wǎng)絡(luò)中的邊進(jìn)行約減,而節(jié)點(diǎn)數(shù)量沒有改變,不利于網(wǎng)絡(luò)分析。文獻(xiàn)[8]提出一種自組織的邊緣捆綁算法,該算法在不減少網(wǎng)絡(luò)節(jié)點(diǎn)和邊的前提下,將相鄰的邊捆綁成束來(lái)對(duì)邊進(jìn)行壓縮。

上述算法主要從復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)、社區(qū)等角度來(lái)設(shè)計(jì)壓縮算法。文獻(xiàn)[9]基于多尺度幾何分析中的顯微鏡策略,提出一種網(wǎng)絡(luò)壓縮策略,實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)及結(jié)構(gòu)的稀疏表示。文獻(xiàn)[10]基于三角形結(jié)構(gòu)提出一種Bound_tri算法,該算法從節(jié)點(diǎn)出發(fā),通過(guò)構(gòu)建三角形集合來(lái)對(duì)網(wǎng)絡(luò)進(jìn)行壓縮,但其缺點(diǎn)是需要同時(shí)訪問(wèn)鄰接矩陣和鄰接列表,導(dǎo)致算法執(zhí)行時(shí)間增加,且Bound_tri算法以度作為選擇標(biāo)準(zhǔn)來(lái)降低計(jì)算規(guī)模,具有片面性,不符合網(wǎng)絡(luò)的實(shí)際情況。

雖然研究人員已經(jīng)從不同角度提出了復(fù)雜網(wǎng)絡(luò)壓縮方法,但如何縮短壓縮時(shí)間、提高壓縮率和保持原網(wǎng)絡(luò)的結(jié)構(gòu)仍然是有待解決的問(wèn)題。為此,本文提出基于三角形子圖的復(fù)雜網(wǎng)絡(luò)過(guò)濾壓縮算法。為縮短壓縮時(shí)間并提高壓縮率,在計(jì)算三角形子圖集合前,提出一種節(jié)點(diǎn)重要性排序算法NRSA,以選出高、低重要性節(jié)點(diǎn)并進(jìn)行過(guò)濾。利用三角形子圖來(lái)保留復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu),以邊為迭代對(duì)象,列出邊兩端的節(jié)點(diǎn)及共同節(jié)點(diǎn)集組成三角形子圖集合,在此基礎(chǔ)上,解析三角形子圖集合以完成網(wǎng)絡(luò)壓縮。

1 節(jié)點(diǎn)重要性排序

1.1 相關(guān)技術(shù)

LeaderRank[11]是一種節(jié)點(diǎn)重要性排序算法,該算法在原網(wǎng)絡(luò)的基礎(chǔ)上增加一個(gè)節(jié)點(diǎn)g,將g與所有節(jié)點(diǎn)相連接,得到一個(gè)強(qiáng)連接的新網(wǎng)絡(luò)。算法首先給除節(jié)點(diǎn)g之外的N個(gè)節(jié)點(diǎn)分配1個(gè)單位的LR值(LLR),接著將1個(gè)單位的LR值分配給與N個(gè)節(jié)點(diǎn)直接相連的鄰居節(jié)點(diǎn),這一過(guò)程根據(jù)式(1)不斷迭代,直至達(dá)到穩(wěn)定狀態(tài)。

(1)

1.2 NRSA算法

LeaderRank算法主要依賴節(jié)點(diǎn)的鄰居節(jié)點(diǎn)來(lái)給其分配LR值,這種計(jì)算方式僅考慮節(jié)點(diǎn)的局部重要性,而忽略節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中的全局重要性。

由圖1可以看出,節(jié)點(diǎn)4的鄰居節(jié)點(diǎn)明顯多于節(jié)點(diǎn)7,LeaderRank算法每次迭代分配給節(jié)點(diǎn)4的LR值大于節(jié)點(diǎn)7,因此,LeaderRank算法認(rèn)為節(jié)點(diǎn)4的重要性高于節(jié)點(diǎn)7。但是,從網(wǎng)絡(luò)的整體結(jié)構(gòu)來(lái)看,節(jié)點(diǎn)7作為連接3個(gè)不同節(jié)點(diǎn)群的中間節(jié)點(diǎn),其在整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)中最重要。為綜合考慮節(jié)點(diǎn)的局部重要性和全局重要性,本文采用鄰度來(lái)反映節(jié)點(diǎn)影響力大小并作為全局重要性的衡量指標(biāo)。

圖1 簡(jiǎn)單無(wú)向網(wǎng)絡(luò)示意圖

定義1(鄰度) 設(shè)vi是網(wǎng)絡(luò)G中的一個(gè)節(jié)點(diǎn),鄰度是G中vi的所有鄰居節(jié)點(diǎn)vj的度的總和,記為AdjDe(vi),計(jì)算公式如下:

AdjDe(vi)=∑De(vj)

(2)

定義2(節(jié)點(diǎn)影響力) 設(shè)vi是網(wǎng)絡(luò)G中的一個(gè)節(jié)點(diǎn),節(jié)點(diǎn)vi的影響力是G中vi的鄰度和本身度之和,記為Node_Ef(vi),計(jì)算公式如下:

Node_Ef(vi)=AdjDe(vi)+De(vi)

(3)

(4)

式(4)表明:

1)ai為與節(jié)點(diǎn)vi相連的鄰接節(jié)點(diǎn),鄰接節(jié)點(diǎn)個(gè)數(shù)越多,節(jié)點(diǎn)vi的排序值就會(huì)越高,符合直觀判斷;

2)vj的節(jié)點(diǎn)影響力越大,vi所得的vj的LR值就會(huì)越大,vi在網(wǎng)絡(luò)結(jié)構(gòu)中就越重要。

NRSA算法步驟如下:

1)使用LeaderRank算法計(jì)算節(jié)點(diǎn)的LR值。

2)通過(guò)式(2)、式(3)計(jì)算節(jié)點(diǎn)vi的鄰度,并得出節(jié)點(diǎn)vi的節(jié)點(diǎn)影響力Node_Ef(vi)。

3)根據(jù)得到的節(jié)點(diǎn)vi的LR值和Node_Ef(vi),使用式(4)計(jì)算得出節(jié)點(diǎn)vi的排序值,并通過(guò)離差標(biāo)準(zhǔn)化將結(jié)果映射到[0,1]區(qū)間上。

2 復(fù)雜網(wǎng)絡(luò)過(guò)濾壓縮算法

2.1 三角形子圖

三角形子圖[12]是復(fù)雜網(wǎng)絡(luò)中一種特別的3-連通子圖。在復(fù)雜網(wǎng)絡(luò)G=(V,E)中,可以用TΔ=(vΔ,eΔ)表示含有3個(gè)節(jié)點(diǎn)和3條邊的三角形子圖,即TΔ〈a,b,c〉={vΔ={a,b,c}?v,eΔ={(a,b),(a,c),(b,c)}?e}。對(duì)于擁有e條邊的復(fù)雜網(wǎng)絡(luò)而言,計(jì)算三角形子圖所需的時(shí)間為O(e3/2)[13],說(shuō)明三角形子圖能在有效時(shí)間內(nèi)被計(jì)算出來(lái)。

2.2 三角形子圖集合

傳統(tǒng)三角形子圖計(jì)算算法是節(jié)點(diǎn)迭代算法,其對(duì)象是網(wǎng)絡(luò)中的節(jié)點(diǎn)。而本文算法是一種邊迭代算法,算法從復(fù)雜網(wǎng)絡(luò)中任意選取一條邊,搜索邊兩端節(jié)點(diǎn)的鄰接列表,檢查其中是否存在共同節(jié)點(diǎn),最后將它們與共同節(jié)點(diǎn)集構(gòu)成三角形子圖集合。例如,選取的邊為(a,b),邊兩端節(jié)點(diǎn)的鄰接列表分別為:Adj(a)={w,h,m,n},Adj(b)={w,h,m,n,l,d}。a、b節(jié)點(diǎn)的共同鄰接節(jié)點(diǎn)為Adj(a)∩Adj(b)={w,h,m,n}。因此,三角形子圖集合為:,,,。邊迭代算法的偽代碼如下:

算法1邊迭代算法

輸入復(fù)雜網(wǎng)絡(luò)G(V,E)

輸出三角形子圖集合Triangle_list

Begin

Triangle_list=?;

for (a,b) in E: //迭代復(fù)雜網(wǎng)絡(luò)的每條邊

If (Adj(a) ∩ Adj(b) != ?):

Node_list = Adj(a) ∩ Adj(b) //節(jié)點(diǎn)鄰接列表的共

//同節(jié)點(diǎn)

End if

For w in Node_list:

Triangle_list.add()//組成三角形子圖,并添

//加到三角形子圖集合中

End for

End for

End

2.3 三角形子圖壓縮算法

復(fù)雜網(wǎng)絡(luò)中通常有上萬(wàn)甚至幾百萬(wàn)個(gè)節(jié)點(diǎn)或者邊,如果直接將列出三角形子圖集合的算法應(yīng)用到復(fù)雜網(wǎng)絡(luò)的壓縮中,算法不僅執(zhí)行效率較低,而且需要極高的代價(jià)才能完全列出所有三角形子圖。因此,在復(fù)雜網(wǎng)絡(luò)中降低列出三角形子圖的代價(jià)是網(wǎng)絡(luò)壓縮的關(guān)鍵。

由圖2可以看出,節(jié)點(diǎn)重要性值的分布十分不均勻,多數(shù)節(jié)點(diǎn)的重要性非常低,小部分節(jié)點(diǎn)的重要性很高。特別地,高重要性與低重要性節(jié)點(diǎn)之間含有的共同鄰接節(jié)點(diǎn)非常少,但尋找它們之間的三角形子圖卻占用大量的計(jì)算時(shí)間。因此,在計(jì)算三角形子圖前過(guò)濾掉高、低重要性節(jié)點(diǎn),可以減小計(jì)算規(guī)模,且能避免較高的計(jì)算代價(jià),從而得到高效的三角形子圖集合。本文將帶過(guò)濾性質(zhì)的三角形子圖壓縮算法定義為NIIET(Node Importance In Edge Triangle)。NIIET算法在壓縮時(shí)只需要訪問(wèn)鄰接列表,鄰接列表中包含邊的方向性,可應(yīng)用于有向圖和無(wú)向圖。

圖2 節(jié)點(diǎn)重要性統(tǒng)計(jì)結(jié)果

圖3是一個(gè)包含8個(gè)節(jié)點(diǎn)、16條邊的簡(jiǎn)單無(wú)向網(wǎng)絡(luò)圖,其中,線上數(shù)字表示線的編號(hào)。如表1、表2所示,邊迭代算法可以得到一個(gè)包含42個(gè)三角形的三角形子圖集合,會(huì)產(chǎn)生27條邊的冗余。假如存儲(chǔ)一個(gè)三角形子圖的邊需要2個(gè)單位,則會(huì)產(chǎn)生54個(gè)單位的冗余。因此,可以通過(guò)過(guò)濾掉高、低重要性節(jié)點(diǎn)來(lái)降低三角形子圖集合的冗余,從而提高壓縮算法的效率。

圖3 原始網(wǎng)絡(luò)結(jié)構(gòu)

表1 原始網(wǎng)絡(luò)節(jié)點(diǎn)重要性統(tǒng)計(jì)結(jié)果

表2 原始網(wǎng)絡(luò)三角形子圖個(gè)數(shù)

由表1、表2可知,NRSA算法計(jì)算出的低重要性節(jié)點(diǎn)為節(jié)點(diǎn)7、高重要性節(jié)點(diǎn)為節(jié)點(diǎn)4。此時(shí)低重要性節(jié)點(diǎn)標(biāo)準(zhǔn)low_percent=15%,高重要性節(jié)點(diǎn)標(biāo)準(zhǔn)high_percent=85%。圖4所示為已經(jīng)過(guò)濾掉高、低重要性節(jié)點(diǎn)后的網(wǎng)絡(luò),運(yùn)用NIIET算法得到的三角形子圖數(shù)量?jī)H為15,如表3所示。三角形子圖集合中僅包含7條冗余的邊,表明過(guò)濾掉高、低重要性節(jié)點(diǎn)后,能以較小的計(jì)算代價(jià)得到一個(gè)具有較少冗余的三角形子圖集合,并能依據(jù)三角形子圖集合解析出一個(gè)壓縮率較高的網(wǎng)絡(luò)。

圖4 節(jié)點(diǎn)過(guò)濾后的網(wǎng)絡(luò)

表3 過(guò)濾后網(wǎng)絡(luò)三角形子圖個(gè)數(shù)

2.4 NIIET算法步驟

NIIET算法步驟如下:

輸入復(fù)雜網(wǎng)絡(luò)G(V,E),G的鄰接列表AdjG

輸出復(fù)雜網(wǎng)絡(luò)G′(V′,E′),三角形子圖集合Trangle_list

1)輸入復(fù)雜網(wǎng)絡(luò)G(V,E),采用NRSA算法計(jì)算出節(jié)點(diǎn)的重要性值。

2)設(shè)置low_percent和high_percent的百分比。

3)根據(jù)百分比篩選出低重要性節(jié)點(diǎn)集合low_nodelist和高重要性節(jié)點(diǎn)集合high_nodelist。

4)遍歷邊E,如果邊兩端的節(jié)點(diǎn)vi和vj位于低或者高重要性節(jié)點(diǎn)集合中,則從與它們相連節(jié)點(diǎn)的鄰接列表中過(guò)濾掉vi和vj。

5)遍歷邊E,如果AdjG(vi)與AdjG(vj)相交,則三角形子圖集合Trangle_list由節(jié)點(diǎn)vi和vj以及它們的共同節(jié)點(diǎn)集構(gòu)成。

6)解析三角形子圖集合Trangle_list,并構(gòu)建出復(fù)雜網(wǎng)絡(luò)G′(V′,E′)。

7)輸出G′(V′,E′)和Trangle_list。

3 實(shí)驗(yàn)結(jié)果與分析

本文分別進(jìn)行節(jié)點(diǎn)重要性和網(wǎng)絡(luò)壓縮分析,并選用6種真實(shí)網(wǎng)絡(luò)來(lái)進(jìn)行實(shí)驗(yàn),分別為Zachary[14]、Football[15]、Neural[15]、Netscience[16]、Polblogs[15]以及Youtube[17]。網(wǎng)絡(luò)參數(shù)由Gephi軟件統(tǒng)計(jì)得出,如表4所示。實(shí)驗(yàn)的運(yùn)行環(huán)境為Intel(R)Core(TM)2 Quad CPU Q8300@2.50 GHz,內(nèi)存為16 GB,64位Win10的PC。

表4 不同網(wǎng)絡(luò)的參數(shù)統(tǒng)計(jì)

3.1 節(jié)點(diǎn)重要性實(shí)驗(yàn)

為證明NRSA算法的合理性,本文使用SIR模型[18]對(duì)PageRank、LeaderRank和NRSA算法在Neural網(wǎng)絡(luò)中進(jìn)行傳播實(shí)驗(yàn)。選取傳播時(shí)間步為40,主要觀察隨著時(shí)間的變化,SIR模型中I(感染)狀態(tài)的節(jié)點(diǎn)個(gè)數(shù)占網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)的比例lin的變化情況。選取NRSA、LeaderRank、PageRank算法的前10%和20%的節(jié)點(diǎn)作為感染節(jié)點(diǎn)進(jìn)行傳播,Neural網(wǎng)絡(luò)的感染實(shí)驗(yàn)結(jié)果如圖5所示。圖5中SIR模型的感染率Infect_rate為0.35,免疫率Res_rate為0.15。圖5(a)、圖5(b)是NRSA算法與LeaderRank算法的對(duì)比結(jié)果。從中可以看出,NRSA算法中l(wèi)in的最高值均超過(guò)LeaderRank算法,并都接近0.8,說(shuō)明NRSA算法選出的節(jié)點(diǎn)在相同時(shí)間步內(nèi)傳播的深度高于LeaderRank算法。從時(shí)間步上來(lái)看,在5～40時(shí)間步內(nèi),由于節(jié)點(diǎn)都從S(易感染)狀態(tài)轉(zhuǎn)變到I(感染)狀態(tài),而免疫率一直不變,2種算法的lin值差距不大。但從5～10時(shí)間步內(nèi)的結(jié)果可得,NRSA算法的斜率高于LeaderRank算法,說(shuō)明NRSA算法挑選出的節(jié)點(diǎn)的傳播速度明顯快于LeaderRank算法。綜上,NRSA算法選出的節(jié)點(diǎn)要比LeaderRank算法選出的節(jié)點(diǎn)更為合理。同理,從圖5(c)、圖5(d)可以看出,NRSA算法的性能更優(yōu)于PageRank算法。

圖5 Neural網(wǎng)絡(luò)傳播仿真結(jié)果

3.2 壓縮實(shí)驗(yàn)

壓縮實(shí)驗(yàn)主要從節(jié)點(diǎn)選擇標(biāo)準(zhǔn)和壓縮效率這2個(gè)部分進(jìn)行分析。由于NIIET算法采用過(guò)濾的方式來(lái)降低計(jì)算規(guī)模,因此需要分析高、低重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)對(duì)壓縮結(jié)果的影響。本文將NIIET算法與Bound_tri、Node_iterator[19]、Edge_iterator_hash[20]、CABK算法從壓縮率[5]、壓縮時(shí)間和信息量保持率[21]等方面進(jìn)行壓縮分析。

3.2.1 節(jié)點(diǎn)選擇標(biāo)準(zhǔn)的影響分析

節(jié)點(diǎn)選擇標(biāo)準(zhǔn)的影響分析具體如下:

1)低重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)分析

在本文實(shí)驗(yàn)中,采用式(5)來(lái)分別計(jì)算節(jié)點(diǎn)壓縮率和邊壓縮率。

(5)

其中,|V|和|V′|表示壓縮前后的節(jié)點(diǎn)數(shù)量,|E|和|E′|表示壓縮前后的邊數(shù)量。

設(shè)置低重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)的范圍為low_percent=[10%,30%],仿真節(jié)點(diǎn)壓縮率、邊壓縮率與選擇標(biāo)準(zhǔn)之間的關(guān)系,結(jié)果如圖6所示。從圖6可以看出,低重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)對(duì)點(diǎn)集壓縮率和邊集壓縮率的影響非常小,原因是低重要性節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的連接關(guān)系較少,使得這類節(jié)點(diǎn)不能構(gòu)成三角形子圖,從而不能參與三角形子圖的計(jì)算。因此,低重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)對(duì)復(fù)雜網(wǎng)絡(luò)壓縮的影響可以忽略。

圖6 低重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)分析

2)高重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)分析

高重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)直接影響NIIET算法的壓縮率及壓縮時(shí)間,并且壓縮得到的三角形子圖數(shù)量也會(huì)受此影響。因此,設(shè)置高重要性節(jié)點(diǎn)的選擇標(biāo)準(zhǔn)范圍為high_percent=[70%,90%],實(shí)驗(yàn)結(jié)果如圖7所示。高重要性節(jié)點(diǎn)的選擇標(biāo)準(zhǔn)設(shè)定越高,計(jì)算出的三角形子圖數(shù)量也越多。但是,過(guò)多的三角形子圖會(huì)導(dǎo)致壓縮時(shí)間變長(zhǎng),因此,本文設(shè)置一個(gè)合適的過(guò)濾標(biāo)準(zhǔn)來(lái)提高壓縮效率并減少壓縮時(shí)間。從圖7(a)、圖7(b)中可以看出,在過(guò)濾標(biāo)準(zhǔn)的范圍為[75%,85%]時(shí),三角形子圖的數(shù)量變化趨勢(shì)不是很大,對(duì)應(yīng)在圖7(a)上的區(qū)間為[1,2],此范圍內(nèi)壓縮率之間相差不大,即壓縮率相對(duì)穩(wěn)定,可以得到一個(gè)較平衡的三角形子圖集合。

圖7 高重要性節(jié)點(diǎn)選擇標(biāo)準(zhǔn)分析

3.2.2 壓縮效率對(duì)比分析

對(duì)壓縮后的復(fù)雜網(wǎng)絡(luò)進(jìn)行量化估計(jì),本文設(shè)置高重要性選擇標(biāo)準(zhǔn)為high_percent=80%,低重要性選擇標(biāo)準(zhǔn)為low_percent=10%,壓縮效果對(duì)比如圖8所示。由圖8(a)、圖8(b)可以得出,Node_iterator和Edge_iterator_hash的壓縮率明顯低于NIIET算法。原因是Node_iterator和Edge_iterator_hash算法需要網(wǎng)絡(luò)中所有節(jié)點(diǎn)和邊參與計(jì)算,它們雖能獲得較多的三角形子圖,但占用太多的壓縮時(shí)間,壓縮率較低。NIIET算法在壓縮時(shí)間和壓縮率上優(yōu)于Bound_tri算法,由于Bound_tri算法在壓縮前需訪問(wèn)鄰接矩陣來(lái)確定節(jié)點(diǎn)之間的連邊關(guān)系,然后修改鄰接列表來(lái)減少網(wǎng)絡(luò)規(guī)模,這種方式極大地增加了時(shí)間成本。此外,鄰接矩陣會(huì)重復(fù)確認(rèn)相連的節(jié)點(diǎn),使計(jì)算后的集合中包含重復(fù)的三角形子圖,導(dǎo)致Bound_tri算法的壓縮率低于NIIET算法。

圖8 4種算法壓縮效果對(duì)比

此外,CABK算法依據(jù)節(jié)點(diǎn)的k-core值和閾值ks來(lái)處理節(jié)點(diǎn),該方式所需的壓縮時(shí)間遠(yuǎn)小于在網(wǎng)絡(luò)中尋找三角形子圖。但是,CABK算法的壓縮率取決于閾值ks,通常情況下,ks選取的是k-core的平均值。若復(fù)雜網(wǎng)絡(luò)中各節(jié)點(diǎn)的k-core值與ks相差不大,則CABK算法的壓縮率要遠(yuǎn)低于NIIET算法。如Football數(shù)據(jù)集,各節(jié)點(diǎn)的k-core值與閾值ks相近,能處理的節(jié)點(diǎn)相對(duì)較少,導(dǎo)致壓縮率低于0.1。而NIIET算法能在不同的數(shù)據(jù)集中列出三角形子圖集合,因此,其不存在數(shù)據(jù)集的限制問(wèn)題。

從圖8(c)可以看出,經(jīng)NIIET算法壓縮后,網(wǎng)絡(luò)的總信息量有所減少,但仍能保持在50%～70%,說(shuō)明壓縮后的網(wǎng)絡(luò)還保留著原網(wǎng)絡(luò)的大部分信息和結(jié)構(gòu),壓縮結(jié)果合理且可信。

4 結(jié)束語(yǔ)

復(fù)雜網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大使得用戶難以從中獲取有價(jià)值的信息。因此,本文提出一種過(guò)濾壓縮算法NIIET,該算法以邊為迭代對(duì)象,通過(guò)列出邊兩端的節(jié)點(diǎn)以及它們所擁有的共同節(jié)點(diǎn)集來(lái)對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行壓縮。在計(jì)算三角形子圖集合之前,本文設(shè)計(jì)NRSA算法來(lái)選出高、低重要性節(jié)點(diǎn),以過(guò)濾掉高、低重要性節(jié)點(diǎn)的方式來(lái)降低計(jì)算規(guī)模。實(shí)驗(yàn)結(jié)果表明,NRSA算法在無(wú)向和有向網(wǎng)絡(luò)中的排序結(jié)果均合理且有效,NIIET算法的壓縮率優(yōu)于Node_iterator等算法,且其壓縮后的網(wǎng)絡(luò)仍能保持很高的信息量和大部分網(wǎng)絡(luò)結(jié)構(gòu)。下一步將從節(jié)點(diǎn)所處的位置、節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)功能的影響等不同角度,探究新的節(jié)點(diǎn)重要性排序方法,并基于三角形子圖結(jié)構(gòu)和復(fù)雜網(wǎng)絡(luò)的k-core等其他性質(zhì),提出一種改進(jìn)的復(fù)雜網(wǎng)絡(luò)壓縮算法。