基于網絡拓撲結構的重要節點發現算法

鄧曉懿， 楊 陽， 金 淳

(1.華僑大學 工商管理學院，福建 泉州 362021; 2.大連理工大學 系統工程研究所，遼寧 大連 116024)

0 引言

復雜網絡由大量節點組成，其中重要節點是少數能對整個網絡的結構及功能產生深層次影響的特殊節點。在網絡安全、信息傳播、疾病防控、犯罪預防、交通及電力傳輸等領域中，少數重要節點的影響可以快速地波及到網絡中大部分節點狀態。例如，在internet中，只需攻擊其中5%度大于5的網絡節點就能阻斷因特網的連通性[1]；美國俄亥俄州克利夫蘭市的電力傳輸故障導致了整個北美電力網絡癱瘓；在全球經濟網絡中，控制著40%財富的147家跨國公司數量不到全球公司總量的1%[2]；在SNS網站(Weibo，Twitter或Facebook)上，少數具有較強影響力的用戶所發的信息會很快就會傳遍整個網絡。因此，重要節點對網絡的結構和功能有著巨大影響, 如何發現復雜網絡中的重要節點、并度量其重要性具有重大理論意義和實際應用價值[3,4]。

在復雜網絡中，節點的重要性依賴于網絡拓撲結構，其常見度量指標有度中心性(Degree Centrality, DC)[5]、介數中心性(Betweenness Centrality, BC)[6]、接近中心性(Closeness Centrality, CC)[7]、特征向量中心性(Eigenvector Centrality, EC)[8]等。相對其他方法，EC不但蘊含著節點的特征信息(如重要性、聲望以及地位等)，同時更強調節點所處的周圍環境，認為節點重要性不但取決于其鄰居節點的數量，還取決于其鄰居節點的重要性[9]。換句話說，節點的EC值即為其所有鄰居的EC值之和，節點可通過連接其他重要節點的方式來提升自身重要性，EC值較高的節點要么和大量一般節點相連，要么和少量具有較高EC值的節點相連?！?br>