孟昱煜，王 霄，閆光輝，羅 浩，楊 波，張 磊，王 瓊

1.蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

2.國(guó)網(wǎng)甘肅省電力公司信息通信公司，蘭州 730070

隨著信息技術(shù)的發(fā)展，復(fù)雜網(wǎng)絡(luò)（complex networks）已經(jīng)深入到人類社會(huì)的各個(gè)方面[1]。作為刻畫(huà)復(fù)雜系統(tǒng)相互作用的重要工具[2]，復(fù)雜網(wǎng)絡(luò)可以描述自然界中的大量復(fù)雜系統(tǒng)，如生物領(lǐng)域的食物鏈網(wǎng)絡(luò)[3]、新陳代謝網(wǎng)絡(luò)[4]；信息領(lǐng)域的www網(wǎng)絡(luò)[5]、論文引用網(wǎng)絡(luò)[6]等。復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)在結(jié)構(gòu)和功能上承擔(dān)著不同作用[7]，其中重要節(jié)點(diǎn)是指相比復(fù)雜網(wǎng)絡(luò)的其他節(jié)點(diǎn)而言能夠在更大程度上影響網(wǎng)絡(luò)的結(jié)構(gòu)與功能的一些特殊節(jié)點(diǎn)，重要節(jié)點(diǎn)排序?qū)τ谕诰蚓W(wǎng)絡(luò)的重要節(jié)點(diǎn)意義重大。重要節(jié)點(diǎn)數(shù)量很少，但其影響卻可以快速地波及到網(wǎng)絡(luò)中大部分節(jié)點(diǎn)[8]。如微博中最有影響力的幾個(gè)用戶所發(fā)的微博很快就能傳遍整個(gè)網(wǎng)絡(luò)[9]；僅僅1%的公司卻控制著40%的全球經(jīng)濟(jì)[10]；再如2019年12月在湖北省武漢市爆發(fā)的新型冠狀病毒通過(guò)少數(shù)感染人群在較短時(shí)間將疫情蔓延至全國(guó)[11]，如果能夠通過(guò)重要節(jié)點(diǎn)排序算法對(duì)超級(jí)傳播者[12]（即重要節(jié)點(diǎn)）早發(fā)現(xiàn)早隔離，就能夠盡早控制住疫情。

在網(wǎng)絡(luò)科學(xué)研究中，設(shè)計(jì)有效的重要節(jié)點(diǎn)排序算法，有著很強(qiáng)的理論研究和實(shí)踐意義[13]。學(xué)者們?cè)谥匾?jié)點(diǎn)排序上提出了很多指標(biāo)與算法[14]，大致可分為4類：（1）基于節(jié)點(diǎn)近鄰的排序算法。其中，度中心性DC（degree centrality）[15]僅考察節(jié)點(diǎn)的直接鄰居數(shù)目；H指數(shù)（H-index）[16]定義為節(jié)點(diǎn)至少有h個(gè)鄰居的度不小于h的最大h值；K-殼分解法（K-shell）[17]認(rèn)為節(jié)點(diǎn)的重要性取決于節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，通過(guò)將外圍節(jié)點(diǎn)層層剝?nèi)ィ诰虺鼍哂休^高重要性的內(nèi)層節(jié)點(diǎn)。度數(shù)（歸一化后為度中心性DC）、H指數(shù)H-index和核數(shù)或者殼數(shù)Kshell是H算子作用下的初始態(tài)、中間態(tài)和穩(wěn)態(tài)[18]，它們對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)重要性的劃分是粗粒化的。這類算法最簡(jiǎn)單直觀，缺點(diǎn)是僅僅考慮了網(wǎng)絡(luò)節(jié)點(diǎn)的鄰居信息，忽略了路徑對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性的影響。（2）基于路徑的排序算法。其中，介數(shù)中心性BC（betweenness centrality）[15]認(rèn)為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)的最短路徑中，經(jīng)過(guò)一個(gè)節(jié)點(diǎn)的最短路徑數(shù)越多，這個(gè)節(jié)點(diǎn)就越重要[8]；接近中心性CC（closeness centrality）[15]認(rèn)為一個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的平均距離越小，該節(jié)點(diǎn)的接近中心性就越大[8]。這類算法的缺點(diǎn)是僅僅考慮了網(wǎng)絡(luò)路徑的信息，忽略了節(jié)點(diǎn)近鄰的影響，且時(shí)間復(fù)雜度較高。（3）基于迭代優(yōu)化的排序算法。其中，特征向量中心性EC（eigenvector centrality）[19]認(rèn)為一個(gè)節(jié)點(diǎn)的重要性既取決于其鄰居節(jié)點(diǎn)的數(shù)量（即該節(jié)點(diǎn)的度），也取決于每個(gè)鄰居節(jié)點(diǎn)的重要性；PageRank[20]是網(wǎng)頁(yè)排序領(lǐng)域中的著名算法，它認(rèn)為萬(wàn)維網(wǎng)中一個(gè)頁(yè)面的重要性取決于指向它的其他頁(yè)面的數(shù)量和質(zhì)量，如果一個(gè)頁(yè)面被很多高質(zhì)量頁(yè)面指向，則這個(gè)頁(yè)面的質(zhì)量也高[8]，其主要應(yīng)用于有向網(wǎng)絡(luò)。（4）基于節(jié)點(diǎn)移除和收縮的排序算法。其中，節(jié)點(diǎn)刪除的生成樹(shù)法通過(guò)計(jì)算節(jié)點(diǎn)刪除后網(wǎng)絡(luò)的生成樹(shù)的減少比例來(lái)反映節(jié)點(diǎn)的重要性。這類算法研究節(jié)點(diǎn)移除或者收縮后網(wǎng)絡(luò)的結(jié)構(gòu)與功能的變化，是一種動(dòng)態(tài)的方法，缺點(diǎn)是計(jì)算復(fù)雜度較高，與上述3類方法相比，更像是一種對(duì)于重要節(jié)點(diǎn)排序算法的評(píng)價(jià)指標(biāo)。

