一種基于最短路徑介數(shù)的重要節(jié)點發(fā)現(xiàn)算法

張珍，張振宇，宋蔓蔓

新疆大學(xué)信息科學(xué)與工程學(xué)院計算機(jī)科學(xué)系，烏魯木齊 830000

一種基于最短路徑介數(shù)的重要節(jié)點發(fā)現(xiàn)算法

張珍，張振宇，宋蔓蔓

新疆大學(xué)信息科學(xué)與工程學(xué)院計算機(jī)科學(xué)系，烏魯木齊 830000

現(xiàn)實世界中存在的大量復(fù)雜系統(tǒng)都可以通過各種網(wǎng)絡(luò)加以描述，例如，因特網(wǎng)、電力網(wǎng)絡(luò)、病毒網(wǎng)絡(luò)、罪犯關(guān)系網(wǎng)絡(luò)、謠言傳播網(wǎng)絡(luò)等。在復(fù)雜網(wǎng)絡(luò)的各種基礎(chǔ)研究工作中，對網(wǎng)絡(luò)中節(jié)點的重要性進(jìn)行評估，發(fā)掘網(wǎng)絡(luò)中的重要節(jié)點，具有重要的實用價值。對于無標(biāo)度網(wǎng)絡(luò)，5%的核心節(jié)點被攻擊，網(wǎng)絡(luò)就基本癱瘓[1]。在電力網(wǎng)絡(luò)中，重要的發(fā)電單元若出現(xiàn)故障，將會相繼引起大范圍的停電[2]。通過節(jié)點的重要度評估，找出網(wǎng)絡(luò)中重要的“核心節(jié)點”，一方面可以重點保護(hù)這些“核心節(jié)點”來提高整個網(wǎng)絡(luò)的可靠性，另外一方面也可以攻擊這些“薄弱環(huán)節(jié)”達(dá)到摧毀整個網(wǎng)絡(luò)的目的[3]。

1 相關(guān)工作

節(jié)點的重要性評估方法有很多，目前主要分為社會網(wǎng)絡(luò)分析、系統(tǒng)科學(xué)分析、信息搜索領(lǐng)域分析三大類。社會網(wǎng)絡(luò)分析方法的一個重要基本思想是，網(wǎng)絡(luò)中不同節(jié)點的重要性差異是通過分析網(wǎng)絡(luò)中某種有用的信息得到的，例如節(jié)點的度、介數(shù)、中心接近度、特征向量指標(biāo)等。其中，利用節(jié)點度作為節(jié)點重要度的衡量標(biāo)準(zhǔn)[4]是最簡單的方法，該方法認(rèn)為與節(jié)點相連的邊越多則該節(jié)點越重要，但是這種方法容易忽略一些“核心節(jié)點”，例如“橋接節(jié)點”，作為網(wǎng)絡(luò)中信息流量很大的節(jié)點，它的重要性不能被忽視。文獻(xiàn)[5]提出通過節(jié)點介數(shù)（betweenness centrality）發(fā)現(xiàn)網(wǎng)絡(luò)中的重要節(jié)點，但其計算復(fù)雜度非常高，為O(n3)。文獻(xiàn)[6]定義節(jié)點的中心接近度反映了節(jié)點在網(wǎng)絡(luò)中居于中心的程度。節(jié)點的中心接近度越大，表明節(jié)點越居于網(wǎng)絡(luò)的中心，它在網(wǎng)絡(luò)中就越重要。然而，直接使用中心接近度衡量節(jié)點的重要性對網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)依賴性比較大。Poulin等人[7]對求解特征向量的映射迭代方法進(jìn)行了改進(jìn)，提出了一種累計提名指標(biāo)，但是這類方法是在保證網(wǎng)絡(luò)整體性的前提下進(jìn)行的，具有一定的局限性。系統(tǒng)科學(xué)的研究方法是利用網(wǎng)絡(luò)的連通性來反映系統(tǒng)某種功能的完整性，通過度量節(jié)點的刪除或融合對網(wǎng)絡(luò)連通的破壞程度來反應(yīng)網(wǎng)絡(luò)節(jié)點的重要性。例如，Chen等人[8]提出了一種基于最小生成樹的指標(biāo)，認(rèn)為最重要的節(jié)點是自身及相關(guān)鏈路去掉后使得圖的生成樹的數(shù)目最小的節(jié)點。該方法的缺點是如果多個節(jié)點的刪除都使得網(wǎng)絡(luò)不連通，那么這些節(jié)點的重要性將是一致的，例如“末梢節(jié)點”所依附的節(jié)點，因而使得評估結(jié)果不精確。文獻(xiàn)[9]將節(jié)點的平均路徑和節(jié)點的個數(shù)乘積的倒數(shù)定義為網(wǎng)絡(luò)凝聚度，用每個節(jié)點融合后的網(wǎng)絡(luò)凝聚度來評價節(jié)點重要性，但文中沒有描述如何計算節(jié)點的平均路徑。信息搜索領(lǐng)域的分析方法，主要適用于互聯(lián)網(wǎng)搜索領(lǐng)域，其中最具有代表性的算法是PageRank算法[10]和HIΤS算法[11]。此后，互聯(lián)網(wǎng)的搜索領(lǐng)域越來越受到人們的關(guān)注，不斷有新的算法和變種提出。例如，文獻(xiàn)[12]提出的改進(jìn)方法，即提出了一種基于物理學(xué)場論模型的節(jié)點排序算法，用節(jié)點間的相互作用力來衡量節(jié)點之間的轉(zhuǎn)移概率，指向高質(zhì)量網(wǎng)頁的網(wǎng)頁節(jié)點應(yīng)該被賦予更大的轉(zhuǎn)移概率，但由于該方法在考慮節(jié)點的物質(zhì)場作用力時主要從兩個節(jié)點的距離和節(jié)點自身的度來衡量，從而忽略了節(jié)點在全網(wǎng)內(nèi)的位置和作用。

