節(jié)點(diǎn)重要度在復(fù)雜網(wǎng)絡(luò)魯棒性中的應(yīng)用

莫泓銘

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

?

節(jié)點(diǎn)重要度在復(fù)雜網(wǎng)絡(luò)魯棒性中的應(yīng)用

莫泓銘

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

[摘要]如何評價(jià)網(wǎng)絡(luò)的魯棒性一直是當(dāng)前的一個(gè)研究熱點(diǎn)。識別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)從而梳理網(wǎng)絡(luò)的體系結(jié)構(gòu)有助于提高網(wǎng)絡(luò)的可控性。近年來，有關(guān)識別復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)的研究取得了一定的進(jìn)展?；诖?，本文提出了一種復(fù)雜網(wǎng)絡(luò)中識別重要節(jié)點(diǎn)的方法來驗(yàn)證網(wǎng)絡(luò)的魯棒性。實(shí)例驗(yàn)證表明越重要的節(jié)點(diǎn)對網(wǎng)絡(luò)魯棒性的影響越大。

[關(guān)鍵詞]復(fù)雜網(wǎng)絡(luò)；重要節(jié)點(diǎn)；魯棒性；脆弱性

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

1基礎(chǔ)知識

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

1.1復(fù)雜網(wǎng)絡(luò)的基本特性[3-4]

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

1.2識別復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)的算法

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

2網(wǎng)絡(luò)的魯棒性指標(biāo)

網(wǎng)絡(luò)的魯棒性是指網(wǎng)絡(luò)中的一個(gè)或多個(gè)部件遭到破壞時(shí)，網(wǎng)絡(luò)維持其基本性能的能力。網(wǎng)絡(luò)的脆弱性是指當(dāng)網(wǎng)絡(luò)的結(jié)構(gòu)遭遇變化時(shí)，其所遭受的破壞能力，即系統(tǒng)崩潰的可能性。魯棒性與脆弱性分別從穩(wěn)定指標(biāo)與失效指標(biāo)的角度來表征網(wǎng)絡(luò)的特性，兩者相輔相成。網(wǎng)絡(luò)的魯棒性越大，則其脆弱性就越小，即抗毀能力越強(qiáng)。網(wǎng)絡(luò)的魯棒性越小，則其脆弱性越大，即其抗毀能力越弱。下面介紹兩種常用的魯棒性指標(biāo)：

2.1最大連通度Gmax

2.2連通因子?

網(wǎng)絡(luò)的魯棒性或脆弱性都是從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的視角來檢驗(yàn)網(wǎng)絡(luò)的抗毀能力。識別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)有助于梳理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，提高對網(wǎng)絡(luò)的整體把握能力。因而識別網(wǎng)絡(luò)中的重要結(jié)點(diǎn)并加以重點(diǎn)維護(hù)或保護(hù)，有助于提高網(wǎng)絡(luò)的魯棒性。

3實(shí)例應(yīng)用

以圖1所示的網(wǎng)絡(luò)為例，該網(wǎng)絡(luò)由12個(gè)結(jié)點(diǎn)構(gòu)成，其中節(jié)點(diǎn)最大的度為4，平均度為1.8333。通過計(jì)算得知，節(jié)點(diǎn)的度中心DC、介數(shù)中心BC、緊密度中心CC及將DC、BC和CC運(yùn)用證據(jù)理論融合后得到的新指標(biāo)DBC[16]值，如表1中第2～4列所示。

圖1　示例網(wǎng)絡(luò)

節(jié)點(diǎn)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可知，節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3和節(jié)點(diǎn)4是上述算法的指標(biāo)值最高的4個(gè)節(jié)點(diǎn)。然而，在DC算法中，節(jié)點(diǎn)1、節(jié)點(diǎn)3和節(jié)點(diǎn)4有相同的值因而被認(rèn)定為同等重要。BC、CC和DBC算法中節(jié)點(diǎn)3的值最大，因而節(jié)點(diǎn)3被判定為最重要的節(jié)點(diǎn)。

當(dāng)移除網(wǎng)絡(luò)中的某個(gè)節(jié)點(diǎn)后，網(wǎng)絡(luò)的最大連通度及連通因子值變化如表1中第6～7列及圖2所示。

圖2　節(jié)點(diǎn)的最大連通度Gmax與連通因子?

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

4結(jié)論

在大數(shù)據(jù)背景下，網(wǎng)絡(luò)體系越來越龐大，內(nèi)部結(jié)構(gòu)越來越復(fù)雜，網(wǎng)絡(luò)的可靠性越來越受到人們的關(guān)注。實(shí)例驗(yàn)證表明，通過識別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)來探尋網(wǎng)絡(luò)的魯棒性是可行的。識別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，并對其加強(qiáng)維護(hù)或保護(hù)，有利于提升網(wǎng)絡(luò)的抗風(fēng)險(xiǎn)能力，提高網(wǎng)絡(luò)的可靠性。從融合節(jié)點(diǎn)的多重屬性的角度來挖掘網(wǎng)絡(luò)中的重要節(jié)點(diǎn)來驗(yàn)證網(wǎng)絡(luò)的魯棒性是下一步的研究方向。

[參考文獻(xiàn)]

[1]彭志蓮.智能農(nóng)業(yè)中物聯(lián)網(wǎng)技術(shù)的應(yīng)用分析[J].長春師范學(xué)院學(xué)報(bào):自然科學(xué)版,2014,33(1):59-60.

[2]于昊.MSTP在遼寧電力傳輸網(wǎng)中的應(yīng)用[J].長春師范學(xué)院學(xué)報(bào):自然科學(xué)版,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]羅筱如.基于復(fù)雜網(wǎng)絡(luò)理論的電力網(wǎng)絡(luò)魯棒性及脆弱性分析[D].成都:西南交通大學(xué),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- )，男，助理研究員，西南大學(xué)碩士研究生，從事不確定信息處理、復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要度研究。

[基金項(xiàng)目]四川省教育廳理工科一般科研項(xiàng)目“基于復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度識別理論的網(wǎng)絡(luò)魯棒性研究”(14ZB0322)；國家民委自籌科研項(xiàng)目“基于證據(jù)理論的決策方法及其在民族地區(qū)生態(tài)環(huán)境治理決策中的應(yīng)用”(14SCZ014)。

[收稿日期]2015-12-21

[中圖分類號]TP391.9

[文獻(xiàn)標(biāo)識碼]A

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