一種基于度排序的節(jié)點(diǎn)重要性排序算法

張玫,解建軍,馮科展

（1.河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河北石家莊050024；2.河北省計算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室,河北石家莊050024）

一種基于度排序的節(jié)點(diǎn)重要性排序算法

張玫1,2,解建軍1,2,馮科展1,2

（1.河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河北石家莊050024；2.河北省計算數(shù)學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室,河北石家莊050024）

為有效評估復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性,特提出了一種基于經(jīng)典度排序方法的合度排序算法.合度排序算法是在節(jié)點(diǎn)度的基礎(chǔ)上提出了鄰度和合度的概念,通過計算每個節(jié)點(diǎn)的合度值來評估節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性,即合度值越大,節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性越高.并利用經(jīng)典的度排序算法、接近度排序算法及新提出的合度排序算法對同一網(wǎng)絡(luò)拓?fù)鋱D的節(jié)點(diǎn)進(jìn)行排序,證明了合度排序算法的有效性.

復(fù)雜網(wǎng)絡(luò)；節(jié)點(diǎn)重要性；度；排序

自從17世紀(jì)瑞士科學(xué)家Euler研究七橋問題開始,很多學(xué)科的科研人員也都嘗試?yán)脠D論知識開展研究,其中包括社會科學(xué)、生命科學(xué)、信息科學(xué)等.無論是人類社會網(wǎng)絡(luò)、牲畜群網(wǎng)絡(luò)還是Web互聯(lián)網(wǎng),它們都是由眾多復(fù)雜的節(jié)點(diǎn)和連接方式構(gòu)成的龐大網(wǎng)絡(luò),都屬于復(fù)雜網(wǎng)絡(luò)[1].通過對復(fù)雜網(wǎng)絡(luò)的分析研究,得出與實(shí)際問題相關(guān)的規(guī)律,從而應(yīng)用到解決實(shí)際問題中去.例如人類社會關(guān)系網(wǎng)絡(luò)[2],通過節(jié)點(diǎn)排序可以迅速找到某個人,這與著名的“六度分離（six degrees of separation）”實(shí)驗(yàn)[3]類似；利用謠言傳播網(wǎng)絡(luò)[4],可以挖掘出始作俑者,從而切斷謠言傳播途徑；通過世界航空網(wǎng)絡(luò)[5],可以迅速找出到達(dá)目的地的最合適路徑等.那么,如何定量地分析網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性就成為復(fù)雜網(wǎng)絡(luò)研究的一個重要方面.經(jīng)典的度排序算法存在著不足,本文從如何解決這一問題入手,受復(fù)雜網(wǎng)絡(luò)中熟人免疫機(jī)制的啟發(fā),在考慮節(jié)點(diǎn)自身度值的同時,也將鄰居節(jié)點(diǎn)的度值加入考慮的范疇,從而極大地提升了網(wǎng)絡(luò)中節(jié)點(diǎn)排序的準(zhǔn)確性.

1 經(jīng)典的節(jié)點(diǎn)重要性排序算法

評估網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的算法有很多,大多都是根據(jù)節(jié)點(diǎn)或節(jié)點(diǎn)之間的連邊來進(jìn)行考慮的.下面首先介紹度排序算法與接近度排序算法.

度排序,簡而言之就是根據(jù)網(wǎng)絡(luò)中每個節(jié)點(diǎn)度值的大小進(jìn)行排序的算法[6].度大的節(jié)點(diǎn)則在該網(wǎng)絡(luò)中的地位比較重要,度越小的節(jié)點(diǎn)越不重要.比如在鐵路網(wǎng)中,車站代表節(jié)點(diǎn),兩城市之間若有開通列車,則存在連邊,那么某節(jié)點(diǎn)的連邊越多,說明該城市的列車開往的城市越多,該點(diǎn)的地位也越重要.若網(wǎng)絡(luò)為無權(quán)的完全圖,那么網(wǎng)絡(luò)中存在條邊,計算網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的時間復(fù)雜度為O（N2）,利用快速排序算法對節(jié)點(diǎn)度排序,時間復(fù)雜度為O（NlogN）,因此度排序算法時間復(fù)雜度為O（N2+NlogN）,式中N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目.該方法能以較低的算法復(fù)雜度從一定程度上計算出復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性,但是此方法也存在明顯的缺點(diǎn).如圖1所示網(wǎng)絡(luò)中,節(jié)點(diǎn)5的度數(shù)雖小于節(jié)點(diǎn)4和節(jié)點(diǎn)6,但它是連接兩個子網(wǎng)絡(luò)的關(guān)鍵,因此不能簡單地僅用節(jié)點(diǎn)的度來衡量節(jié)點(diǎn)的重要性.

圖1 網(wǎng)絡(luò)拓?fù)銯ig.1 Network topology

