一種基于局部特征的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法

王 建 偉， 榮 莉 莉， 郭 天 柱

（大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116024）

0 引 言

現(xiàn)實(shí)生活中的許多系統(tǒng)都可以通過網(wǎng)絡(luò)的形式加以描述，如人際關(guān)系網(wǎng)絡(luò)[1]、航空網(wǎng)絡(luò)[2]、電力網(wǎng)絡(luò)[3]、互聯(lián)網(wǎng)絡(luò)[4]、新陳代謝網(wǎng)絡(luò)[5]、科研合作網(wǎng)絡(luò)[6]等.近年來隨著大規(guī)模網(wǎng)絡(luò)實(shí)證研究的開展，對(duì)于哪些節(jié)點(diǎn)在網(wǎng)絡(luò)功能運(yùn)轉(zhuǎn)中扮演重要角色的研究引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，并出現(xiàn)了許多結(jié)合不同實(shí)際背景的節(jié)點(diǎn)重要性評(píng)估方法[7～9].這些方法都基于節(jié)點(diǎn)之間的差異性，從某一角度探討網(wǎng)絡(luò)節(jié)點(diǎn)的重要性問題，如人際關(guān)系網(wǎng)絡(luò)中節(jié)點(diǎn)本身的地位；通訊網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)信息傳播的控制能力；交通網(wǎng)絡(luò)中節(jié)點(diǎn)處理信息的流量等.大體可以將這些方法分為三大類：節(jié)點(diǎn)關(guān)聯(lián)性問題、最短路徑問題和網(wǎng)絡(luò)流問題，具體包括度、介數(shù)[10、11]、凝聚性[9]、特征向量[8]、子圖[12]、網(wǎng)絡(luò)流[13]、隨機(jī)行走[14]等.其中基于度的重要性評(píng)估方法最為簡(jiǎn)單，它只強(qiáng)調(diào)節(jié)點(diǎn)與鄰接節(jié)點(diǎn)連邊的數(shù)量；介數(shù)刻畫了節(jié)點(diǎn)或邊對(duì)網(wǎng)絡(luò)中信息或流的控制能力；凝聚性側(cè)重于分析節(jié)點(diǎn)在網(wǎng)絡(luò)中的幾何位置；特征向量充分考慮與目標(biāo)節(jié)點(diǎn)建立連接節(jié)點(diǎn)的重要性，并通過鄰接節(jié)點(diǎn)的重要性來確定目標(biāo)節(jié)點(diǎn)的地位；子圖反映了節(jié)點(diǎn)在網(wǎng)絡(luò)局部結(jié)構(gòu)的貢獻(xiàn)大?。痪W(wǎng)絡(luò)流和隨機(jī)行走都利用模擬現(xiàn)實(shí)的思想，分析網(wǎng)絡(luò)節(jié)點(diǎn)在實(shí)際應(yīng)用中的作用.

此外，網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法研究還有譚躍進(jìn)等[15]提出的節(jié)點(diǎn)收縮方法，李翔鵬等[16]和許進(jìn)等[17]提出的核與核度理論.前者與前面介紹的方法一樣，從節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的貢獻(xiàn)出發(fā)評(píng)估其重要性；后者則采用了節(jié)點(diǎn)刪除法的思想，用節(jié)點(diǎn)刪除后對(duì)網(wǎng)絡(luò)連通性破壞程度定義其重要性.

