物理學

復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性排序的研究進展

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

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

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

入選年份：2016