基于彈簧模型的重要節點排序算法

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

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

2.國網甘肅省電力公司信息通信公司，蘭州 730070

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

在網絡科學研究中，設計有效的重要節點排序算法，有著很強的理論研究和實踐意義[13]。學者們在重要節點排序上提出了很多指標與算法[14]，大致可分為4類：（1）基于節點近鄰的排序算法。其中，度中心性DC（degree centrality）[15]僅考察節點的直接鄰居數目；H指數（H-index）[16]定義為節點至少有h個鄰居的度不小于h的最大h值；K-殼分解法（K-shell）[17]認為節點的重要性取決于節點在網絡中的位置，通過將外圍節點層層剝去，挖掘出具有較高重要性的內層節點。度數（歸一化后為度中心性DC）、H指數H-index和核數或者殼數Kshell是H算子作用下的初始態、中間態和穩態[18]，它們對網絡節點重要性的劃分是粗粒化的。這類算法最簡單直觀，缺點是僅僅考慮了網絡節點的鄰居信息，忽略了路徑對網絡中的節點重要性的影響。（2）基于路徑的排序算法。其中，介數中心性BC（betweenness centrality）[15]認為網絡中所有節點對的最短路徑中，經過一個節點的最短路徑數越多，這個節點就越重要[8]；接近中心性CC（closeness centrality）[15]認為一個節點與網絡中其他節點的平均距離越小，該節點的接近中心性就越大[8]。這類算法的缺點是僅僅考慮了網絡路徑的信息，忽略了節點近鄰的影響，且時間復雜度較高。（3）基于迭代優化的排序算法。其中，特征向量中心性EC（eigenvector centrality）[19]認為一個節點的重要性既取決于其鄰居節點的數量（即該節點的度），也取決于每個鄰居節點的重要性；PageRank[20]是網頁排序領域中的著名算法，它認為萬維網中一個頁面的重要性取決于指向它的其他頁面的數量和質量，如果一個頁面被很多高質量頁面指向，則這個頁面的質量也高[8]，其主要應用于有向網絡。（4）基于節點移除和收縮的排序算法。其中，節點刪除的生成樹法通過計算節點刪除后網絡的生成樹的減少比例來反映節點的重要性。這類算法研究節點移除或者收縮后網絡的結構與功能的變化，是一種動態的方法，缺點是計算復雜度較高，與上述3類方法相比，更像是一種對于重要節點排序算法的評價指標。

如果兩個社團之間僅通過一個節點連接，那么，雖然這個節點只有很小的度，但是卻具有極大的重要性，因為它具有很大的介數，隨著這樣的節點的移除，網絡的連通性將會急劇降低。在真實網絡中，很多的節點往往只與一個度很大的節點直接連接，當這個度大的節點處在網絡邊緣時，雖然它的介數會很小，但是它卻很重要，因為它具有很大的節點度，隨著這樣的節點的移除，網絡中將會產生很多孤立節點，網絡的最大連通分支的節點數目也會快速下降。當用度中心性DC來評價節點重要性時，不能很好地識別上述度小而介數大的重要節點；當用介數中心性BC來評價節點重要性時，對上述度大而介數小的重要節點的識別能力較弱；當用接近中心性CC來評價節點重要性時，由于和介數中心性BC一樣也是一種基于路徑的重要節點排序算法，同樣會忽略節點度對節點重要性的影響，甚至對于上述那種處在網絡邊緣的度大的節點，接近中心性CC認為它的重要性甚至不如去除后對網絡結構與功能幾乎沒有太大影響的處在網絡較中心位置的節點；當用特征向量中心性EC評價節點重要性時，由于其認為一個節點的重要性既取決于其鄰居節點的數量，也取決于每個鄰居節點的重要性，說明節點對其鄰居有很強的依賴性，當其鄰居從網絡中移除后，這種節點的后續移除往往對網絡的結構與功能不會有太大影響，因為它的重要性依賴于其鄰居的重要性，而當其鄰居節點移除后，它的重要性也會快速衰減。

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