如果兩個(gè)社團(tuán)之間僅通過(guò)一個(gè)節(jié)點(diǎn)連接，那么，雖然這個(gè)節(jié)點(diǎn)只有很小的度，但是卻具有極大的重要性，因?yàn)樗哂泻艽蟮慕閿?shù)，隨著這樣的節(jié)點(diǎn)的移除，網(wǎng)絡(luò)的連通性將會(huì)急劇降低。在真實(shí)網(wǎng)絡(luò)中，很多的節(jié)點(diǎn)往往只與一個(gè)度很大的節(jié)點(diǎn)直接連接，當(dāng)這個(gè)度大的節(jié)點(diǎn)處在網(wǎng)絡(luò)邊緣時(shí)，雖然它的介數(shù)會(huì)很小，但是它卻很重要，因?yàn)樗哂泻艽蟮墓?jié)點(diǎn)度，隨著這樣的節(jié)點(diǎn)的移除，網(wǎng)絡(luò)中將會(huì)產(chǎn)生很多孤立節(jié)點(diǎn)，網(wǎng)絡(luò)的最大連通分支的節(jié)點(diǎn)數(shù)目也會(huì)快速下降。當(dāng)用度中心性DC來(lái)評(píng)價(jià)節(jié)點(diǎn)重要性時(shí)，不能很好地識(shí)別上述度小而介數(shù)大的重要節(jié)點(diǎn)；當(dāng)用介數(shù)中心性BC來(lái)評(píng)價(jià)節(jié)點(diǎn)重要性時(shí)，對(duì)上述度大而介數(shù)小的重要節(jié)點(diǎn)的識(shí)別能力較弱；當(dāng)用接近中心性CC來(lái)評(píng)價(jià)節(jié)點(diǎn)重要性時(shí)，由于和介數(shù)中心性BC一樣也是一種基于路徑的重要節(jié)點(diǎn)排序算法，同樣會(huì)忽略節(jié)點(diǎn)度對(duì)節(jié)點(diǎn)重要性的影響，甚至對(duì)于上述那種處在網(wǎng)絡(luò)邊緣的度大的節(jié)點(diǎn)，接近中心性CC認(rèn)為它的重要性甚至不如去除后對(duì)網(wǎng)絡(luò)結(jié)構(gòu)與功能幾乎沒(méi)有太大影響的處在網(wǎng)絡(luò)較中心位置的節(jié)點(diǎn)；當(dāng)用特征向量中心性EC評(píng)價(jià)節(jié)點(diǎn)重要性時(shí)，由于其認(rèn)為一個(gè)節(jié)點(diǎn)的重要性既取決于其鄰居節(jié)點(diǎn)的數(shù)量，也取決于每個(gè)鄰居節(jié)點(diǎn)的重要性，說(shuō)明節(jié)點(diǎn)對(duì)其鄰居有很強(qiáng)的依賴性，當(dāng)其鄰居從網(wǎng)絡(luò)中移除后，這種節(jié)點(diǎn)的后續(xù)移除往往對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)與功能不會(huì)有太大影響，因?yàn)樗闹匾砸蕾囉谄溧従拥闹匾?，而?dāng)其鄰居節(jié)點(diǎn)移除后，它的重要性也會(huì)快速衰減。

盡管專家學(xué)者在重要節(jié)點(diǎn)排序領(lǐng)域開(kāi)展了大量的研究工作，也取得了豐碩的成果，但基于節(jié)點(diǎn)近鄰的算法往往忽略了路徑對(duì)節(jié)點(diǎn)重要性的影響，基于路徑的算法也不能對(duì)節(jié)點(diǎn)近鄰進(jìn)行充分考慮，基于特征向量的排序算法太過(guò)依賴于其鄰居節(jié)點(diǎn)的重要性，算法在重要節(jié)點(diǎn)排序精度方面仍然存在提升之處。Li等人[21]提出的GM算法和其局部算法LGM充分結(jié)合了網(wǎng)絡(luò)中節(jié)點(diǎn)近鄰和路徑的信息，在引力公式的啟發(fā)下，通過(guò)把節(jié)點(diǎn)的度看作物體的質(zhì)量，把節(jié)點(diǎn)間的最短路徑長(zhǎng)度看作物體間的距離，深化了引力模型的內(nèi)涵?？系?tīng)柕燃?jí)相關(guān)系數(shù)τ[22]可以用來(lái)衡量重要節(jié)點(diǎn)排序算法賦予給節(jié)點(diǎn)的重要性值序列與SIR傳播模型[23]中的對(duì)應(yīng)節(jié)點(diǎn)的影響力序列之間的一致性強(qiáng)度，將其作為評(píng)價(jià)指標(biāo)，顯示出了這兩種算法的優(yōu)勢(shì)。在GM算法和LGM算法的基礎(chǔ)上，考慮到節(jié)點(diǎn)間影響力隨著節(jié)點(diǎn)度數(shù)的增大而增大，隨著節(jié)點(diǎn)間最短路徑長(zhǎng)度的增大而減小，受到彈簧模型的啟發(fā)，進(jìn)一步融合網(wǎng)絡(luò)節(jié)點(diǎn)近鄰和路徑信息，并結(jié)合網(wǎng)絡(luò)直徑，提出SM算法和其局部算法LSM。將其與GM、LGM以及網(wǎng)絡(luò)對(duì)于節(jié)點(diǎn)移除的魯棒性和脆弱性的2種表現(xiàn)最好的經(jīng)典算法DC和BC進(jìn)行比較，在2種合成網(wǎng)絡(luò)和4種真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果表明SM算法和LSM算法對(duì)于網(wǎng)絡(luò)中重要節(jié)點(diǎn)排序具有更高的準(zhǔn)確性。特別地，在SIR傳播模型下，將SM算法得到的排名靠前的重要節(jié)點(diǎn)作為一個(gè)感染節(jié)點(diǎn)集合，在Power網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果顯示該感染集相較于其他算法得到的感染集能以更快的速度感染網(wǎng)絡(luò)中的其他易感節(jié)點(diǎn)，穩(wěn)態(tài)時(shí)也具有更大的感染范圍，證明SM算法對(duì)于網(wǎng)絡(luò)中重要節(jié)點(diǎn)排序具有更高的合理性和有效性。

