一種基于局部特征的網絡節點重要性度量方法

王 建 偉， 榮 莉 莉， 郭 天 柱

（大連理工大學 系統工程研究所，遼寧 大連 116024）

0 引 言

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

此外，網絡節點重要性評估方法研究還有譚躍進等[15]提出的節點收縮方法，李翔鵬等[16]和許進等[17]提出的核與核度理論.前者與前面介紹的方法一樣，從節點對網絡的貢獻出發評估其重要性；后者則采用了節點刪除法的思想，用節點刪除后對網絡連通性破壞程度定義其重要性.

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

1 符號與方法的描述

1.1 網絡的表示

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

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

1.2 方法描述

網絡中節點的重要性與節點所連邊的重要性是密切相關的.

公理1 連接節點的邊越重要，節點越重要.

基于公理1，將從網絡邊的角度來探討節點的重要性.設w ij表示邊ij的權重，同時節點i的所有鄰居節點表示為Гi.

定義1 邊ij的權重定義為

其中ki表示與節點i連接的邊的數目，即節點i的度.令

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

定義2 帶有邊權的節點i的權重定義為w i表示節點i所連邊的權值之和.

由定義2可以看出，節點i的重要度取決于節點i所連邊的權值的大小，而邊的權值有兩個影響因素：一是節點i的度k i，另一個是節點i的鄰居節點的度.相同條件下，如果節點i的度k i越大，同時所對應的鄰居節點的度越大，該節點越重要.

定義3 為消除網絡規模對節點權重的影響，定義歸一化的節點i的重要性為

1.3 方法優勢分析

圖1描述了網絡節點重要性與節點的度及節點鄰居節點連接狀況之間的密切關系.

圖1 局部特征方法的優勢Fig.1 Advantages of local characteristics method

在圖1中，很明顯，節點i和j的局部特征影響了兩個節點在網絡上的重要性.在網絡的拓撲結構上，雖然兩個不同節點具有相同的度，然而由于鄰居節點的影響，節點i的重要性明顯高于節點j的重要性.可以看出，節點本身的度及其鄰居節點特征都是不能夠忽略的指標.由于考慮到了網絡節點的局部特征，本方法對于度分布較為異質的網絡，如具有無標度特性的網絡：Internet、人際關系網絡、科研合作網絡、新陳代謝網絡、引文網絡以及電子郵件網絡等，都能夠比較細致地凸現節點之間的差異性，并比較客觀地反映節點對網絡整體的影響效應.

2 實例分析

選取艾滋病患者性關系網絡作為研究對象，如圖2所示.網絡中節點表示帶有艾滋病的患者，邊表示兩個艾滋病患者之間存在性關系.

圖2 艾滋病患者性關系網絡[18]Fig.2 Sexy relation network of the patients with AIDS[18]

2.1 方法對比

分別用本文提出的方法、度方法、凝聚性方法、介數方法以及節點刪除法對艾滋病患者性關系網絡中節點的重要性進行評估，計算結果如表1所示.

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

表1 節點重要性評估結果Tab.1 Valuable results of node importance

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

2.2 時間復雜度對比分析

幾乎所有的復雜系統都可以抽象成網絡模型，這些網絡往往具有大量的節點，網絡規模龐大，這使得在實際的情況下，考慮度量網絡節點的重要性方法的同時，也不得不關注算法的時間復雜度，關注對大型的復雜網絡應用此類方法能不能獲得理想的計算能力.

本文對比了幾類典型的網絡節點重要性的評估方法，如表2所示.

表2 時間復雜度對比Tab.2 Comparison of time complexity

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

3 結論與展望

通過本文提出的方法與其他幾種典型的節點重要性評估的方法結果的對比、算法的時間復雜度的分析，認為新方法具有以下優點：

（1）依據網絡局部特征來評判網絡中節點的重要性，避免了對網絡全局架構的了解；

（2）方法簡單有效，只考慮了所關注節點本身的度及其鄰居節點的度的情況，在現實生活中，很容易獲得數據；

（3）算法的時間復雜度很小，對于大型的網絡而言是一個比較優越的算法.

從方法的對比中可以發現，本文所提出的方法與介數存在一定的關聯性，如前面的幾個重要節點序列是一致的，然而在某些節點上也存在很大的分歧，如節點33，雖然不同的方法考慮問題的角度不同，但是本文所提出的方法與節點的介數方法間的相似性，絕不是偶然.如果能夠從網絡的局域角度獲得一種方法，并能夠很好地代替介數方法，這樣就有效地避免了介數方法存在的兩個缺陷：一是要了解網絡的全局信息，二是算法的高時間復雜度.尋找一種有效的方法更好地擬合介數方法，這將在實際的網絡應用中具有更大的價值.

[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，FALOUTSOS P，FALOUTSOS 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，FORTUNATO 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].系統工程理論與實踐，2006，26（11）：79－83

[16]李翔鵬，任玉晴，席酉民.網絡節點（集）重要性的一種度量指標[J].系統工程，2004，22（4）：13－20

[17]許 進，席酉民，汪應洛.系統的核與核度理論[J].系統科學與數學，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