上述節(jié)點(diǎn)重要性評(píng)估方法的差異主要體現(xiàn)在對(duì)節(jié)點(diǎn)重要性的定義上，無論是基于節(jié)點(diǎn)顯著性等價(jià)于重要性，還是破壞性等價(jià)于重要性，都需要給重要性一個(gè)合適的定義和度量方法.在現(xiàn)有的評(píng)估方法中，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)重要性的度量都是側(cè)重于全局和局域兩個(gè)不同的角度.而基于全局的角度對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的度量需要遍歷整個(gè)網(wǎng)絡(luò)，例如，節(jié)點(diǎn)介數(shù)的計(jì)算都要遍歷整個(gè)網(wǎng)絡(luò)，這在小規(guī)模的網(wǎng)絡(luò)中具有一定的應(yīng)用價(jià)值，但現(xiàn)實(shí)生活中的很多網(wǎng)絡(luò)，網(wǎng)絡(luò)規(guī)模非常龐大，結(jié)構(gòu)非常復(fù)雜，想從全局的角度度量節(jié)點(diǎn)的重要性幾乎是不可能的；網(wǎng)絡(luò)流的方法既耗資源，又不太現(xiàn)實(shí)；而一些基于局域角度的度量方法，譬如：度方法不能很好地描述出節(jié)點(diǎn)之間的差異性，節(jié)點(diǎn)收縮方法又不能很好地體現(xiàn)研究節(jié)點(diǎn)本身的度的情況.鑒于此，基于節(jié)點(diǎn)度和鄰居節(jié)點(diǎn)度，本文提出一種簡(jiǎn)單而有效的網(wǎng)絡(luò)節(jié)點(diǎn)重要性的度量方法，即節(jié)點(diǎn)的度，節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的度越大，節(jié)點(diǎn)就越重要.這樣一方面克服了全局方面應(yīng)用的局限，又在一定程度上使得網(wǎng)絡(luò)中心節(jié)點(diǎn)的判別方法得到簡(jiǎn)化，可以使得在效率、有效性等方面更優(yōu)于已有的方法.

1 符號(hào)與方法的描述

1.1 網(wǎng)絡(luò)的表示

網(wǎng)絡(luò)可以用二元組（V，E）表示，其中V＝｛v1，v2，…，v n｝，代 表 節(jié) 點(diǎn) 集 合，E＝ ｛e1，e2，…，em｝，代表邊的集合，n和m分別表示網(wǎng)絡(luò)包含的節(jié)點(diǎn)數(shù)和邊數(shù).網(wǎng)絡(luò)的鄰接矩陣A為

其中aij∈ ｛0，1｝，i，j＝1，2，…，n，表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間是否有邊相連，如果aij＝1，則表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間有邊，否則表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間沒有邊.

1.2 方法描述

網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性與節(jié)點(diǎn)所連邊的重要性是密切相關(guān)的.

公理1 連接節(jié)點(diǎn)的邊越重要，節(jié)點(diǎn)越重要.

基于公理1，將從網(wǎng)絡(luò)邊的角度來探討節(jié)點(diǎn)的重要性.設(shè)w ij表示邊ij的權(quán)重，同時(shí)節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)表示為Гi.

定義1 邊ij的權(quán)重定義為

其中ki表示與節(jié)點(diǎn)i連接的邊的數(shù)目，即節(jié)點(diǎn)i的度.令

其中e＝（111 … 1）T是n維列向量；b＝（b1b2…bn）T，bi表示為節(jié)點(diǎn)i的度.所以，邊ij的權(quán)重可以表示為

定義2 帶有邊權(quán)的節(jié)點(diǎn)i的權(quán)重定義為w i表示節(jié)點(diǎn)i所連邊的權(quán)值之和.

由定義2可以看出，節(jié)點(diǎn)i的重要度取決于節(jié)點(diǎn)i所連邊的權(quán)值的大小，而邊的權(quán)值有兩個(gè)影響因素：一是節(jié)點(diǎn)i的度k i，另一個(gè)是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的度.相同條件下，如果節(jié)點(diǎn)i的度k i越大，同時(shí)所對(duì)應(yīng)的鄰居節(jié)點(diǎn)的度越大，該節(jié)點(diǎn)越重要.

定義3 為消除網(wǎng)絡(luò)規(guī)模對(duì)節(jié)點(diǎn)權(quán)重的影響，定義歸一化的節(jié)點(diǎn)i的重要性為

1.3 方法優(yōu)勢(shì)分析