1 重要節(jié)點(diǎn)排序算法

1.1 GM算法和LGM算法

GM算法和LGM算法用節(jié)點(diǎn)引力來(lái)描述節(jié)點(diǎn)的重要性，也就是影響力。其中，GM算法充分結(jié)合網(wǎng)絡(luò)中節(jié)點(diǎn)近鄰信息和節(jié)點(diǎn)間的路徑信息，在引力公式的啟發(fā)下，通過(guò)把網(wǎng)絡(luò)中節(jié)點(diǎn)的度看作物體質(zhì)量，把節(jié)點(diǎn)間的最短路徑長(zhǎng)度看作物體之間的距離，計(jì)算出各節(jié)點(diǎn)之間的引力，遍歷求和得到每個(gè)節(jié)點(diǎn)的總引力，對(duì)其從大到小排序得到一個(gè)重要節(jié)點(diǎn)排序結(jié)果。

定義1G i定義為網(wǎng)絡(luò)中節(jié)點(diǎn)i的引力，其計(jì)算公式為：

其中，k i代表節(jié)點(diǎn)i的度，d ij代表節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑長(zhǎng)度，j遍歷網(wǎng)絡(luò)中i以外的所有其他節(jié)點(diǎn)。令節(jié)點(diǎn)自身之間的引力為0。

定義2為了降低GM算法的計(jì)算復(fù)雜度，通過(guò)只考慮截?cái)喟霃絩 g以內(nèi)的引力，提出了LGM算法，G r i定義為網(wǎng)絡(luò)節(jié)點(diǎn)i的局部引力，其計(jì)算公式為：

在14個(gè)數(shù)據(jù)集里，與經(jīng)典算法相比，GM算法和LGM算法賦予給節(jié)點(diǎn)的重要性值（引力）序列與SIR模型中的對(duì)應(yīng)節(jié)點(diǎn)的影響力序列之間的肯德?tīng)柕燃?jí)相關(guān)系數(shù)τ取得了較大值，甚至在某些數(shù)據(jù)集里，LGM算法取得了最大的τ，體現(xiàn)了算法的優(yōu)越性[21]。觀察公式（1）和（2），對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)i，如果它有較小的節(jié)點(diǎn)度k i，那么很難通過(guò)計(jì)算得到較大的引力Gi和局部引力G r i。由于引力和局部引力的計(jì)算公式中的分母都是平方項(xiàng)，節(jié)點(diǎn)與其低階鄰居之間具有較小的最短路徑長(zhǎng)度，因此，G i和G r i的值主要由低階鄰居的節(jié)點(diǎn)度決定。節(jié)點(diǎn)引力（包含局部引力）的計(jì)算公式?jīng)Q定了GM算法和LGM算法對(duì)度小的重要節(jié)點(diǎn)識(shí)別能力較弱，并且節(jié)點(diǎn)的引力依賴于近鄰節(jié)點(diǎn)的度數(shù)，用網(wǎng)絡(luò)的魯棒性和脆弱性指標(biāo)評(píng)價(jià)重要節(jié)點(diǎn)排序算法時(shí)，度大的節(jié)點(diǎn)和其近鄰節(jié)點(diǎn)往往具有較大的節(jié)點(diǎn)引力，當(dāng)度大的節(jié)點(diǎn)從網(wǎng)絡(luò)中移除后，一般來(lái)說(shuō)，其引力較大的近鄰節(jié)點(diǎn)的后續(xù)移除并不能在很大程度上影響網(wǎng)絡(luò)的結(jié)構(gòu)與功能，說(shuō)明算法在重要節(jié)點(diǎn)排序精度方面仍然存在提升之處。為進(jìn)一步提升算法在網(wǎng)絡(luò)的魯棒性和脆弱性方面的表現(xiàn)，在彈簧模型的啟發(fā)下，提出SM算法和LSM算法。

1.2 SM算法和LSM算法

將以胡克定律[24]為基礎(chǔ)的彈簧模型引入到復(fù)雜網(wǎng)絡(luò)的重要節(jié)點(diǎn)排序領(lǐng)域，提出基于彈簧模型的重要節(jié)點(diǎn)排序算法SM和其局部算法LSM。

定義3在彈簧模型中，F(xiàn)定義為彈簧的彈力，其計(jì)算公式為：

公式（3）是彈簧模型的表達(dá)式。其中，F(xiàn)代表彈簧的彈力，k代表彈簧的勁度系數(shù)，x代表彈簧的形變量?？紤]到彈簧的彈力隨著彈簧的勁度系數(shù)和形變量的增大而增大，類似地，復(fù)雜網(wǎng)絡(luò)中兩節(jié)點(diǎn)之間的影響力隨著節(jié)點(diǎn)鄰居數(shù)目（度數(shù)）的增大而增大，隨著節(jié)點(diǎn)間最短路徑長(zhǎng)度的增大而減小，也就是說(shuō)隨著網(wǎng)絡(luò)直徑d與網(wǎng)絡(luò)節(jié)點(diǎn)間最短路徑長(zhǎng)度的差值的增大而增大，將網(wǎng)絡(luò)中的節(jié)點(diǎn)i和節(jié)點(diǎn)j以及它們之間的最短路徑看作一個(gè)原長(zhǎng)為網(wǎng)絡(luò)直徑d的彈簧，基于彈簧模型，并受GM算法的引力計(jì)算公式的啟發(fā)，把節(jié)點(diǎn)i和節(jié)點(diǎn)j的度的乘積k i k j視作彈簧的勁度系數(shù)k，把網(wǎng)絡(luò)直徑d與兩節(jié)點(diǎn)間的最短路徑長(zhǎng)度d ij的差值d-d ij視作彈簧的形變量，將兩節(jié)點(diǎn)之間的彈力視作彈簧的彈力F，并將其視為標(biāo)量，只考慮大小，不考慮方向，即可計(jì)算得到網(wǎng)絡(luò)中各節(jié)點(diǎn)與其他所有節(jié)點(diǎn)間的總彈力，也就是各節(jié)點(diǎn)的重要性值。

