節點重要度在復雜網絡魯棒性中的應用

莫泓銘

(四川民族學院，四川康定 626001)

?

節點重要度在復雜網絡魯棒性中的應用

莫泓銘

(四川民族學院，四川康定 626001)

[摘要]如何評價網絡的魯棒性一直是當前的一個研究熱點。識別網絡中的重要節點從而梳理網絡的體系結構有助于提高網絡的可控性。近年來，有關識別復雜網絡中重要節點的研究取得了一定的進展。基于此，本文提出了一種復雜網絡中識別重要節點的方法來驗證網絡的魯棒性。實例驗證表明越重要的節點對網絡魯棒性的影響越大。

[關鍵詞]復雜網絡；重要節點；魯棒性；脆弱性

隨著大數據時代的到來，生活中的各種系統都可以被抽象為網絡。我們的生活被各種各樣的網絡包圍著，常見的如通信網絡、在線社交網絡、電力網絡、交通網絡、物聯網等，在學術上它們都可以被視為復雜網絡[1-4]。由于這些系統越來越龐大，結構越來越復雜，與人們的生活聯系得越來越緊密，一旦其系統失效，將會對我們的生產、生活和經濟發展帶來不可估量的后果。復雜網絡具自組織、自相似、吸引子、小世界、無標度中部分或全部性質[3-4]。近年來，復雜網絡的可靠性與抗毀能力越來越受到廣大學者的關注[5-7]。魯棒性是用來表征控制系統對特性或參數攝動的不敏感性。在實際應用中，系統或網絡面臨的各種各樣的主觀或客觀的干擾是不可避免的。近年來，對復雜網絡魯棒性的研究大多集中在網絡中的邊與節點。本文主要從復雜網絡中節點重要度的視角來探討復雜網絡的魯棒性。

1基礎知識

自然界中存在的許多復雜系統都可以通過各種各樣的網絡加以描述。一個典型的網絡可由許多的節點和節點之間邊的關系構成。假如一個網絡G=(V，E)是由|V|=n個節點和|E|=m條邊組成[8]。vij=1表示節點i和節點j之間有一條連邊，vij=0代表節點i和節點j不相連。

1.1復雜網絡的基本特性[3-4]

復雜網絡具有自組織、自相似、吸引子、小世界、無標度等特性，相對于一般意義上的網絡而言，其“復雜”主要體現：(1)結構復雜。節點數目眾多，網絡結構特征呈現多樣性與復雜性；(2)節點間關系錯綜復雜，對于加權網絡，節點間的權重各異；對于有向網絡且節點間的連邊存在方向性；(3)對于時域或空域網絡，節點的狀態隨時間或空間的變化而變化；(4)多重屬性的融合。復雜網絡中的節點、邊、結構都具有多重的關系，因而很難簡單地概括、掌握其結構。

1.2識別復雜網絡中重要節點的算法

通過以上這些算法或指標可以單一地衡量節點某一個方面的能力，每種單一的算法都有其側重點及局限性。基于此，學者們提出了一些多屬性指標的綜合計算方法，例如：Du[11]等綜合考慮了節點的DC、BC和CC等指標，然后運用TOPSIS(technique for order performance by similarity to ideal solution)法來為每個節點確定了一個的綜合指標，從而按最優解排序，據此得到節點的重要性排序結果。Wei[12-13]等利用證據理論[14-15]的思想將加權網絡中節點的DC、BC和CC等指標視作BPAs(basic probability assignments)，結合證據理論的組合規則將這些BPAs進行融合，得到一個節點的綜合BPA值，最終對節點的影響力進行排序。Mo[16]等基于證據理論的思想提出了一種在無權網絡中融合節點的DC、BC和CC等指標的算法。度僅僅考慮的是節點的最相鄰的鄰居情況，認為度相同的節點則其同等重要，然而近來的一些研究表明，節點所處的位置也是非常重要的，即使一些處在核心位置的關鍵節點，雖然度很小，但它們卻非常重要，而一些處在網絡邊緣的節點度很大，但影響力卻很小。基于此，Kitsak[17]等提出了K-核分解法(K-shell decomposition)，通過網絡分層的方法來確定節點的重要性。K-核分解法在分析大規模網絡的層級結構等方面有很多應用，然而也存在一定的局限性，有很多后續的改進、改良K-殼分解法的研究工作[18]。此外，還有PageRank 算法[19]、LeaderRank算法[20]和HITS算法[21]等。