接近度CLi的計算公式為其中d（Vi,Vj）表示以節(jié)點(diǎn)Vi為起點(diǎn),節(jié)點(diǎn)Vj為終點(diǎn)的最短路徑長度.那么接近度越大的節(jié)點(diǎn)在網(wǎng)絡(luò)中所處位置也越接近中心,接近度越小的節(jié)點(diǎn)越靠近網(wǎng)絡(luò)的邊緣[7].若計算兩節(jié)點(diǎn)之間的最短路徑長度采用Dijstra算法,時間復(fù)雜度為O（N2）,同樣利用快速排序算法對各節(jié)點(diǎn)的接近度值進(jìn)行排序,那么接近度算法的時間復(fù)雜度為O（N3+NlogN）.接近度排序算法不僅考慮了節(jié)點(diǎn)的度值,還考慮了節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置,以此算法對節(jié)點(diǎn)的重要性進(jìn)行判斷比較準(zhǔn)確.

2 度排序的改進(jìn)算法

2.1 網(wǎng)絡(luò)模型

本文研究的復(fù)雜網(wǎng)絡(luò)均為無向無權(quán)網(wǎng)絡(luò).假設(shè)網(wǎng)絡(luò)G有N個節(jié)點(diǎn),M條邊,則V={V1,V2,V3,…,Vn},代表頂點(diǎn)的集合,E={E1,E2,E3,…,Em}代表網(wǎng)絡(luò)中邊的集合,網(wǎng)絡(luò)G中各節(jié)點(diǎn)之間的關(guān)系用鄰接矩陣A=[aij]來表示,其中

定義1（度）頂點(diǎn)Vi的度是和Vi相關(guān)聯(lián)的邊的數(shù)目,記為TD（Vi）.

定義2（鄰度）對于網(wǎng)絡(luò)G中的一個節(jié)點(diǎn)Vi,G中所有與Vi相鄰的節(jié)點(diǎn)的度的總和稱為節(jié)點(diǎn)Vi的鄰度,記為Ni.

定義3（合度）對于網(wǎng)絡(luò)G中的一個節(jié)點(diǎn)Vi,其鄰度與節(jié)點(diǎn)自身度值之和稱為節(jié)點(diǎn)Vi的合度,記為Bi,即2.2 合度排序算法

合度排序算法的基本思路是將網(wǎng)絡(luò)中節(jié)點(diǎn)自身的度值與其所有鄰居節(jié)點(diǎn)度值之和相加,進(jìn)而利用所得數(shù)據(jù)作為分析節(jié)點(diǎn)重要性的評估依據(jù).

根據(jù)上面的定義,可以給出復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的合度排序算法：

若網(wǎng)絡(luò)為無權(quán)的完全圖,則步驟（1）和步驟（2）的時間復(fù)雜度均為O（N2）,步驟（3）和步驟（4）的時間復(fù)雜度均為O（N）,步驟（5）的時間復(fù)雜度為O（NlogN）,那么合度排序算法的時間復(fù)雜度為O（N2+ NlogN）.

通過上述對合度排序算法的性能分析,其時間復(fù)雜度與度排序算法相同,優(yōu)于接近度排序算法.另外,合度排序算法與度排序算法相比,不僅考慮了節(jié)點(diǎn)的度,還考慮了節(jié)點(diǎn)之間的聯(lián)系,因此與傳統(tǒng)的度排序算法相比具有準(zhǔn)確性上的優(yōu)勢.

3 算例

以一個簡單的復(fù)雜網(wǎng)絡(luò)G（見圖2）為例,利用合度排序算法對網(wǎng)絡(luò)G中節(jié)點(diǎn)的重要性進(jìn)行排序.首先敘述合度排序算法的執(zhí)行過程,并通過結(jié)果驗(yàn)證該算法的有效性及準(zhǔn)確性.

圖2 復(fù)雜網(wǎng)絡(luò)GFig.2 Complex network G

以節(jié)點(diǎn)2為例,首先計算節(jié)點(diǎn)2的鄰度.節(jié)點(diǎn)2的鄰居節(jié)點(diǎn)7、9、10、11、12的度值分別為2、1、1、1、2,節(jié)點(diǎn)2的鄰度值就是將節(jié)點(diǎn)7、9、10、11、12的度值相加,為7.那么,節(jié)點(diǎn)2的合度值就是將節(jié)點(diǎn)2自身的度值加上其鄰度值,即5+7=12.

根據(jù)合度排序算法計算出的網(wǎng)絡(luò)G中各節(jié)點(diǎn)的度值、鄰度值以及計算獲得的合度值如表1所示.

表1 節(jié)點(diǎn)參數(shù)Tab.1 Node parameter