1 重要節點排序算法

1.1 GM算法和LGM算法

GM算法和LGM算法用節點引力來描述節點的重要性，也就是影響力。其中，GM算法充分結合網絡中節點近鄰信息和節點間的路徑信息，在引力公式的啟發下，通過把網絡中節點的度看作物體質量，把節點間的最短路徑長度看作物體之間的距離，計算出各節點之間的引力，遍歷求和得到每個節點的總引力，對其從大到小排序得到一個重要節點排序結果。

定義1G i定義為網絡中節點i的引力，其計算公式為：

其中，k i代表節點i的度，d ij代表節點i和節點j之間的最短路徑長度，j遍歷網絡中i以外的所有其他節點。令節點自身之間的引力為0。

定義2為了降低GM算法的計算復雜度，通過只考慮截斷半徑r g以內的引力，提出了LGM算法，G r i定義為網絡節點i的局部引力，其計算公式為：

在14個數據集里，與經典算法相比，GM算法和LGM算法賦予給節點的重要性值（引力）序列與SIR模型中的對應節點的影響力序列之間的肯德爾等級相關系數τ取得了較大值，甚至在某些數據集里，LGM算法取得了最大的τ，體現了算法的優越性[21]。觀察公式（1）和（2），對于網絡中的節點i，如果它有較小的節點度k i，那么很難通過計算得到較大的引力Gi和局部引力G r i。由于引力和局部引力的計算公式中的分母都是平方項，節點與其低階鄰居之間具有較小的最短路徑長度，因此，G i和G r i的值主要由低階鄰居的節點度決定。節點引力（包含局部引力）的計算公式決定了GM算法和LGM算法對度小的重要節點識別能力較弱，并且節點的引力依賴于近鄰節點的度數，用網絡的魯棒性和脆弱性指標評價重要節點排序算法時，度大的節點和其近鄰節點往往具有較大的節點引力，當度大的節點從網絡中移除后，一般來說，其引力較大的近鄰節點的后續移除并不能在很大程度上影響網絡的結構與功能，說明算法在重要節點排序精度方面仍然存在提升之處。為進一步提升算法在網絡的魯棒性和脆弱性方面的表現，在彈簧模型的啟發下，提出SM算法和LSM算法。

1.2 SM算法和LSM算法

將以胡克定律[24]為基礎的彈簧模型引入到復雜網絡的重要節點排序領域，提出基于彈簧模型的重要節點排序算法SM和其局部算法LSM。

定義3在彈簧模型中，F定義為彈簧的彈力，其計算公式為：

公式（3）是彈簧模型的表達式。其中，F代表彈簧的彈力，k代表彈簧的勁度系數，x代表彈簧的形變量。考慮到彈簧的彈力隨著彈簧的勁度系數和形變量的增大而增大，類似地，復雜網絡中兩節點之間的影響力隨著節點鄰居數目（度數）的增大而增大，隨著節點間最短路徑長度的增大而減小，也就是說隨著網絡直徑d與網絡節點間最短路徑長度的差值的增大而增大，將網絡中的節點i和節點j以及它們之間的最短路徑看作一個原長為網絡直徑d的彈簧，基于彈簧模型，并受GM算法的引力計算公式的啟發，把節點i和節點j的度的乘積k i k j視作彈簧的勁度系數k，把網絡直徑d與兩節點間的最短路徑長度d ij的差值d-d ij視作彈簧的形變量，將兩節點之間的彈力視作彈簧的彈力F，并將其視為標量，只考慮大小，不考慮方向，即可計算得到網絡中各節點與其他所有節點間的總彈力，也就是各節點的重要性值。

定義4S ij定義為節點i和節點j之間的彈力，其計算公式為：

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

定義5Si定義為網絡中節點i的彈力，其計算公式為：

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