2網絡的魯棒性指標

網絡的魯棒性是指網絡中的一個或多個部件遭到破壞時，網絡維持其基本性能的能力。網絡的脆弱性是指當網絡的結構遭遇變化時，其所遭受的破壞能力，即系統崩潰的可能性。魯棒性與脆弱性分別從穩定指標與失效指標的角度來表征網絡的特性，兩者相輔相成。網絡的魯棒性越大，則其脆弱性就越小，即抗毀能力越強。網絡的魯棒性越小，則其脆弱性越大，即其抗毀能力越弱。下面介紹兩種常用的魯棒性指標：

2.1最大連通度Gmax

2.2連通因子?

網絡的魯棒性或脆弱性都是從網絡的拓撲結構的視角來檢驗網絡的抗毀能力。識別網絡中的重要節點有助于梳理網絡的拓撲結構，提高對網絡的整體把握能力。因而識別網絡中的重要結點并加以重點維護或保護，有助于提高網絡的魯棒性。

3實例應用

以圖1所示的網絡為例，該網絡由12個結點構成，其中節點最大的度為4，平均度為1.8333。通過計算得知，節點的度中心DC、介數中心BC、緊密度中心CC及將DC、BC和CC運用證據理論融合后得到的新指標DBC[16]值，如表1中第2～4列所示。

圖1　示例網絡

節點IDDCBCCCDBCGmax10.33330.49090.40740.79781.00000.250020.16670.50910.47830.30370.63640.500030.33330.70910.52380.99740.55560.250040.33330.49090.44000.80831.00000.250050.083300.2973-0.99741.00000.500060.083300.2973-0.99741.00000.500070.083300.2973-0.99741.00000.500080.083300.3548-0.99701.00000.500090.083300.3548-0.99701.00000.5000100.083300.3143-0.99731.00000.5000110.083300.3143-0.99731.00000.5000120.083300.3143-0.99731.00000.5000

從表1可知，節點1、節點2、節點3和節點4是上述算法的指標值最高的4個節點。然而，在DC算法中，節點1、節點3和節點4有相同的值因而被認定為同等重要。BC、CC和DBC算法中節點3的值最大，因而節點3被判定為最重要的節點。

當移除網絡中的某個節點后，網絡的最大連通度及連通因子值變化如表1中第6～7列及圖2所示。

圖2　節點的最大連通度Gmax與連通因子?

對于該網絡，從表1及圖2可知，當移除節點3后，網絡的Gmax與連通因子值?都達到最小值。結合上述的不同的節點重要度算法可知，節點3為該網絡的最重要節點。即當節點3失效后，網絡最脆弱，網絡的魯棒性最差。反之，移除一些末梢節點(如節點5、節點12等)后，網絡的最大連通度及連通因子都維持在一個較高的值，網絡的魯棒性較好。

4結論

在大數據背景下，網絡體系越來越龐大，內部結構越來越復雜，網絡的可靠性越來越受到人們的關注。實例驗證表明，通過識別網絡中的重要節點來探尋網絡的魯棒性是可行的。識別網絡中的重要節點，并對其加強維護或保護，有利于提升網絡的抗風險能力，提高網絡的可靠性。從融合節點的多重屬性的角度來挖掘網絡中的重要節點來驗證網絡的魯棒性是下一步的研究方向。

[參考文獻]

[1]彭志蓮.智能農業中物聯網技術的應用分析[J].長春師范學院學報:自然科學版,2014,33(1):59-60.

[2]于昊.MSTP在遼寧電力傳輸網中的應用[J].長春師范學院學報:自然科學版,2014,33(6):50-51.

