基于三角形子圖的復雜網(wǎng)絡過濾壓縮算法

吳 濤,任淑霞,張書博

(天津工業(yè)大學 計算機科學與技術學院,天津 300387)

0 概述

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

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

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

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

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

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

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

1.1 相關技術

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

(1)

1.2 NRSA算法

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

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

圖1 簡單無向網(wǎng)絡示意圖

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

AdjDe(vi)=∑De(vj)

(2)

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

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

(3)

(4)

式(4)表明:

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

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

NRSA算法步驟如下:

1)使用LeaderRank算法計算節(jié)點的LR值。

2)通過式(2)、式(3)計算節(jié)點vi的鄰度,并得出節(jié)點vi的節(jié)點影響力Node_Ef(vi)。

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

2 復雜網(wǎng)絡過濾壓縮算法

2.1 三角形子圖

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

2.2 三角形子圖集合

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

算法1邊迭代算法

輸入復雜網(wǎng)絡G(V,E)

輸出三角形子圖集合Triangle_list

Begin

Triangle_list=?;

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

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

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

//同節(jié)點

End if

For w in Node_list:

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

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

End for

End for

End

2.3 三角形子圖壓縮算法

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

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

圖2 節(jié)點重要性統(tǒng)計結(jié)果

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

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

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

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

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

圖4 節(jié)點過濾后的網(wǎng)絡

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

2.4 NIIET算法步驟

NIIET算法步驟如下:

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

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

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

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

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

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

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

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

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

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

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

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

3.1 節(jié)點重要性實驗

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

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

3.2 壓縮實驗

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

3.2.1 節(jié)點選擇標準的影響分析

節(jié)點選擇標準的影響分析具體如下:

1)低重要性節(jié)點選擇標準分析

在本文實驗中,采用式(5)來分別計算節(jié)點壓縮率和邊壓縮率。

(5)

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

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

圖6 低重要性節(jié)點選擇標準分析

2)高重要性節(jié)點選擇標準分析

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

圖7 高重要性節(jié)點選擇標準分析

3.2.2 壓縮效率對比分析

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

圖8 4種算法壓縮效果對比

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

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

4 結(jié)束語

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