算法1 SM重要節點排序算法

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

下面分析算法的時間復雜度。對于給定的復雜網絡G，網絡包含n個節點和m條邊，SM算法的時間耗費主要在于計算所有節點對之間的最短路徑長度，通過Johnson算法[25]計算全源最短路徑的時間復雜度為O(n2lbn+nm)，因此SM算法的時間復雜度為O(n2lbn+nm)。

定義6通過只考慮截斷半徑r s以內的彈力，提出LSM算法以降低SM算法的計算復雜度，S ri定義為網絡節點i的局部彈力，其計算公式為：將算法1中的第4步改為通過公式（6）計算節點i的局部彈力S ri，即可得到LSM算法的偽碼描述。同樣的，LSM算法的時間復雜度也是O(n2lbn+nm)。表1顯示了基于彈簧模型的重要節點排序算法SM和其局部算法LSM、基于引力模型的重要節點排序算法GM和其局部算法LGM、度中心性DC、介數中心性BC這6種算法的時間復雜度。可以看到除度中心性DC外的其他5種算法具有相同的時間復雜度，均為O(n2lbn+nm)。

表1 6種算法的時間復雜度Table 1 Time complexity of six algorithms

GM算法和LGM算法的計算公式決定了度大的節點和其鄰居節點會具有較大的重要性值（引力值），觀察公式（5）和公式（6），由于節點彈力的計算公式中k i、k j和d-d ij是一次項相乘的形式（對于選定網絡，網絡直徑d為定值），與GM算法和LGM算法的節點引力的計算公式相比，增強了最短路徑對節點重要性的影響，也就是提高了介數對于節點重要性的作用。介數大的節點有更多的最短路徑通過，從概率上來看，這類節點往往與網絡中的其他節點有更小的最短路徑長度，因此它會有較大的節點彈力。對于一些度小而介數大的節點，其彈力值仍然可能很大，在這點上，SM算法和LSM算法與GM和LGM算法有很大的不同。基于節點近鄰的算法（如度中心性DC）只需知道網絡中節點的鄰居信息；基于路徑信息的算法（如介數中心性BC）只需知道節點間的路徑信息；基于引力模型的GM算法和LGM算法雖然考慮了節點的近鄰信息和路徑信息，但以網絡對于節點移除的魯棒性和脆弱性指標評價排序算法時，由于節點重要性過于依賴鄰居節點的重要性，以至在重要節點排序精度方面仍然存在提升之處；基于彈簧模型的SM算法和LSM算法充分結合網絡中節點近鄰信息、路徑信息以及網絡統計特征中的直徑信息，對網絡的整體拓撲結構信息有充分把握，并增強了最短路徑對節點重要性的影響，即削弱了節點對其鄰居節點的重要性的影響，當度大的節點從網絡中移除后，對其鄰居節點的重要性不會有太大影響，也就是說不會在很大程度上削弱鄰居節點移除對網絡結構和功能的影響，維持了原網絡重要節點排序的精度，表明SM算法和LSM算法能夠對網絡中的重要節點進行更準確的排序。

2 實驗分析

2.1 數據集描述

為了客觀評價算法的有效性和適用性，選取了2種經典的合成網絡和4個公開的不同規模的真實網絡數據集。BA無標度網絡和WS小世界網絡是復雜網絡中最重要的2個網絡模型，本文基于BA無標度網絡模型和WS小世界網絡模型構建了2種10 000個節點的人工合成網絡：BA無標度網絡（BA）和WS小世界網絡（WS），并選取了4種真實網絡：遺傳疾病網絡（Diseasome）[26]、蛋白質相互作用網絡（Y2H）[27]、美國西部電力網絡（Power）[28]、性社交網絡（Sex）[29]，其網絡參數如表2所示。

表2 6種無向網絡的參數Table 2 Parameters of six undirected networks