圖1 由網(wǎng)絡(luò)拓?fù)渫ㄟ^寬度優(yōu)先遍歷構(gòu)造最短路徑拓?fù)浣Y(jié)構(gòu)

重要節(jié)點，即網(wǎng)絡(luò)中的“樞紐”節(jié)點，其反應(yīng)的是節(jié)點在網(wǎng)絡(luò)中的地位高低或者說是在網(wǎng)絡(luò)中的影響力大小。本文首先通過最短路徑樹得到網(wǎng)絡(luò)中邊介數(shù)較大的邊，由于這些邊兩端的節(jié)點處于許多其他兩節(jié)點之間的路徑上，因此這些節(jié)點具有控制其他兩個節(jié)點之間通信的能力，一個節(jié)點在網(wǎng)絡(luò)中占據(jù)這樣的位置越多，就代表有越多的節(jié)點需要通過它才能與其他節(jié)點發(fā)生聯(lián)系，那么該節(jié)點在網(wǎng)絡(luò)中就擁有較大的“權(quán)利”，因而最短路徑樹可以幫助定性地找出在網(wǎng)絡(luò)中居于重要地位的節(jié)點。但此時找到的重要節(jié)點的重要性相同，在現(xiàn)實網(wǎng)絡(luò)中，由于自然經(jīng)濟(jì)、社會條件的差異，重要節(jié)點之間仍然會表現(xiàn)出重要性的差異。本文使用中心接近度來定量地分析這些重要節(jié)點的重要性，中心接近度刻畫的是節(jié)點的中心指數(shù)，它衡量了網(wǎng)絡(luò)中節(jié)點與其他節(jié)點聯(lián)系的多少，如果一個節(jié)點通過比較短的路徑與許多其他節(jié)點相連，那么該節(jié)點就具有較高的中心接近度?？偨Y(jié)來說，本文的方法首先通過邊介數(shù)來衡量網(wǎng)絡(luò)中節(jié)點“控制”其他節(jié)點的能力，然后對找到的重要節(jié)點通過中心接近度來衡量這些節(jié)點不受其他節(jié)點“控制”的能力，最后得出網(wǎng)絡(luò)中重要節(jié)點的排序。