定義4S ij定義為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的彈力，其計(jì)算公式為：

SM算法和LSM算法用節(jié)點(diǎn)彈力來(lái)描述節(jié)點(diǎn)的重要性，或者說(shuō)影響力。其中，SM算法進(jìn)一步考慮網(wǎng)絡(luò)中節(jié)點(diǎn)近鄰信息和節(jié)點(diǎn)間的路徑信息，并結(jié)合了網(wǎng)絡(luò)直徑d。為提高重要節(jié)點(diǎn)排序精度，基于彈簧模型，借助胡克定律，計(jì)算各節(jié)點(diǎn)之間的彈力，遍歷求和得到每個(gè)節(jié)點(diǎn)的總彈力，對(duì)其從大到小排序得到一個(gè)重要節(jié)點(diǎn)排序結(jié)果。SM算法與GM算法的最大不同是：SM算法考慮了網(wǎng)絡(luò)直徑d對(duì)節(jié)點(diǎn)重要性的影響。

定義5Si定義為網(wǎng)絡(luò)中節(jié)點(diǎn)i的彈力，其計(jì)算公式為：

令節(jié)點(diǎn)自身之間的彈力為0。公式（5）表明：（1）有較多鄰居數(shù)目和較小最短路徑長(zhǎng)度的兩節(jié)點(diǎn)間具有較大的影響力，符合直觀判斷。（2）節(jié)點(diǎn)的鄰居數(shù)目越多，與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的最短路徑長(zhǎng)度越小，節(jié)點(diǎn)的影響力越大，即越重要。（3）兩節(jié)點(diǎn)間的最短路徑長(zhǎng)度為d時(shí)，節(jié)點(diǎn)間影響力為0。（4）網(wǎng)絡(luò)直徑反映出網(wǎng)絡(luò)中具有最大最短路徑長(zhǎng)度的兩節(jié)點(diǎn)間建立聯(lián)系的困難程度，且是一種網(wǎng)絡(luò)尺寸度量。有相同k i、k j和d ij值的兩節(jié)點(diǎn)i和j處在不同網(wǎng)絡(luò)直徑的網(wǎng)絡(luò)時(shí)，它們之間的影響力是不同的，SM算法認(rèn)為處在較大網(wǎng)絡(luò)直徑的網(wǎng)絡(luò)時(shí)兩節(jié)點(diǎn)間的影響力較大。下面給出SM算法的偽碼描述：

算法1 SM重要節(jié)點(diǎn)排序算法

Input：undirected networkG=(V,E)

Output：the result of node ranking

1.begin

2. calculate the degreek′of each node，the shortest path lengthd′between nodes and the network diameterd

3. for nodeiinVdo

4. calculateSiaccording to formula（5）

5. end

6. rankSifrom large to small to get the result of node ranking

7.end

下面分析算法的時(shí)間復(fù)雜度。對(duì)于給定的復(fù)雜網(wǎng)絡(luò)G，網(wǎng)絡(luò)包含n個(gè)節(jié)點(diǎn)和m條邊，SM算法的時(shí)間耗費(fèi)主要在于計(jì)算所有節(jié)點(diǎn)對(duì)之間的最短路徑長(zhǎng)度，通過(guò)Johnson算法[25]計(jì)算全源最短路徑的時(shí)間復(fù)雜度為O(n2lbn+nm)，因此SM算法的時(shí)間復(fù)雜度為O(n2lbn+nm)。

定義6通過(guò)只考慮截?cái)喟霃絩 s以內(nèi)的彈力，提出LSM算法以降低SM算法的計(jì)算復(fù)雜度，S ri定義為網(wǎng)絡(luò)節(jié)點(diǎn)i的局部彈力，其計(jì)算公式為：將算法1中的第4步改為通過(guò)公式（6）計(jì)算節(jié)點(diǎn)i的局部彈力S ri，即可得到LSM算法的偽碼描述。同樣的，LSM算法的時(shí)間復(fù)雜度也是O(n2lbn+nm)。表1顯示了基于彈簧模型的重要節(jié)點(diǎn)排序算法SM和其局部算法LSM、基于引力模型的重要節(jié)點(diǎn)排序算法GM和其局部算法LGM、度中心性DC、介數(shù)中心性BC這6種算法的時(shí)間復(fù)雜度?？梢钥吹匠戎行男訢C外的其他5種算法具有相同的時(shí)間復(fù)雜度，均為O(n2lbn+nm)。

表1 6種算法的時(shí)間復(fù)雜度Table 1 Time complexity of six algorithms