圖1描述了網(wǎng)絡(luò)節(jié)點(diǎn)重要性與節(jié)點(diǎn)的度及節(jié)點(diǎn)鄰居節(jié)點(diǎn)連接狀況之間的密切關(guān)系.

圖1 局部特征方法的優(yōu)勢(shì)Fig.1 Advantages of local characteristics method

在圖1中，很明顯，節(jié)點(diǎn)i和j的局部特征影響了兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)上的重要性.在網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)上，雖然兩個(gè)不同節(jié)點(diǎn)具有相同的度，然而由于鄰居節(jié)點(diǎn)的影響，節(jié)點(diǎn)i的重要性明顯高于節(jié)點(diǎn)j的重要性.可以看出，節(jié)點(diǎn)本身的度及其鄰居節(jié)點(diǎn)特征都是不能夠忽略的指標(biāo).由于考慮到了網(wǎng)絡(luò)節(jié)點(diǎn)的局部特征，本方法對(duì)于度分布較為異質(zhì)的網(wǎng)絡(luò)，如具有無標(biāo)度特性的網(wǎng)絡(luò)：Internet、人際關(guān)系網(wǎng)絡(luò)、科研合作網(wǎng)絡(luò)、新陳代謝網(wǎng)絡(luò)、引文網(wǎng)絡(luò)以及電子郵件網(wǎng)絡(luò)等，都能夠比較細(xì)致地凸現(xiàn)節(jié)點(diǎn)之間的差異性，并比較客觀地反映節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)整體的影響效應(yīng).

2 實(shí)例分析

選取艾滋病患者性關(guān)系網(wǎng)絡(luò)作為研究對(duì)象，如圖2所示.網(wǎng)絡(luò)中節(jié)點(diǎn)表示帶有艾滋病的患者，邊表示兩個(gè)艾滋病患者之間存在性關(guān)系.

圖2 艾滋病患者性關(guān)系網(wǎng)絡(luò)[18]Fig.2 Sexy relation network of the patients with AIDS[18]

2.1 方法對(duì)比

分別用本文提出的方法、度方法、凝聚性方法、介數(shù)方法以及節(jié)點(diǎn)刪除法對(duì)艾滋病患者性關(guān)系網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性進(jìn)行評(píng)估，計(jì)算結(jié)果如表1所示.

在圖2中，可以看到僅僅通過節(jié)點(diǎn)度并不能夠很好地區(qū)別不同節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)整體的影響，例如，節(jié)點(diǎn)8、11、20和38盡管都擁有相同的度3，但由于所連接的鄰居節(jié)點(diǎn)之間度的差異對(duì)它們的影響，4個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中所起的作用顯然不同.實(shí)驗(yàn)結(jié)果表明基于局域角度的網(wǎng)絡(luò)節(jié)點(diǎn)重要性的度量方法能更細(xì)致地刻畫網(wǎng)絡(luò)中節(jié)點(diǎn)之間的差異性.

表1 節(jié)點(diǎn)重要性評(píng)估結(jié)果Tab.1 Valuable results of node importance

不同的指標(biāo)是從不同的角度來探討同一問題的，所以指標(biāo)無所謂好壞，每個(gè)指標(biāo)都有自身的優(yōu)點(diǎn)和缺點(diǎn)，如節(jié)點(diǎn)度注重節(jié)點(diǎn)在局部的影響，而無法體現(xiàn)節(jié)點(diǎn)在網(wǎng)絡(luò)中的整體作用；凝聚性強(qiáng)調(diào)節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)廣播消息需要的總花費(fèi)，而忽視了信息傳播過程中的覆蓋率等.本文提出的節(jié)點(diǎn)重要性的度量方法，從網(wǎng)絡(luò)的局部特征入手，不僅能充分體現(xiàn)節(jié)點(diǎn)本身的影響力，而且也全面地考慮了節(jié)點(diǎn)的鄰居對(duì)節(jié)點(diǎn)本身的間接影響效應(yīng)，這在人際關(guān)系網(wǎng)絡(luò)、渠道銷售網(wǎng)絡(luò)、傳染病網(wǎng)絡(luò)等許多實(shí)際網(wǎng)絡(luò)中，在無法獲得網(wǎng)絡(luò)的全局信息和網(wǎng)絡(luò)規(guī)模龐大的情況下，應(yīng)用本文所提出的方法更符合事實(shí)，對(duì)實(shí)際應(yīng)用有指導(dǎo)意義.