2.2 網絡的魯棒性和脆弱性驗證實驗

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

定義7R定義為網絡對于節點移除的魯棒性（robustness）[8]：

定義8V定義為網絡對于節點移除的脆弱性（vulnerability）[8]：

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

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

圖1 經典算法在6種網絡上的魯棒性和脆弱性實驗Fig.1 Experiments on robustness and vulnerability of classical algorithms on six networks

LSM算法和LGM算法存在最優截斷半徑（使LSM算法和LGM算法具有最大V值的最小截斷半徑）的選取問題。為了得到LSM算法和LGM算法在較小計算復雜度下的最優截斷半徑和，只考慮截斷半徑為10以內的情況，由于BA網絡直徑為9，所以其只考慮到9以內的截斷半徑，以截斷半徑r為橫坐標，以V值為縱坐標，在6個數據集上對比LSM算法和LGM算法在不同截斷半徑r下的V值，作出V值隨r增大而變化的折線圖V-r，實驗圖如圖2所示。設LSM和LGM的最優截斷半徑分別為和。對于BA網絡，如圖2（a）所示，6；對于圖2（b）、圖2（d）和圖2（e）中的WS網絡、Y2H網絡和Power網絡，10；對于Diseasome網絡，如圖2（c）所示，10，7；對于Sex網絡，如圖2（f）所示，7。在6種網絡中，LSM在取得的V值均大于LGM在取得的V值，說明LSM算法在網絡的魯棒性和脆弱性上較LGM算法具有一定優勢。為了使局部算法LSM和LGM具有更強的適用性，最優截斷半徑可以取成一個定值。當r s=r g=10時，實驗結果顯示LSM算法和LGM算法在除BA網絡外的其他5種網絡中的V值均可以取到最大值。對于BA網絡這樣的直徑小于10的網絡，把最優截斷半徑取成網絡直徑，此時，LSM算法和SM算法、LGM和GM算法完全等價。可以看到，在6種網絡中，以上述這種方式選取最優截斷半徑時，LSM算法和LGM算法可以取得最大的V值，并且，LSM算法的V值總比LGM算法的V值大，體現了以網絡魯棒性和脆弱性指標評價排序算法時，LSM算法相較于LGM算法的優越性。

圖2 LSM和LGM關于6種網絡的V-r圖Fig.2 V-r graphs of LSM and LGM on six networks

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

圖3 SM和LSM在6種網絡上的魯棒性和脆弱性驗證實驗Fig.3 Experiments on robustness and vulnerability of SM and LSM on six networks

2.3 SIR傳播模型驗證實驗

此類方法著重考察網絡中節點對于信息的傳播能力或者是病毒在網絡中的擴散能力。SIR模型中，一個節點的傳播能力被定義為該節點的平均傳播范圍，如果一個排序算法的結果使得網絡流傳播又快又廣，則說明該重要節點排序算法優于其他算法[8]。

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

圖4 SM和LSM在Power網絡上的SIR傳播模型驗證實驗（感染率β=0.15，恢復率λ=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 結束語

本文主要工作是在GM算法和LGM算法的啟發下，在彈簧模型的基礎上，借助胡克定律，進一步考慮網絡中節點近鄰信息和路徑信息，并結合網絡直徑，提出了重要節點排序算法SM和其局部算法LSM。在2種合成網絡和4種真實網絡的基于網絡的魯棒性和脆弱性實驗，驗證了SM算法和LSM算法對于網絡中重要節點排序具有更高的準確性。特別地，在SIR傳播模型下，在Power網絡上的實驗結果證實SM算法得到的排名靠前的重要節點作為一個感染節點集合，與其他算法得到的感染集相比，有更快的傳播速度，達到穩態時，有更大的傳播范圍。SM算法和LSM算法依賴于網絡的連通性，后續工作需要針對不連通的網絡，考慮對此網絡的重要節點排序算法，對其重要節點進行更科學全面的排序。