GM算法和LGM算法的計(jì)算公式?jīng)Q定了度大的節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)會(huì)具有較大的重要性值（引力值），觀察公式（5）和公式（6），由于節(jié)點(diǎn)彈力的計(jì)算公式中k i、k j和d-d ij是一次項(xiàng)相乘的形式（對(duì)于選定網(wǎng)絡(luò)，網(wǎng)絡(luò)直徑d為定值），與GM算法和LGM算法的節(jié)點(diǎn)引力的計(jì)算公式相比，增強(qiáng)了最短路徑對(duì)節(jié)點(diǎn)重要性的影響，也就是提高了介數(shù)對(duì)于節(jié)點(diǎn)重要性的作用。介數(shù)大的節(jié)點(diǎn)有更多的最短路徑通過(guò)，從概率上來(lái)看，這類節(jié)點(diǎn)往往與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)有更小的最短路徑長(zhǎng)度，因此它會(huì)有較大的節(jié)點(diǎn)彈力。對(duì)于一些度小而介數(shù)大的節(jié)點(diǎn)，其彈力值仍然可能很大，在這點(diǎn)上，SM算法和LSM算法與GM和LGM算法有很大的不同。基于節(jié)點(diǎn)近鄰的算法（如度中心性DC）只需知道網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰居信息；基于路徑信息的算法（如介數(shù)中心性BC）只需知道節(jié)點(diǎn)間的路徑信息；基于引力模型的GM算法和LGM算法雖然考慮了節(jié)點(diǎn)的近鄰信息和路徑信息，但以網(wǎng)絡(luò)對(duì)于節(jié)點(diǎn)移除的魯棒性和脆弱性指標(biāo)評(píng)價(jià)排序算法時(shí)，由于節(jié)點(diǎn)重要性過(guò)于依賴鄰居節(jié)點(diǎn)的重要性，以至在重要節(jié)點(diǎn)排序精度方面仍然存在提升之處；基于彈簧模型的SM算法和LSM算法充分結(jié)合網(wǎng)絡(luò)中節(jié)點(diǎn)近鄰信息、路徑信息以及網(wǎng)絡(luò)統(tǒng)計(jì)特征中的直徑信息，對(duì)網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)信息有充分把握，并增強(qiáng)了最短路徑對(duì)節(jié)點(diǎn)重要性的影響，即削弱了節(jié)點(diǎn)對(duì)其鄰居節(jié)點(diǎn)的重要性的影響，當(dāng)度大的節(jié)點(diǎn)從網(wǎng)絡(luò)中移除后，對(duì)其鄰居節(jié)點(diǎn)的重要性不會(huì)有太大影響，也就是說(shuō)不會(huì)在很大程度上削弱鄰居節(jié)點(diǎn)移除對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響，維持了原網(wǎng)絡(luò)重要節(jié)點(diǎn)排序的精度，表明SM算法和LSM算法能夠?qū)W(wǎng)絡(luò)中的重要節(jié)點(diǎn)進(jìn)行更準(zhǔn)確的排序。

2 實(shí)驗(yàn)分析

2.1 數(shù)據(jù)集描述

為了客觀評(píng)價(jià)算法的有效性和適用性，選取了2種經(jīng)典的合成網(wǎng)絡(luò)和4個(gè)公開(kāi)的不同規(guī)模的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集。BA無(wú)標(biāo)度網(wǎng)絡(luò)和WS小世界網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)中最重要的2個(gè)網(wǎng)絡(luò)模型，本文基于BA無(wú)標(biāo)度網(wǎng)絡(luò)模型和WS小世界網(wǎng)絡(luò)模型構(gòu)建了2種10 000個(gè)節(jié)點(diǎn)的人工合成網(wǎng)絡(luò)：BA無(wú)標(biāo)度網(wǎng)絡(luò)（BA）和WS小世界網(wǎng)絡(luò)（WS），并選取了4種真實(shí)網(wǎng)絡(luò)：遺傳疾病網(wǎng)絡(luò)（Diseasome）[26]、蛋白質(zhì)相互作用網(wǎng)絡(luò)（Y2H）[27]、美國(guó)西部電力網(wǎng)絡(luò)（Power）[28]、性社交網(wǎng)絡(luò)（Sex）[29]，其網(wǎng)絡(luò)參數(shù)如表2所示。

表2 6種無(wú)向網(wǎng)絡(luò)的參數(shù)Table 2 Parameters of six undirected networks

2.2 網(wǎng)絡(luò)的魯棒性和脆弱性驗(yàn)證實(shí)驗(yàn)

網(wǎng)絡(luò)的魯棒性和脆弱性驗(yàn)證實(shí)驗(yàn)著重考察網(wǎng)絡(luò)中一部分節(jié)點(diǎn)移除后網(wǎng)絡(luò)結(jié)構(gòu)和功能的變化，變化越大說(shuō)明移除的節(jié)點(diǎn)越重要[8]。對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為n、連邊數(shù)為m的網(wǎng)絡(luò)，用重要節(jié)點(diǎn)排序算法對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行重要性排序，得到一個(gè)重要節(jié)點(diǎn)排序序列，再按照重要性大小依次移除網(wǎng)絡(luò)中的節(jié)點(diǎn)，直到網(wǎng)絡(luò)的節(jié)點(diǎn)集和邊集都為空集。其中，把移除i n比例的節(jié)點(diǎn)后的網(wǎng)絡(luò)的最大連通分支的節(jié)點(diǎn)數(shù)目占網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)目n的比例記為σ(i/n)。

定義7R定義為網(wǎng)絡(luò)對(duì)于節(jié)點(diǎn)移除的魯棒性（robustness）[8]：

定義8V定義為網(wǎng)絡(luò)對(duì)于節(jié)點(diǎn)移除的脆弱性（vulnerability）[8]：

V值越大代表節(jié)點(diǎn)移除方法越有效，即表示重要節(jié)點(diǎn)排序算法越好。以重要節(jié)點(diǎn)排序算法的節(jié)點(diǎn)序列作為節(jié)點(diǎn)移除序列，把i n和σ(i/n)分別作為橫縱坐標(biāo)，可在二維坐標(biāo)作出算法的σ(i/n)值隨i n的增大而減小最后趨于穩(wěn)定值0的曲線圖。在同一網(wǎng)絡(luò)中，與其他重要節(jié)點(diǎn)排序算法相比，某種排序算法作出的曲線圖，對(duì)于相同的i n，有較小σ(i/n)值，說(shuō)明移除i n比例的節(jié)點(diǎn)后，剩余網(wǎng)絡(luò)具有較小的最大連通分支節(jié)點(diǎn)數(shù)。由公式（7）和公式（8）可知，隨著i n的變化，若某種重要節(jié)點(diǎn)排序算法都有最小的σ(i/n)值，即曲線的縱坐標(biāo)離橫軸最近，則這種算法有最小的R值和最大的V值，也就是說(shuō)，算法在網(wǎng)絡(luò)的魯棒性和脆弱性指標(biāo)的評(píng)價(jià)下表現(xiàn)得最好。

