基于平衡系數的加權網絡改進k核算法

2018-03-02 09:22:29張曦煌

計算機工程 2018年2期

王棹,張曦煌

(江南大學物聯網工程學院,江蘇無錫 214000)

0 概述

復雜網絡節點重要性研究是復雜網絡理論中十分重要的部分,對不同網絡的研究已經發展出很多新的理論[1-3]。這些相關理論已應用到社交網絡[4]、傳播網絡[5]、計算機網絡[6]等各種網絡的分析中,并取得了科學的可靠的結果。由于復雜網絡中的節點數目十分巨大,一個網絡中有成百上千個甚至數十萬個網絡節點,如何高效準確地識別出其中的重要節點變得十分困難,這些關鍵的節點處于網絡中十分重要的位置,對整個網絡的抗毀性[7-8]有至關重要的作用。

目前,在復雜網絡理論中節點重要性的評價方法主要有節點度[9]、網絡介數[10]、接近中心和PankRank[11]。節點度只反映了節點在網絡局部的重要性。介數和接近中心算法從網絡全局角度出發,對節點在網絡中所處的位置給出了較為準確的節點重要性評價,但是由于它們都需要計算所有節點到其他網絡節點的最短路徑[12],因此算法復雜度非常高。文獻[13]提出了基于節點重要度貢獻的節點重要性算法,給出了基于m階鄰居節點重要度貢獻的復雜網絡節點重要度計算方法,該算法取得了較好的實驗結果,但不適用于加權網絡。文獻[14]在文獻[12]的基礎上提出了適用于加權網絡的節點重要度改進算法,但由于算法復雜度高,因此不適合用來分析大型網絡。PankRank算法是由谷歌公司提出的基于隨機游走的網頁重要性排序算法,該算法主要應用在互聯網領域,且不適合用來分析加權網絡。文獻[15-16]提出了k核算法,認為網絡傳播動力學中最重要的節點并非傳統的度最大或介數最大的 Hub 節點,而是具有最大k核值的節點。該算法從網絡整體布局的角度提出了節點重要性的評價方法,具有較低的算法復雜度,能快速地給出超大型網絡的節點重要性評價參數。但該算法同樣只適用于無權網絡。

針對以上算法的問題,本文在k核算法的基礎上,提出基于平衡系數的復雜加權網絡改進k核算法。該算法引入權重值重新定義了更適用于加權網絡的節點k核值指標。將權重值對評價結果的影響定量化,并調整平衡系數以適應不同網絡的特點。

1 復雜網絡

1.1 接近中心算法

節點的接近中心是它到其他所有節點的最短距離之和的倒數,表達式為:

(1)

其中,N是節點總數,kij是從節點vi到節點vj的最短路徑長度。CC值越大,則節點在全局網絡中居于中心位置的程度也越大。

1.2 k核算法

k核算法通過遞歸地移去網絡中所有度值小于或等于k的節點來描述網絡結構特征,揭示網絡層次性質。

圖1 k核算法分解示意圖

該網絡被劃分為3層不同的核:最外層的節點k核值為1,它們處于整個網絡的邊緣,對網絡的影響較小。中間層的節點k核值為2,最里層的節點k核值為3,它們是處于網絡中心的節點,對整個網絡的連通性和完整性有巨大的影響。但是由于k核算法只注重于尋找網絡中最關鍵的節點,因此在k核分析中存在大量k核值相同的節點。例如圖中的節點1～節點12的k核值均為1。這也是k核算法的不足之處。

1.3 基于平衡系數的改進k核算法

1.3.1 基本思路

在Kitsak 等人的研究基礎上,本文提出一種針對復雜加權網絡的k核改進算法。在加權網絡中節點的度k′和k″定義如下:

(2)

(3)