2.2 時(shí)間復(fù)雜度對(duì)比分析

幾乎所有的復(fù)雜系統(tǒng)都可以抽象成網(wǎng)絡(luò)模型，這些網(wǎng)絡(luò)往往具有大量的節(jié)點(diǎn)，網(wǎng)絡(luò)規(guī)模龐大，這使得在實(shí)際的情況下，考慮度量網(wǎng)絡(luò)節(jié)點(diǎn)的重要性方法的同時(shí)，也不得不關(guān)注算法的時(shí)間復(fù)雜度，關(guān)注對(duì)大型的復(fù)雜網(wǎng)絡(luò)應(yīng)用此類方法能不能獲得理想的計(jì)算能力.

本文對(duì)比了幾類典型的網(wǎng)絡(luò)節(jié)點(diǎn)重要性的評(píng)估方法，如表2所示.

表2 時(shí)間復(fù)雜度對(duì)比Tab.2 Comparison of time complexity

方法的時(shí)間復(fù)雜度對(duì)比分析中，n為網(wǎng)絡(luò)的規(guī)模，m為網(wǎng)絡(luò)的邊數(shù)目.從方法的時(shí)間復(fù)雜度對(duì)比中可以看到，本文提出的評(píng)估節(jié)點(diǎn)重要性的局部特征方法的時(shí)間復(fù)雜度僅為o（m＋n〈k〉），明顯低于介數(shù)、凝聚性、網(wǎng)絡(luò)流、隨機(jī)行走、特征向量和子圖等評(píng)估方法.而且，各方法對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)評(píng)估的對(duì)比，也說明了此方法的有效性.在現(xiàn)實(shí)的絕大多數(shù)網(wǎng)絡(luò)中，如Internet、WWW、電子郵件網(wǎng)絡(luò)等，網(wǎng)絡(luò)規(guī)模龐大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，因此，急需一種簡(jiǎn)單、計(jì)算時(shí)間復(fù)雜度小，同時(shí)又有效的方法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)重要性進(jìn)行評(píng)估.而局域特征方法一方面克服了全局法應(yīng)用的局限，又在一定程度上使網(wǎng)絡(luò)中心節(jié)點(diǎn)的判別方法得以簡(jiǎn)化，計(jì)算的時(shí)間復(fù)雜度僅線性相關(guān)于網(wǎng)絡(luò)的規(guī)模，因此可以使得在效率、方法的有效性等方面更優(yōu)于已有的方法.本方法對(duì)于大型的復(fù)雜網(wǎng)絡(luò)可以獲得更理想的計(jì)算速度.

3 結(jié)論與展望

通過本文提出的方法與其他幾種典型的節(jié)點(diǎn)重要性評(píng)估的方法結(jié)果的對(duì)比、算法的時(shí)間復(fù)雜度的分析，認(rèn)為新方法具有以下優(yōu)點(diǎn)：

（1）依據(jù)網(wǎng)絡(luò)局部特征來評(píng)判網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，避免了對(duì)網(wǎng)絡(luò)全局架構(gòu)的了解；

（2）方法簡(jiǎn)單有效，只考慮了所關(guān)注節(jié)點(diǎn)本身的度及其鄰居節(jié)點(diǎn)的度的情況，在現(xiàn)實(shí)生活中，很容易獲得數(shù)據(jù)；

（3）算法的時(shí)間復(fù)雜度很小，對(duì)于大型的網(wǎng)絡(luò)而言是一個(gè)比較優(yōu)越的算法.