以網(wǎng)絡(luò)的魯棒性和脆弱性指標(biāo)評(píng)價(jià)重要節(jié)點(diǎn)排序算法時(shí)，為了找到在此方面表現(xiàn)較好的經(jīng)典算法，選取度中心性DC、介數(shù)中心性BC、接近中心性CC、H指數(shù)H-index和K-殼分解法（K-shell）這5種經(jīng)典的重要節(jié)點(diǎn)排序算法，在上述6個(gè)數(shù)據(jù)集上進(jìn)行網(wǎng)絡(luò)的魯棒性和脆弱性實(shí)驗(yàn)，如圖1所示，其中條形圖的高度代表V值的大小，圖例中附有各種算法的V值。對(duì)上述5種排序算法得到的V值從大到小排序，可知DC和BC的V值在6個(gè)數(shù)據(jù)集中都分別居于第1和第2位。并且6種網(wǎng)絡(luò)中的曲線圖表明，DC和BC的σ(i/n)值隨著i n的增大有較大的下降趨勢(shì)，說(shuō)明以這2種算法移除網(wǎng)絡(luò)中的節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)會(huì)變得極其脆弱。由此可知，度中心性DC和介數(shù)中心性BC是在這6個(gè)數(shù)據(jù)集表現(xiàn)得最好的2種經(jīng)典算法。

圖1 經(jīng)典算法在6種網(wǎng)絡(luò)上的魯棒性和脆弱性實(shí)驗(yàn)Fig.1 Experiments on robustness and vulnerability of classical algorithms on six networks

LSM算法和LGM算法存在最優(yōu)截?cái)喟霃剑ㄊ筁SM算法和LGM算法具有最大V值的最小截?cái)喟霃剑┑倪x取問(wèn)題。為了得到LSM算法和LGM算法在較小計(jì)算復(fù)雜度下的最優(yōu)截?cái)喟霃胶?，只考慮截?cái)喟霃綖?0以內(nèi)的情況，由于BA網(wǎng)絡(luò)直徑為9，所以其只考慮到9以內(nèi)的截?cái)喟霃剑越財(cái)喟霃絩為橫坐標(biāo)，以V值為縱坐標(biāo)，在6個(gè)數(shù)據(jù)集上對(duì)比LSM算法和LGM算法在不同截?cái)喟霃絩下的V值，作出V值隨r增大而變化的折線圖V-r，實(shí)驗(yàn)圖如圖2所示。設(shè)LSM和LGM的最優(yōu)截?cái)喟霃椒謩e為和。對(duì)于BA網(wǎng)絡(luò)，如圖2（a）所示，6；對(duì)于圖2（b）、圖2（d）和圖2（e）中的WS網(wǎng)絡(luò)、Y2H網(wǎng)絡(luò)和Power網(wǎng)絡(luò)，10；對(duì)于Diseasome網(wǎng)絡(luò)，如圖2（c）所示，10，7；對(duì)于Sex網(wǎng)絡(luò)，如圖2（f）所示，7。在6種網(wǎng)絡(luò)中，LSM在取得的V值均大于LGM在取得的V值，說(shuō)明LSM算法在網(wǎng)絡(luò)的魯棒性和脆弱性上較LGM算法具有一定優(yōu)勢(shì)。為了使局部算法LSM和LGM具有更強(qiáng)的適用性，最優(yōu)截?cái)喟霃娇梢匀〕梢粋€(gè)定值。當(dāng)r s=r g=10時(shí)，實(shí)驗(yàn)結(jié)果顯示LSM算法和LGM算法在除BA網(wǎng)絡(luò)外的其他5種網(wǎng)絡(luò)中的V值均可以取到最大值。對(duì)于BA網(wǎng)絡(luò)這樣的直徑小于10的網(wǎng)絡(luò)，把最優(yōu)截?cái)喟霃饺〕删W(wǎng)絡(luò)直徑，此時(shí)，LSM算法和SM算法、LGM和GM算法完全等價(jià)。可以看到，在6種網(wǎng)絡(luò)中，以上述這種方式選取最優(yōu)截?cái)喟霃綍r(shí)，LSM算法和LGM算法可以取得最大的V值，并且，LSM算法的V值總比LGM算法的V值大，體現(xiàn)了以網(wǎng)絡(luò)魯棒性和脆弱性指標(biāo)評(píng)價(jià)排序算法時(shí)，LSM算法相較于LGM算法的優(yōu)越性。

圖2 LSM和LGM關(guān)于6種網(wǎng)絡(luò)的V-r圖Fig.2 V-r graphs of LSM and LGM on six networks