本文首先介紹了基于最短路徑介數(shù)發(fā)現(xiàn)重要節(jié)點的算法設(shè)計，然后描述了使用中心接近度評估節(jié)點的重要性，最后通過案例分析驗證了該方法的有效性。

2 算法設(shè)計

2.1 算法描述

（1）基于最短路徑介數(shù)發(fā)現(xiàn)重要節(jié)點

文獻(xiàn)[13]通過最短路徑介數(shù)發(fā)現(xiàn)網(wǎng)絡(luò)中“流量”最大的邊，該方法的基本思想是以網(wǎng)絡(luò)中每個節(jié)點作為根節(jié)點通過寬度優(yōu)先遍歷構(gòu)造其與其他節(jié)點的最短路徑拓?fù)浣Y(jié)構(gòu)并計算邊上的權(quán)值，權(quán)值表示網(wǎng)絡(luò)中經(jīng)過該邊可達(dá)的某個節(jié)點的最短路徑占可到達(dá)該節(jié)點的所有最短路徑總數(shù)的比例之和。原始網(wǎng)絡(luò)中每條邊的邊介數(shù)等于構(gòu)造的所有最短路徑拓?fù)浣Y(jié)構(gòu)上該邊的權(quán)值之和，如圖1所示。

通過計算，圖1（a）中邊介數(shù)最大的邊是BE，應(yīng)當(dāng)刪除BE邊。刪除BE后原始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化，繼續(xù)構(gòu)造最短路徑拓?fù)浣Y(jié)構(gòu)找出第二條可以刪除的邊介數(shù)最大的邊。文獻(xiàn)[10]提出算法終止條件，即最優(yōu)的聚類劃分結(jié)果是當(dāng)模塊Q函數(shù)的Q值達(dá)到最大時的劃分結(jié)果，通過計算得出第二次刪除邊BH后Q值達(dá)到最大，算法終止。因此，劃分過程中刪除的邊是BE、BH。

根據(jù)圖1（a）中的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，計算了所有節(jié)點的點介數(shù)，如表1所示。從表中可以看出，節(jié)點B、E、H的點介數(shù)較之其他節(jié)點較大，說明節(jié)點B、E、H在網(wǎng)絡(luò)中的流量較大，即在網(wǎng)絡(luò)中的地位越重要。因此，通過最短路徑介數(shù)的方法找到邊介數(shù)最大的同時也可以發(fā)現(xiàn)網(wǎng)絡(luò)中比較重要的節(jié)點，這樣大大降低了直接計算節(jié)點介數(shù)的復(fù)雜度。此時發(fā)現(xiàn)的節(jié)點B、E、H的重要性相同。

表1 節(jié)點介數(shù)的計算

（2）用中心接近度評估重要節(jié)點的重要性

2.2 算法流程

對于已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖G，可以直接輸入鄰接矩陣A完成初始化。令m表示圖的邊數(shù)，n表示圖的節(jié)點數(shù)，矩陣B存儲節(jié)點對之間的邊介數(shù)，鏈表Q和K分別存儲模塊化Q值和重要節(jié)點，其中Q0=0，鏈表C存儲重要節(jié)點的中心接近度。本文算法可以簡單描述如下：

輸入：G的鄰接矩陣A

輸出：重要節(jié)點排序結(jié)果

步驟1發(fā)現(xiàn)網(wǎng)絡(luò)中的重要節(jié)點

以當(dāng)前節(jié)點作為根節(jié)點通過寬度優(yōu)先遍歷構(gòu)造最短路徑拓?fù)浣Y(jié)構(gòu)；

步驟2計算重要節(jié)點的重要性

2.3 計算復(fù)雜度分析