其中,ki表示節點i的度,wij表示與節點i相連的邊的權重。α和β是在改進k核算法中加入的2個調整參數,用來調節節點的k核值和連邊權重值對改進k核值的影響程度。在選擇α和β的值時,要有一定的科學依據,合理地選擇這2個值,才能使算法得出的結果具有與實際情況相符的科學性。當α和β的取值發生變化時,反映加權網絡節點重要性的k′核值相應地也隨之變化。因此,本文定義了k″值,從該值的定義中可以看出,無論k′如何變化,k″都能用來定量衡量每個節點的重要性在整個網絡中的定位,其值類似于反映一個數值在所有數值中所占有的百分比。因此,在實際網絡分析中,當α和β的取值變動時,可以用k″來準確地反映節點重要性的變化情況。

為了確定α和β的取值關系,本文定義了平衡系數E這一概念,其定義如下:

(4)

其中,k表示網絡中節點的k核值,wij表示網絡中節點的連邊權重值之和。通過計算網絡中這2個值的總和和合理地設置平衡系數,能科學地確定k核值和連邊權重在節點重要性評價參數中的權重。在不同的網絡中,可以根據實際網絡的情況調整這一系數。例如在城市路網建設規劃時,節點連邊的權重值即車流量應不超過道路設計的最大承載量,各節點的度值一般不超過4。在分析水網情況時,連邊權重值也應考慮到該河流的最大泄洪能力。在本文實驗中,平衡系數的取值將會多樣化,用以分析該系數對最終實驗結果的影響。當E=1時:

(5)

經過平衡系數調整之后的權重值為:

(6)

在調整之后的網絡中,網絡所有節點的度值與所有連邊之間的權重值在數學意義上具有同樣的重要性。

1.3.2 算法步驟和復雜度分析

改進的加權網絡節點重要性算法步驟如下:

步驟1選出網絡中節點度為1的點并將這些點從網絡中刪除。

步驟2在刪除步驟1中節點后得到的新的網絡圖中找出度為1的網絡節點。

步驟3重復步驟2直至網絡圖中找不出度為1的節點。步驟1～步驟3中找出的所有節點的k核值均為1。

步驟4將網絡圖中所有k核值為1的點從網絡圖中刪除,得到一個新的網絡圖,并尋找該網絡圖中節點度為2的點。

步驟5重復步驟2和步驟3,直至網絡圖中不再有度為2的節點。步驟4和步驟5中找出的節點的k核值均為2。

步驟6按照相同的方法確定網絡中所有節點的k核值。

步驟7計算出網絡中所有節點的k核值的總和與網絡中所有邊的權重值之和。

步驟8確定平衡系數E的值,并計算權重值之和與k核值之和的比值,將每條邊的權重值除以這個比值得到新的權重。

步驟9計算得到加權網絡中的節點k核值k′并進一步計算出k″。

由以上步驟可以看出,改進k核算法并沒有改變k核算法的算法復雜度O(n),只是在得到節點的k核值后根據式(2)算出節點的改進k核值k′,并通過式(3)算出k″。這2個步驟的算法復雜度均為O(n),因此適用于加權網絡的改進k核算法的算法復雜度仍為O(n)。而傳統的介數中心算法,接近中心算法的算法復雜度為O(n3)。因此,改進k核算法更適合用來分析大型網絡的節點重要性。

2 實驗結果與分析

本文實驗加權網絡圖如圖2所示。該加權網絡由34個節點和70條邊構成。實驗分別應用接近中心算法、k核算法以及改進k核算法對網絡中的節點進行分析。在實驗中,改進k核算法的平衡系數E=1,在本文后續的實驗中,將會改變改進k核算法中平衡系數E的取值,對比不同平衡系數取值對改進k核算法最終排序結果的影響。并分析網絡中各類節點在平衡系數發生改變時的重要性變化趨勢。本文加權實驗結果如表1所示。

圖2 本文實驗加權網絡圖

接近中心算法k核算法改進k核算法V1V1V1V3V2V34V34V3V33V33V4V2V9V8V3V4V9V4V20V14V14V29V31V31V2V33V32V24V34V9