從方法的對(duì)比中可以發(fā)現(xiàn)，本文所提出的方法與介數(shù)存在一定的關(guān)聯(lián)性，如前面的幾個(gè)重要節(jié)點(diǎn)序列是一致的，然而在某些節(jié)點(diǎn)上也存在很大的分歧，如節(jié)點(diǎn)33，雖然不同的方法考慮問題的角度不同，但是本文所提出的方法與節(jié)點(diǎn)的介數(shù)方法間的相似性，絕不是偶然.如果能夠從網(wǎng)絡(luò)的局域角度獲得一種方法，并能夠很好地代替介數(shù)方法，這樣就有效地避免了介數(shù)方法存在的兩個(gè)缺陷：一是要了解網(wǎng)絡(luò)的全局信息，二是算法的高時(shí)間復(fù)雜度.尋找一種有效的方法更好地?cái)M合介數(shù)方法，這將在實(shí)際的網(wǎng)絡(luò)應(yīng)用中具有更大的價(jià)值.

[1]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review，2003，45（2）：167－256

[2]GUIMERA R，AMARAL L A N.Modeling the world－wide airport network [J]. The European Physical Journal B，2004，38（2）：381－385

[3]KINNEY R，CRUCITTI P，ALBERT R，etal.Modeling cascading failures in the North American power grid [J].The European Physical Journal B，2005，46（1）：101－107

[4]FALOUTSOS M，F(xiàn)ALOUTSOS P，F(xiàn)ALOUTSOS C. On power－law relationships of the internet topology [J].Computer Communications Review，1999，29（4）：251－262

[5]JEONG H，MASON S，BARABSI A L，etal.The large－scale organization of metabolic networks [J].Nature，2000，407（6804）：651－654

[6]NEWMAN M E J.The structure of scientific collaboration networks [J]. Proceedings of the National Academy of Sciences，2001，98（2）：404－409

[7]FREEMAN C L.A set of measures of centrality based on betweenness[J].Sociometry，1977，40（1）：35－41

[8]FREEMAN C L.Centrality in social networks：I.Conceptual clarication [J].Social Networks，1979，1（3）：215－239

[9]FREEMAN L C，ROEDER D，MULHOLLAND R R.Centrality in social networks：ii.Experimental results[J].Social Networks，1979，2（2）：119－141

[10]BARTHELEMY M.Betweenness centrality in large complex networks [J]. The European Physical Journal B，2004，38（2）：163－168

[11]GOH K I，OH E，KAHNG B，etal.Betweenness centrality correlation in social networks [J].Physical Review E－Statistical，Nonlinear，and Soft Matter Physics，2003，67（1）：017101－1－017101－4

[12]ESTRADA E，RODRGUEZ－VELZQUEZ J A.Subgraph centrality in complex networks [J].Physical Review E－Statistical，Nonlinear，and Soft Matter Physics，2005，71（5）：056103－1－056103－9

[13]PERRA N，F(xiàn)ORTUNATO S.Spectral centrality measures in complex networks[J].Physical Review E－Statistical，Nonlinear，and Soft Matter Physics，2008，78（3）：036107－1－036107－10

[14]NEWMAN M E J.A measure of betweenness centrality based on random walk [J]. Social Networks，2005，27（1）：39－54

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

[16]李翔鵬，任玉晴，席酉民.網(wǎng)絡(luò)節(jié)點(diǎn)（集）重要性的一種度量指標(biāo)[J].系統(tǒng)工程，2004，22（4）：13－20

[17]許 進(jìn)，席酉民，汪應(yīng)洛.系統(tǒng)的核與核度理論[J].系統(tǒng)科學(xué)與數(shù)學(xué)，1993，13（2）：102－110

[18]KLOVDAHL A S.Socail networks and the spread of infectious diseases：the AIDS example[J].Social Science Methods，1985，21（11）：1203－1216