從上述算法流程看，整個算法的計算復(fù)雜度取決于步驟1通過最短路徑拓?fù)浣Y(jié)構(gòu)求出網(wǎng)絡(luò)中介數(shù)最大的邊及步驟2計算中心接近度，對于步驟1文獻(xiàn)[9]中給出的最壞情況下的計算復(fù)雜度為O(m2n)，對于步驟2采用Dijstra算法計算復(fù)雜度為O(n2)。因此，整個算法的計算復(fù)雜度為O(m2n+kn2)，考慮到現(xiàn)實網(wǎng)絡(luò)中，k遠(yuǎn)遠(yuǎn)小于n，一般情況下，算法的計算復(fù)雜度〈〈O(m2n+n3)。

3 實驗

3.1 實驗條件及方法

實驗采用真核細(xì)胞新陳代謝網(wǎng)絡(luò)[14]中的一個網(wǎng)絡(luò)模塊，如圖2所示。該模塊有30個節(jié)點，34條邊，其中節(jié)點代表蛋白質(zhì)，若兩個蛋白質(zhì)參與了同一活動，則它們之間存在一條邊。對該模塊分別采用文獻(xiàn)[4]、文獻(xiàn)[5]、文獻(xiàn)[10]、文獻(xiàn)[12]以及本文方法求出全網(wǎng)中最重要的節(jié)點，實驗結(jié)果見表2。

圖2 真核細(xì)胞新陳代謝網(wǎng)絡(luò)中的一個模塊

表2 使用四種方法計算重要節(jié)點的排序

3.2 實驗結(jié)果及分析

由表2可以看出，本文算法與文獻(xiàn)[4]、文獻(xiàn)[5]的方法得出的結(jié)果不相同，原因在于本文方法不僅考慮了節(jié)點的介數(shù)，同時又考慮到了節(jié)點在網(wǎng)絡(luò)中的位置。而本文算法與文獻(xiàn)[12]的算法計算出的排名第三的節(jié)點是22，文獻(xiàn)[10]Pagerank算法計算出排名第三的節(jié)點是26，區(qū)別在于雖然節(jié)點22的度沒有節(jié)點26的度大，但文獻(xiàn)[12]認(rèn)為節(jié)點22跳向9的概率更大，本文方法認(rèn)為節(jié)點22比節(jié)點26更趨向于網(wǎng)絡(luò)中心。綜上所述，本文的算法具有很好的參考價值。

4 總結(jié)

本文提出了一種基于最短路徑介數(shù)及節(jié)點中心接近度的網(wǎng)絡(luò)重要節(jié)點及其重要性的發(fā)現(xiàn)算法。該方法綜合考慮了節(jié)點的網(wǎng)絡(luò)流量和節(jié)點位置，可以準(zhǔn)確發(fā)現(xiàn)全網(wǎng)內(nèi)的重要節(jié)點及其重要性。由于無需對網(wǎng)絡(luò)中的全部節(jié)點的重要性進(jìn)行評估，大大縮減了計算時間，在保證精確性的同時克服了直接計算節(jié)點介數(shù)的復(fù)雜性，提高了效率。

[1]Wang Xun，Ling Yun，F(xiàn)ei Yulian.Personalization recommendation system based on web log&cache data mining[J]. Journal of the China Society for Scientific and Τechnical Information，2005，24（3）：324-328.

[2]赫南，李德毅，淦文燕，等.復(fù)雜網(wǎng)絡(luò)中重要性節(jié)點發(fā)掘綜述[J].計算機(jī)科學(xué)，2007（12）.

[3]譚躍進(jìn)，吳俊，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點重要度評估的節(jié)點收縮方法[J].系統(tǒng)工程理論與實踐，2006，11（11）：79-83.

[4]Callaway D S，Newman M E J，Strogatz S H.Network robustness and fragility：percolation on Randon graphs[J].Physical Review Letters，2000，85（25）：5468-5471.

[5]Freeman L C.A set of measures of centrality based upon betweenness[J].Sociometry，1977，40（1）：35-41.