表1中分別給出了3種算法的節點重要性排序。由于節點數目較多,因此表中只列出了最關鍵的10個節點及其順序。可以比較明顯地看出3種算法對關鍵節點的篩選結果有明顯的不同。除了V1節點都排在首位之外,其余節點的位置都不相同。其中考慮網絡連邊權重的改進k核算法與原k核算法的結果也出現了較大不同。在原k核算法中,也存在相似節點的重要性難以區分的問題,改進k核算法則很好地解決了這個問題。

為了說明表1中3種算法得出的結果的科學性以及驗證改進k核算法與原k核算法、接近中心算法相比的優勢。在實驗中依次將3種算法最重要的10個關鍵節點從網絡圖中移除,分別得到3種算法在依次移除節點之后的10張網絡圖,從移除節點后網絡中的失效節點數、網絡中最大連通子圖的節點數、網絡損失的連邊權重這3個方面進行分析,得到的實驗結果如圖3～圖5所示。從圖3～圖5中可以看出,當依次從網絡圖中移除關鍵節點后,網絡的失效節點數、最大連通子圖節點數、網絡損失連邊權重都發生了很大變化。改進k核算法在移除關鍵節點后,失效節點數量多于接近中心算法和原k核算法。最大連通子圖節點數明顯少于原k核算法,與接近中心算法在移除關鍵節點后的最大連通子圖節點數相當。

圖3 移除節點數與失效節點數關系

圖4 移除節點數與網絡最大連通子圖節點數關系

圖5 移除節點數與網絡損失連邊權重關系

在圖5中,改進k核算法在移除節點之后損失的連邊權重一直高于原k核算法和接近中心算法。圖3～圖5的實驗結果表明,改進k核算法移除節點后對網絡的破壞效果最明顯,因此,這些節點在網絡中的位置更重要,特別是與原k核算法相比,在3個參數的比較中都較原算法提高了很多,并在整體上優于接近中心算法的結果。

在實驗中,改進k核算法的平衡系數值E=1,在加權網絡分析中,權重對網絡的影響不盡相同,因此在評價網絡節點重要性時,權重的參考量是一個不完全定量因素,改進k核算法引進平衡系數E這一參數來描述這一變化,為了研究平衡系數E的取值對網絡節點重要性評價的影響,在后續實驗中,將平衡系數的取值多樣化,從E=1/32依次乘2至E=32進行11次實驗結果比較,得到的實驗結果如圖6所示。從圖6中可以看出,當平衡系數取值發生變化時,相應地節點的重要性參數值也發生變化,節點連邊較多,權重較大的節點的重要性相對下降,其他節點的重要性相對上升。為了更直觀地分析各個節點的重要性變化情況,實驗選取幾個變化較為明顯的節點,例如重要性下降最明顯的節點V1、V34、V33,重要性上升最明顯的節點V5、V11、V29,以及在平衡系數發生變化時,重要性排序發生改變的幾個節點進行兩兩比較的定量分析,后續實驗的結果如圖7～圖9所示。

圖6 不同平衡系數的改進k核算法結果

圖7 節點重要性分析實驗結果1

圖8 節點重要性分析實驗結果2

圖9 節點重要性分析實驗結果3

從圖7可以看出,隨著平衡系數的增大,k核值在節點重要性評價參數中的比重逐漸提高,權重值的比重相應降低,V1、V34、V33等權重值較大的節點的重要性逐漸下降,V5、V11、V29等權重值較小的節點的重要性逐漸上升。

從圖8中V1與V34、V33的比值曲線中可以看出,隨著平衡系數的增大,V1節點較V34、V33節點的重要性下降速度更快,V5節點較V11、V29節點的重要性上升速度更快,因此,V1節點與V5節點分別是平衡系數增大之后重要性變化最大的2個節點。