以上述方式選取在最優(yōu)截?cái)喟霃剑ňW(wǎng)絡(luò)直徑大于或等于10的網(wǎng)絡(luò)，最優(yōu)截?cái)喟霃饺?0；網(wǎng)絡(luò)直徑小于10的網(wǎng)絡(luò)，最優(yōu)截?cái)喟霃饺榫W(wǎng)絡(luò)直徑）下的LSM算法和LGM算法，以及全局算法SM和GM，還有與其他3種算法相比，表現(xiàn)得最好的經(jīng)典算法DC和BC這6種算法，在6種網(wǎng)絡(luò)上對(duì)基于彈簧模型的重要節(jié)點(diǎn)排序算法SM和局部算法LSM進(jìn)行網(wǎng)絡(luò)的魯棒性和脆弱性驗(yàn)證實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3所示。設(shè)SM、LSM、GM、LGM、DC和BC的V值分別為VSM、VLSM、VGM、VLGM、VDC和VBC。對(duì)于BA網(wǎng)絡(luò)和Sex網(wǎng)絡(luò)，如圖3（a）和圖3（f）所示，VSM=VLSM＞VGM=VLGM，反映在曲線圖中，SM和LSM的曲線基本重合，GM和LGM的曲線也幾乎一致。在6種算法中，VSM和VLSM僅小于VDC，對(duì)應(yīng)于曲線圖中SM和LSM的σ(i/n)值隨著i n的增大的下降趨勢(shì)僅小于DC的σ(i/n)值的下降趨勢(shì)。對(duì)于WS網(wǎng)絡(luò)和Power網(wǎng)絡(luò)，如圖3（b）和圖3（e）所示，VSM＞VLSM＞VGM＞VLGM，在6種算法中，VSM最大，VLSM在WS網(wǎng)絡(luò)中僅小于VSM，VLSM在Power網(wǎng)絡(luò)中僅小于VSM和VDC。對(duì)于Diseasome網(wǎng)絡(luò)，如圖3（c），VSM=VLSM＞VGM=VLGM，在6種算法中，VSM和VLSM的值最大。對(duì)于Y2H網(wǎng)絡(luò)，如圖3（d），VSM＞VLSM＞VGM=VLGM，在6種算法中，VSM與VDC相等，大于其他4種算法的V值，VLSM在Y2H網(wǎng)絡(luò)中僅小于VSM和VDC。在6種網(wǎng)絡(luò)中，VSM≥VLSM，VGM≥VLGM，說(shuō)明以網(wǎng)絡(luò)的魯棒性和脆弱性評(píng)價(jià)重要節(jié)點(diǎn)排序算法時(shí)，全局算法一般會(huì)優(yōu)于局部算法。6種網(wǎng)絡(luò)的魯棒性和脆弱性實(shí)驗(yàn)反映出SM算法和LSM算法不僅優(yōu)于GM算法和LGM算法，甚至在某些網(wǎng)絡(luò)（WS網(wǎng)絡(luò)、Diseasome網(wǎng)絡(luò)、Y2H網(wǎng)絡(luò)、Power網(wǎng)絡(luò)），SM算法的表現(xiàn)要比傳統(tǒng)的重要節(jié)點(diǎn)排序算法好。反映出用網(wǎng)絡(luò)的魯棒性和脆弱性評(píng)價(jià)重要節(jié)點(diǎn)排序算法時(shí)，SM算法和LSM算法對(duì)于網(wǎng)絡(luò)中重要節(jié)點(diǎn)排序具有更高的準(zhǔn)確性。圖3（a）和圖3（b）分別是BA無(wú)標(biāo)度網(wǎng)絡(luò)中和WS小世界網(wǎng)絡(luò)中的魯棒性和脆弱性驗(yàn)證實(shí)驗(yàn)，相比WS小世界網(wǎng)絡(luò)，6種算法在BA無(wú)標(biāo)度網(wǎng)絡(luò)中具有更大的脆弱性，說(shuō)明以重要節(jié)點(diǎn)排序算法的排序結(jié)果來(lái)移除網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)BA網(wǎng)絡(luò)的破壞程度更大，反映了BA無(wú)標(biāo)度網(wǎng)絡(luò)的少數(shù)節(jié)點(diǎn)具有極大的度、大部分節(jié)點(diǎn)具有極小的度的無(wú)標(biāo)度特性導(dǎo)致的其對(duì)蓄意攻擊（按重要性大小移除網(wǎng)絡(luò)中的節(jié)點(diǎn)）表現(xiàn)出的極大的脆弱性。WS小世界網(wǎng)絡(luò)中的較小的脆弱性反映了其高聚類的特性，高聚類說(shuō)明節(jié)點(diǎn)的鄰居之間互為鄰居的概率很大，以排序算法的排序結(jié)果來(lái)移除網(wǎng)絡(luò)中的節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)的連通性不容易遭到破壞。圖3（c）～（f）中的4種真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果與BA無(wú)標(biāo)度網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果更接近，6種算法在這5種網(wǎng)絡(luò)中都具有較大的脆弱性，且都在移除大約20%的節(jié)點(diǎn)后，網(wǎng)絡(luò)的最大連通分支的節(jié)點(diǎn)數(shù)目就趨近于0（網(wǎng)絡(luò)變得完全不連通），網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)遭到極大破壞，反映了真實(shí)網(wǎng)絡(luò)類似于BA網(wǎng)絡(luò)的無(wú)標(biāo)度特性；不同于其他5種網(wǎng)絡(luò)，圖3（b）中的WS小世界網(wǎng)絡(luò)在移除60%的節(jié)點(diǎn)后網(wǎng)絡(luò)的最大連通分支的節(jié)點(diǎn)數(shù)目才趨近于0，反映了具有高聚類特性的WS小世界網(wǎng)絡(luò)對(duì)蓄意攻擊的表現(xiàn)出的較大的魯棒性。

圖3 SM和LSM在6種網(wǎng)絡(luò)上的魯棒性和脆弱性驗(yàn)證實(shí)驗(yàn)Fig.3 Experiments on robustness and vulnerability of SM and LSM on six networks

2.3 SIR傳播模型驗(yàn)證實(shí)驗(yàn)

此類方法著重考察網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)于信息的傳播能力或者是病毒在網(wǎng)絡(luò)中的擴(kuò)散能力。SIR模型中，一個(gè)節(jié)點(diǎn)的傳播能力被定義為該節(jié)點(diǎn)的平均傳播范圍，如果一個(gè)排序算法的結(jié)果使得網(wǎng)絡(luò)流傳播又快又廣，則說(shuō)明該重要節(jié)點(diǎn)排序算法優(yōu)于其他算法[8]。