由表1可知,根據(jù)合度值對該網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行排序,結(jié)果為：2,7,12,1,3,4,5,6,8,9,10,11,13,14,15,16.為了說明此算法的有效性,利用度排序算法和比較準(zhǔn)確且常用的接近度算法作比較,結(jié)果如表2所示.

表2 與經(jīng)典算法的比較結(jié)果Tab.2 Comparison with classical algorithms

由表2可知,度排序只考慮了節(jié)點(diǎn)自身度值,未考慮節(jié)點(diǎn)與節(jié)點(diǎn)之間的聯(lián)系,因此將節(jié)點(diǎn)度值一樣的節(jié)點(diǎn)1,2,3排在了首位,而將分別連接兩個子網(wǎng)絡(luò)的節(jié)點(diǎn)7和節(jié)點(diǎn)12排在了后面.本文提出的合度排序算法與經(jīng)典的接近度算法對網(wǎng)絡(luò)G中節(jié)點(diǎn)的重要性排序結(jié)果完全一樣,將位于網(wǎng)絡(luò)中心的節(jié)點(diǎn)2排在了首位,有連接作用的節(jié)點(diǎn)7和節(jié)點(diǎn)12緊隨其后,其次是位于邊緣兩個子網(wǎng)絡(luò)的節(jié)點(diǎn)1和節(jié)點(diǎn)3,對于11個葉子節(jié)點(diǎn),3種排序算法都是一樣的.這個結(jié)果證實(shí)了合度排序算法的有效性.

4 小結(jié)

節(jié)點(diǎn)的重要性排序是復(fù)雜網(wǎng)絡(luò)的研究重點(diǎn),對于復(fù)雜網(wǎng)絡(luò)的研究有十分重要的意義.本文在總結(jié)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序算法的基礎(chǔ)上,對度排序算法進(jìn)行改進(jìn),將節(jié)點(diǎn)度值擴(kuò)大化,兼顧了節(jié)點(diǎn)與節(jié)點(diǎn)之間的聯(lián)系,使排序結(jié)果更準(zhǔn)確有效.同時,較之經(jīng)典的接近度排序算法具有更小的時間復(fù)雜度等優(yōu)點(diǎn),而且更直觀地評估了節(jié)點(diǎn)的重要性.下一步將利用合度排序算法針對復(fù)雜網(wǎng)絡(luò)的抗毀性評估及防護(hù)策略展開研究[8].

[1]汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社,2006.

[2]Wasserman S,Faust K.Social network analysis：methods and applications[M].Cambridge：Cambridge University Press,1994.

[3]Milgram S.The small world problem[J].Psychology Today,1967（5）：60-67.

[4]Zanette D H.Dynamics of rumor propagation on small-world networks[J].Phys Rev,E,2002,65：041908.

[5]高峰,黨亞茹.世界航空客運(yùn)網(wǎng)絡(luò)的節(jié)點(diǎn)度分布特征[J].科學(xué)學(xué)與科學(xué)技術(shù)管理,2009（7）：75-79.

[6]司曉靜.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的研究[D].西安：西安電子科技大學(xué),2012.

[7]陳靜,孫林夫.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評估[J].西南交通大學(xué)學(xué)報,2009,44（3）：426-429.

[8]Albert R,Jeong H,Barabási A L.Error and attack tolerance of complex networks[J].Nature,2000,406：378-382.

（責(zé)任編輯：盧奇）

A method about node importance evaluation based on degree-rank

Zhang Mei1,2,Xie Jianjun1,2,Feng Kezhan1,2
（1.College of Mathematics and Information Science,Hebei Normal University,Shijiazhuang 050024, China；2.Key Laboratory of Computational Mathematics and Applications,Shijiazhuang 050024,China）

To effectively evaluate the importance of nodes in complex networks,a both degree sorting algorithm based on the classical degree sorting algorithm was proposed in this paper.Both degree sorting algorithm is proposed the concept of neighbor degree and both degree on the basis of the concept of node degree,through the calculation of both degree of each node to evaluate the importance of the nodes in the network,the higher the value of both degree, the more important position in the network.And by using the classical degree sorting and closeness sorting algorithms, and the new proposed both degree sorting algorithm on the same network topology node sorting,proving the validity of the proposed sorting algorithm.

complex network；node importance；degree；sorting

O157.5

A

：1008-7516（2015）02-0061-05

10.3969/j.issn.1008-7516.2015.02.014

2015-01-14

河北省自然科學(xué)基金項(xiàng)目（A2014205027）；河北師范大學(xué)應(yīng)用開發(fā)基金項(xiàng)目（L2015K01）

張玫（1989―）,女,河北磁縣人,碩士研究生.主要從事復(fù)雜網(wǎng)絡(luò)、信息安全研究.

解建軍（1971―）,男,山西運(yùn)城人,副教授,碩士生導(dǎo)師.主要從事信息安全研究.