圖9中比較了幾個重要性相當的節點重要性變化關系,從圖9中可以看出,當平衡系數較小時,在算法得出的結果中,V32、V7、V30節點更為重要,隨著平衡系數的增大,比值曲線都開始發生變化,當曲線經過y=1這條線時,2個節點的重要性次序發生變化,V31、V9、V14節點的重要性超過V32、V7、V30。V8節點的重要性則隨著平衡系數的增大逐漸逼近節點V9,即比值曲線無限趨近于1。

在平衡系數發生變化的過程中,大部分節點的重要性并沒有發生極大變化,因此,在節點重要性排序中并沒有與平衡系數為1時的排序有太大的差距,即使改變平衡系數,改進k核算法得出的節點重要性排序結果相比原k核算法也有極大地提高,比最短路徑算法得出的結果更具科學性和合理性。

3 結束語

本文提出一種適用于加權網絡的改進k核算法。該算法可解決k核算法只能適用于無權網絡以及k核值差距過小無法區分節點重要性的問題。在本文實驗中,改進k核算法在與k核算法、接近中心的算法比較中得出更準確的結果。該算法在依次刪除改進k核算法結果中最重要的10個節點之后,網絡受到的破壞程度在失效節點數、最大連通子圖、網絡損失權重3項指標上均比k核算法有了大幅提高,整體優于接近中心算法。在后續實驗中,平衡系數的改變相應地改變了算法最終的結果,并分析了節點重要性的變化。但針對不同加權網絡,如何科學地調整平衡系數以取得更精確的實驗結果,將是下一步的研究方向。

[1] 任曉龍,呂琳媛.網絡重要節點排序方法綜述[J].科學通報,2014,59(13) :1175-1197.

[2] 楊博,陳賀昌,朱冠宇,等.基于超鏈接多樣性分析的新型網頁排名算法[J].計算機學報,2014,37(4):833-847.

[3] 段松青,吳斌,王柏.TTRank:基于傾向性轉變的用戶影響力排序[J].計算機研究與發展,2014,51(10):2225-2238.

[4] SEN Pei,LEV M,JOSE S,et al.Searching for Superspreaders of Information in Real-world Social Media[J].Scientific Reports,2014(4):55-67.

[5] 李棟,徐志明,李生,等.在線社會網絡中信息擴散[J].計算機學報,2014,37(1):189-206.

[6] 楊博,陳賀昌,朱冠宇,等.基于超鏈接多樣性分析的新型網頁排名算法[J].計算機學報,2014,37(4):833-847.

[7] 馬潤年,文剛,邵明志,等.基于抗毀性測度的賦權網絡抗毀性評估方法[J].計算機應用研究,2013,30(6):1802-1804.

[8] 李文鋒,符修文.無線傳感器網絡抗毀性[J].計算機學報,2015,38(3):625-647.

[9] 閔磊,劉智,唐向陽,等.基于擴展度的復雜網絡傳播影響力評估算法[J].物理學報,2015,64(8):387-397.

[10] GOH K I,OH E,KAHANG B,et al.Spectra and Eigenvectors of Scale-free Networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,67(2).

[11] BRYAN K,LEI S E T.Eigenvector:The Linear Algebra Behind Google[J].SIAM Review,2006,48(3):569-581.

[12] 唐晉韜,王挺,王戟.適合復雜網絡分析的最短路徑近似算法[J].軟件學報,2011,22(10):2279-2290.

[13] 張喜平,李永樹,劉剛,等.節點重要度貢獻的復雜網絡節點重要度評估方法[J].復雜系統與復雜性科學,2014,11(3):26-32,49.

[14] 王甲生,吳曉平,廖巍,等.改進的加權復雜網絡節點重要度評估方法[J].計算機工程,2012,38(10):74-76.

[15] KITSAK M,GALLOS L K,HAVLIN S,et al.Identifying Influential Spreaders in Complex Networks[J].Nature Physics,2010,6(11):888-893.

[16] 任卓明,劉建國,邵鳳,胡兆龍,郭強.復雜網絡中最小K-核節點的傳播能力分析[J].物理學報,2013,62(10):474-479.