物理學(xué)

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

劉建國(guó)，任卓明，郭強(qiáng)，等

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

來(lái)源出版物：物理學(xué)報(bào), 2013, 62(17): 178901

入選年份：2016