[3]Strogatz S H.Exploring complex networks[J].Nature,2001,410(6825):268-276.

[4]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[5]Callaway D S,Newman M E J, Strogatz S H, et al.Network robustness and fragility: Percolation on random graphs[J]. Physical review letters,2000,85(25):5468.

[6]Min B,Do Yi S,Lee K M,et al.Network robustness of multiplex networks with interlayer degree correlations[J]. Physical Review E,2014,89(4):042811.

[7]Beygelzimer A,Grinstein G,Linsker R,et al.Improving network robustness by edge modification[J].Physica A: Statistical Mechanics and its Applications,2005,357(3):593-612.

[8]Freeman L C.Centrality in social networks conceptual clarification [J].Social networks,1979,1(3):215-239.

[9]Albert R,Jeong H,Barabási A L.Internet:Diameter of the world-wide web[J].Nature,1999,401(6749):130-131.

[10]Freeman L C.A set of measures of centrality based on betweenness[J].Sociometry,1977:35-41.

[11]Du Y,Gao C, Hu Y,et al.A new method of identifying influential nodes in complex networks based on TOPSIS[J]. Physica A:Statistical Mechanics and its Applications,2014,399:57-69.

[12]Wei D,Deng X,Zhang X,et al.Identifying influential nodes in weighted networks based on evidence theory[J]. Physica A:Statistical Mechanics and its Applications,2013,392(10):2564-2575.

[13]Gao C,Wei D,Hu Y,et al.A modified evidential methodology of identifying influential nodes in weighted networks[J].Physica A:Statistical Mechanics and its Applications,2013,392(21):5490-5500.

[14]Dempster A P.Upper and lower probabilities induced by a multivalued mapping[J].The annals of mathematical statistics,1967:325-339.

[15]Shafer G.A mathematical theory of evidence[M].Princeton:Princeton university press,1976.

[16]Mo H,Gao C,Deng Y.Evidential method to identify influential nodes in complex networks[J].Journal of Systems Engineering and Electronics,2015,26(2):381-387.

[17]Kitsak M,Gallos L K,Havlin S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888-893.

[18]Wei B Liu J,Wei D,et al.Weighted k-shell decomposition for complex networks based on potential edge weights [J].Physica A:Statistical Mechanics and its Applications,2015,420:277-283.

[19]Page L,Brin S,Motwani R,et al.The pagerank citation ranking: Bringing order to the web[C].Brisbane, Australia,In Proceedings of the 7th International World Wide Web Conference,1998:161-172.

[20]Lü L,Zhang Y C,Yeung C H,et al.Leaders in social networks, the delicious case[J].PloS one,2011,6(6):e21202.

[21]Kleinberg J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM,1999,46(5):604-632.

[22]羅筱如.基于復雜網絡理論的電力網絡魯棒性及脆弱性分析[D].成都:西南交通大學,2012.

An Application of the Nodes Importance in Network Robustness

MO Hong-ming

(Sichuan Minzu College, Kangding Sichuan 626001, China)

Abstract:How to evaluate network robustness is still a hot issue. Identifying the influential nodes and classifying the structure of networks will help to enhance the controllability of networks. In recent years, some progress has been made in the research of identifying the influential nodes. This paper, thereafter, proposes a new method to confirm the robustness of network on the basis of influential nodes in complex networks. The experiments have proved that the more influential the nodes are, the more influence they will have on robustness.

Key words:complex network; influential nodes; robustness; vulnerability

[作者簡介]莫泓銘(1983- )，男，助理研究員，西南大學碩士研究生，從事不確定信息處理、復雜網絡的節點重要度研究。

[基金項目]四川省教育廳理工科一般科研項目“基于復雜網絡節點重要度識別理論的網絡魯棒性研究”(14ZB0322)；國家民委自籌科研項目“基于證據理論的決策方法及其在民族地區生態環境治理決策中的應用”(14SCZ014)。

[收稿日期]2015-12-21

[中圖分類號]TP391.9

[文獻標識碼]A

[文章編號]2095-7602(2016)02-0022-04