[6]Sabidussi G.Τhe centrality index of a graph[J].Psychometrika，1966，31：581-603.

[7]Poulin R，Boily M C，Masse B R.Dynamical systems to define centrality in social networks[J].Social Networks，2000，22：187-220.

[8]Chen Y，Hu A Q，Hu J，et al.A method for finding the mostvitalnodeincommunicationnetworks[J].High Τechnology Letters，2004，1：573-575.

[9]Wu J，Τan Y J.Finding the most vital node by node contraction in communication networks[C]//2005 IEEE International Conference on Communications，Circuits and Systems Proceeding，Changsha，2005：1283-1286.

[10]Horowitz D，Kamvar S D.Τhe anatomy of a large-scale social search engine[C]//Τhe International World Wide Web Conference Committee，2010：26-30.

[11]Agichtein E，Brill E，Dumais S.Improving web search ranking by incorporating user behavior information[C]//Proc of the 29th Annual International ACM SIGIR Conf on Research and Development in Information Retrieval，2006.

[12]何建軍，李仁發(fā).改進(jìn)的隨機(jī)游走模型節(jié)點排序方法[J].計算機(jī)工程與應(yīng)用，2011，47（12）：87-89.

[13]Newman M E J，Girvan M.Finding and evaluating community structure in networks[J].Physical Review E，2004，69.

[14]Guimera R，Sales P M，Lan A.Classes of complex networks defined by role-to-role connectivity profiles[J].Nature Physics，2007，3：63-69.

ZHANG Zhen,ZHANG Zhenyu,SONG Manman

Department of Computer Science,School of Information Science and Engineering,Xinjiang University,Urumqi 830000,China

Finding important nodes in network is one of the most important topics of studying the properties of network,which is widely used in complex network,system science,analysis of social network and searching in Internet.In order to improve efficiency and effectiveness of finding important node,a new algorithm based on shortest-path betweenness and closeness centrality is presented.It ensures important nodes in the whole network by using the shortest-path betweenness,analyses the importance of important nodes by using the closeness centrality.Compared with the current approach,the results obtained from performance analysis show the algorithm is a feasible and efficient approach for finding important nodes in large-scale P2P networks.

important nodes;shortest-path betweenness;closeness centrality;complex networks;network topology

網(wǎng)絡(luò)中重要節(jié)點的發(fā)現(xiàn)是研究網(wǎng)絡(luò)特性的重要方面之一，在復(fù)雜網(wǎng)絡(luò)、系統(tǒng)科學(xué)、社會網(wǎng)分析和互聯(lián)網(wǎng)搜索等領(lǐng)域中具有廣泛的應(yīng)用價值。為提高全網(wǎng)范圍內(nèi)重要節(jié)點發(fā)現(xiàn)的效率和有效性，提出了一種基于最短路徑介數(shù)及節(jié)點中心接近度的重要節(jié)點發(fā)現(xiàn)算法，通過最短路徑介數(shù)的方法確定全網(wǎng)內(nèi)的重要節(jié)點，利用中心接近度分析重要節(jié)點的重要性。測試結(jié)果表明，與同類的系統(tǒng)比較起來，該方法具有比較好的性能。

重要節(jié)點；最短路徑介數(shù)；中心接近度；復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)拓?fù)?/p>

A

ΤP393

10.3778/j.issn.1002-8331.1201-0307

ZHANG Zhen,ZHANG Zhenyu,SONG Manman.Important node searching algorithm based on shortest-path betweeness. Computer Engineering and Applications,2013,49（21）：98-100.

張珍（1988—），女，碩士研究生，主要研究方向為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與信息安全；張振宇（1964—），男，副教授，碩士導(dǎo)師，主要研究方向為計算機(jī)應(yīng)用及信息處理、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與信息安全；宋蔓蔓（1987—），女，碩士研究生，主要研究方向為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與信息安全。E-mail：zhangzhen_2013@126.com

2012-01-16

2012-04-10

1002-8331（2013）21-0098-03