復雜網絡中節(jié)點重要性排序的研究進展

劉建國，任卓明，郭強，等

摘要：目的：如何用定量分析的方法識別超大規(guī)模網絡中哪些節(jié)點最重要，或者評價某個節(jié)點相對于其他一個或多個節(jié)點的重要程度，這是復雜網絡研究中亟待解決的重要問題之一。方法：本文首先介紹了基于網絡結構的節(jié)點重要性排序度量指標，這類指標主要從網絡的局部屬性、全局屬性、網絡的位置和隨機游走等4個方面展開，同時對這些方法的優(yōu)缺點及適用范圍進行了分析；然后介紹了傳播動力學與節(jié)點重要性度量指標的關系；最后在總結和展望部分指出了當前面臨的問題和可能的發(fā)展方向。結果：復雜網絡中節(jié)點重要性可以是節(jié)點的影響力、地位或者其他因素的綜合。從網絡拓撲結構入手是研究這一問題常用的方法之一?；诰W絡局部屬性的節(jié)點重要性排序指標主要考慮節(jié)點自身信息和其鄰居信息，這些指標計算簡單，時間復雜度低，可以用于大型網絡。如：節(jié)點的度（degree），簡單直觀，但只反映了節(jié)點的局部特征?？紤]節(jié)點多級鄰居信息的指標（local centrality）比度更準確，但是沒有考慮鄰居之間的緊密程度?；诰W絡全局屬性的節(jié)點重要性排序指標主要考慮網絡全局信息，如：特征向量（eigenvector）考慮了節(jié)點鄰居的重要性，但它的缺點是簡單的將各節(jié)點的拓撲特性進行了線性疊加；Katz指標根據路徑長短給鄰居賦予不同的權重，區(qū)分了不同鄰居對節(jié)點的不同影響力，但是此方法不易獲得權重衰減因子的最優(yōu)值；緊密度（closeness centrality）指標通過網絡對部分節(jié)點產生全局影響；Kernel函數法則是通過網絡對所有節(jié)點產生全局影響；介數（betweenness）指標在識別重要節(jié)點時考慮了節(jié)點的信息負載能力；可達性（accessibility）指標通過計算節(jié)點到達目標節(jié)點的可能性來說明節(jié)點的重要程度。這些指標一般準確性比較高，但時間復雜度高，且不適用于大型網絡。此外，節(jié)點重要性還依賴于其在整個網絡中的位置，k-核分解考慮了節(jié)點在網絡中位置的全局特性，該指標時間復雜度低，適用于大型網絡，且比度、介數更能準確識別出有影響力的節(jié)點，但是不適用于樹狀網絡和 BA網絡?；旌隙确纸夥ǎ∕DD）解決了樹狀網絡和BA網絡不適用的問題，但是不容易確定最佳權重因子?；陔S機游走的節(jié)點重要性排序方法主要是基于網頁之間的鏈接關系的網頁排序技術，如PageRank考慮了網絡的全局拓撲特性，但當網絡中存在孤立節(jié)點或社團時會導致排序不唯一。LeaderRank算法解決了這一缺陷，并對網絡噪音有更好的容忍性，但不適用于無向網絡。HITS算法時間復雜度低，在學術界得到廣泛運用，然而它不能識別非正常目的的網頁引用，會導致計算結果與實際結果有偏差。除了上述4類方法外，有些方法分別從網絡的連通性、節(jié)點刪除法、邊權值、節(jié)點效率等視角度量節(jié)點重要性。通過分析傳播動力學與節(jié)點重要性度量指標之間的關系，發(fā)現節(jié)點重要性排序不僅僅由網絡結構決定，還受網絡行為傳播機制以及節(jié)點自身特性的影響。結論：節(jié)點重要性排序的指標在涉及網絡的結構信息時，都是從某一個角度對于網絡的某一方面的結構特點進行刻畫，如果目標網絡的結構在該方面特征顯著，即可得到較好的效果；或在復雜網絡環(huán)境下，通過節(jié)點的網絡傳播行為的影響力與網絡結構關系判斷節(jié)點的重要性。復雜網絡節(jié)點重要性的研究還有非常多的問題沒有解決，如，（1）節(jié)點重要性的定義。節(jié)點的重要性含義不同，評價節(jié)點重要性排名的結果也不同。（2）各種指標間的內在聯系。各種節(jié)點重要性排序的方法層出不窮，這些指標從不同視角評價節(jié)點重要性。（3）網絡結構和網絡行為是如何影響節(jié)點重要性評價，特別是對研究社會影響力非常有幫助。（4）時變網絡中，網絡結構是變化的，節(jié)點的各種指標具有動態(tài)性，如何在這種具有大數據特征的時變網絡中對節(jié)點重要性排名，這將是一個極具有挑戰(zhàn)性的課題。

來源出版物：物理學報, 2013, 62(17): 178901

入選年份：2016