SIR模型認(rèn)為網(wǎng)絡(luò)中的節(jié)點(diǎn)有3種狀態(tài)：易感態(tài)S（susceptible）、感染態(tài)I（infected）和免疫態(tài)R（recovered）。其中，對(duì)于每個(gè)時(shí)間步t，處于感染態(tài)I的節(jié)點(diǎn)可以感染其處于易感態(tài)S的鄰居節(jié)點(diǎn)，感染概率設(shè)置為β，即它的每個(gè)處于S態(tài)的鄰居都有概率β被感染為I態(tài)節(jié)點(diǎn)。另外，設(shè)置恢復(fù)概率為λ，即每個(gè)處于I態(tài)的節(jié)點(diǎn)都有概率λ恢復(fù)為不會(huì)傳染也不會(huì)被感染的R態(tài)節(jié)點(diǎn)。設(shè)置網(wǎng)絡(luò)中所有節(jié)點(diǎn)初始狀態(tài)都為S，對(duì)于各種重要節(jié)點(diǎn)排序算法，選取其重要性排在前面的某些節(jié)點(diǎn)作為感染態(tài)節(jié)點(diǎn)I，在有限個(gè)時(shí)間步t內(nèi)進(jìn)行傳播實(shí)驗(yàn)，達(dá)到穩(wěn)態(tài)時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)只有兩種狀態(tài)：易感態(tài)S和免疫態(tài)R。I(t)和R(t)分別為t時(shí)刻網(wǎng)絡(luò)中處于I態(tài)和R態(tài)的節(jié)點(diǎn)比例。把t和t時(shí)刻感染過(guò)的節(jié)點(diǎn)比例F(t)分別作為橫縱坐標(biāo)，可作出F(t)隨t的增大而增大最后趨于穩(wěn)定的曲線圖，不難發(fā)現(xiàn)F(t)=I(t)+R(t)。對(duì)于同一網(wǎng)絡(luò)，在相同的感染率β和恢復(fù)率λ下，各種重要節(jié)點(diǎn)排序算法選取相同數(shù)目的排在前列的節(jié)點(diǎn)作為感染節(jié)點(diǎn)I，越快趨于穩(wěn)定且具有較大穩(wěn)態(tài)值的排序算法越有效。在Power網(wǎng)絡(luò)上分別選取重要性排名前5‰、10‰、20‰和50‰的節(jié)點(diǎn)，設(shè)置感染率β和恢復(fù)率λ分別為0.15和0.3，針對(duì)SM和LSM等6種重要節(jié)點(diǎn)排序算法在50個(gè)時(shí)間步t內(nèi)進(jìn)行SIR傳播驗(yàn)證實(shí)驗(yàn)（每種算法的傳播實(shí)驗(yàn)獨(dú)立運(yùn)行100次后對(duì)F(t)取平均值），實(shí)驗(yàn)結(jié)果如圖4所示。其中，圖例中各種算法的F(t)值為該算法在傳播達(dá)到穩(wěn)態(tài)時(shí)的F(t)值。對(duì)于圖4（d），即選取重要性排在前50‰的節(jié)點(diǎn)作為感染節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)傳播，比較6種排序算法（SM、LSM、GM、LGM、DC和BC），達(dá)到穩(wěn)態(tài)時(shí)，雖然LSM算法的F(t)值僅大于BC算法的F(t)值，但是基于彈簧模型的全局算法SM的F(t)值僅小于DC算法的F(t)值，并且SM曲線的斜率也僅小于DC曲線的斜率，可知SM算法的傳播速率和傳播范圍都僅次于DC算法。尤其對(duì)于圖4（a）～（c），也就是分別選取前5‰、10‰、20‰的節(jié)點(diǎn)作為感染節(jié)點(diǎn)，與其他5種排序算法的曲線比較，SM曲線有最大斜率和趨于穩(wěn)定時(shí)的最大高度（最大的F(t)值），反映出SM算法有最快感染速率和達(dá)到穩(wěn)態(tài)時(shí)的最大感染范圍，可知在這兩個(gè)方面SM算法都好于其他5種排序算法，證明了SM算法較于其他算法更高的合理性和有效性。

圖4 SM和LSM在Power網(wǎng)絡(luò)上的SIR傳播模型驗(yàn)證實(shí)驗(yàn)（感染率β=0.15，恢復(fù)率λ=0.3）Fig.4 Experiments on SIR epidemic model of SM and LSM on Power network（infected probabilityβ=0.15，recovered probabilityλ=0.3）

3 結(jié)束語(yǔ)

本文主要工作是在GM算法和LGM算法的啟發(fā)下，在彈簧模型的基礎(chǔ)上，借助胡克定律，進(jìn)一步考慮網(wǎng)絡(luò)中節(jié)點(diǎn)近鄰信息和路徑信息，并結(jié)合網(wǎng)絡(luò)直徑，提出了重要節(jié)點(diǎn)排序算法SM和其局部算法LSM。在2種合成網(wǎng)絡(luò)和4種真實(shí)網(wǎng)絡(luò)的基于網(wǎng)絡(luò)的魯棒性和脆弱性實(shí)驗(yàn)，驗(yàn)證了SM算法和LSM算法對(duì)于網(wǎng)絡(luò)中重要節(jié)點(diǎn)排序具有更高的準(zhǔn)確性。特別地，在SIR傳播模型下，在Power網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果證實(shí)SM算法得到的排名靠前的重要節(jié)點(diǎn)作為一個(gè)感染節(jié)點(diǎn)集合，與其他算法得到的感染集相比，有更快的傳播速度，達(dá)到穩(wěn)態(tài)時(shí)，有更大的傳播范圍。SM算法和LSM算法依賴于網(wǎng)絡(luò)的連通性，后續(xù)工作需要針對(duì)不連通的網(wǎng)絡(luò)，考慮對(duì)此網(wǎng)絡(luò)的重要節(jié)點(diǎn)排序算法，對(duì)其重要節(jié)點(diǎn)進(jìn)行更科學(xué)全面的排序。