一種新的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度分析方法

張廷萍

（重慶交通大學(xué)　信息科學(xué)與工程學(xué)院，重慶　400074）

一種新的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度分析方法

張廷萍

（重慶交通大學(xué)信息科學(xué)與工程學(xué)院，重慶400074）

網(wǎng)絡(luò)節(jié)點重要度分析即識別有影響力的節(jié)點，是研究和分析復(fù)雜網(wǎng)絡(luò)的一種非常重要的方法.目前比較常用的是利用中心性方法解決這個問題，然而，使用不同的中心性方法，可以得到不同的結(jié)果.本文提出了一種新的折衷中心性方法來分析網(wǎng)絡(luò)節(jié)點重要度.利用計算度中心性、接近中心性和介數(shù)中心性的值，再進行歐氏距離計算，得到折衷中心性值.最后通過實例分析證明該方法是一種有效的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度分析方法.

復(fù)雜網(wǎng)絡(luò)；重要節(jié)點；中心性方法

引言

隨著小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的提出，復(fù)雜網(wǎng)絡(luò)受到越來越多的重視.在為人類生產(chǎn)生活帶來極大便利的同時，復(fù)雜網(wǎng)絡(luò)也產(chǎn)生了不可忽視的負面沖擊，如微博謠言的傳播及電力網(wǎng)絡(luò)癱瘓引起的大面積停電等.因此，對復(fù)雜網(wǎng)絡(luò)進行深入的研究和分析以方便對其負面影響進行預(yù)測、避免和控制是刻不容緩的.其中，節(jié)點重要度分析是一個非常重要的方向.目前，多種復(fù)雜網(wǎng)絡(luò)節(jié)點中心性如度中心性、介數(shù)中心性、接近中心性、特征向量中心性以及流介數(shù)中心性等被提出來以解決節(jié)點重要度分析問題，但是大多數(shù)方法只用單一中心性來確定有節(jié)點的影響力和重要度，而且使用不同的中心性方法得到了不同的結(jié)果.因此，本文提出了一種折衷中心性方法，利用使用不同中心性方法計算的結(jié)果，再進行變化計算，得到折衷中心性結(jié)果，進行網(wǎng)絡(luò)節(jié)點重要度分析，并進行實例數(shù)值計算和模型分型.

1　基本理論

復(fù)雜網(wǎng)絡(luò)是由數(shù)量巨大的節(jié)點和節(jié)點之間錯綜復(fù)雜的關(guān)系共同構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)，在數(shù)學(xué)上可以抽象為一個由點集V和邊集E組成的圖G=(V,E).如圖1所示，是具有9個節(jié)點的簡單無向無權(quán)網(wǎng)絡(luò)圖.為簡化問題，本文僅針對無向無權(quán)網(wǎng)絡(luò)進行研究.

圖1　有11個節(jié)點的簡單無向網(wǎng)絡(luò)圖

定義1度中心性（Degreecentralitymeasure）

節(jié)點i的度中心性是在網(wǎng)絡(luò)分析中刻畫節(jié)點中心性的最直接度量指標(biāo)，用CD(i)表示，定義為：

其中i為當(dāng)前所求節(jié)點，j表示其他所有的節(jié)點，是網(wǎng)絡(luò)節(jié)點總數(shù)，表示i與j之間有連接關(guān)系.兩個節(jié)點之間相連，則為1，反之則為0.

定義2接近中心性（Closenesscentralitymeasure）

節(jié)點i的接近中心性是刻畫節(jié)點通過網(wǎng)絡(luò)到達其它節(jié)點難易程度的指標(biāo)，用CC(i)表示，定義為：

其中dij表示節(jié)點i和節(jié)點j之間的距離，其定義如下：

定義3介數(shù)中心性（Betweennesscentralitymeasure）

節(jié)點i的介數(shù)中心性，用CB(i)表示，定義為：

2　節(jié)點重要度評估新算法

定義4折衷中心性（Compromisecentralitymeasure）

盡管已提出多種中心性方法進行節(jié)點重要度評估，但是每一種方法都只從一個中心性角度考慮，導(dǎo)致使用不同的中心性方法得到的評估結(jié)果不一致.因此，本文提出了將度中心性、接近中心性和介數(shù)中心性的評估結(jié)果進行折衷處理的節(jié)點重要度評估新算法即折衷中心性.下面給出折衷中心性算法的具體步驟：

1）利用公式（1）、（2）和（4），分別計算復(fù)雜網(wǎng)絡(luò)所有節(jié)點的度中心性、接近中心性和介數(shù)中心性的值，即得到CD，CC和CB.

2）根據(jù)定義5，分別得到復(fù)雜網(wǎng)絡(luò)每個節(jié)點的度中心性、接近中心性和介數(shù)中心性的歸一化值，即得到C~D(i)，C~C(i)和C~B(i).

定義5設(shè)CD(i)，CC(i)和CB(i)分別為節(jié)點i的度中心性、接近中心性和介數(shù)中心性的值，歸一化中心計算方法為：

其中C~i表示節(jié)點i的歸一化中心值，N為復(fù)雜網(wǎng)絡(luò)節(jié)點數(shù).

3）根據(jù)定義6，整合節(jié)點i的歸一化中心值，得到CED(i).

定義6設(shè)C~D(i),C~C(i)和C~B(i)分別為節(jié)點i的度中心性、接近中心性和介數(shù)中心性歸一化中心值.利用歐拉公式得到的折衷中心性的值定義為：

其中n為網(wǎng)絡(luò)節(jié)點的數(shù)目.

4）利用計算所得的值，對復(fù)雜網(wǎng)絡(luò)節(jié)點進行排序，值越高，則節(jié)點越重要.

3　算例

圖1為有11個節(jié)點，9條邊的無向無權(quán)網(wǎng)絡(luò).首先利用公式（1）、（2）、（4）和（5），分別計算該復(fù)雜網(wǎng)絡(luò)所有節(jié)點的度中心性、接近中心性和介數(shù)中心性的值及歸一化值，如表1所示.

表1　圖1所有節(jié)點的度中心性、接近中心性和介數(shù)中心性的值及歸一化值

根據(jù)公式6，計算節(jié)點1的折衷中心性值如下：

同理，利用上述方法計算其他節(jié)點的折衷中心性值，并按值進行排序，如表2所示：

表2　本文所提算法計算的折衷中心性值

由表2可見，圖1的節(jié)點重要度依次為7>6>4>5>1>8、9、11>2、3，有效識別了復(fù)雜網(wǎng)絡(luò)節(jié)點的重要度.

4　結(jié)論

本文提出了一種新的折衷中心性方法來是來分析網(wǎng)絡(luò)節(jié)點重要度.通過計算度中心性、接近中心性和介數(shù)中心性的值，再進行歐氏距離計算，得到折衷中心性值.通過實例分析證明該方法是一種有效的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度分析方法.

〔1〕張寧，蘇樹清.個人微博用戶網(wǎng)絡(luò)的節(jié)點中心性研究［J］.上海理工大學(xué)學(xué)報，2015，37（1）：43-48.

〔2〕苑衛(wèi)國，劉云，程軍軍，等.微博雙向“關(guān)注”網(wǎng)絡(luò)節(jié)點中心性及傳播影響力的分析［J］.物理學(xué)報，2013，62（3）：91-95.

〔3〕D.Wei，X.Deng，X.Zhang，Y.Deng，andS.Mahadevan，Identifyinginfluentialnodesinweightednetworksbasedonevidencetheory，PhysicaA：Statistical MechanicsanditsApplications，vol.392，no.10，pp.2564 –2575，2013.

〔4〕M.Karsai，M.Kivel？，R.K.Pan，K.Kaski，J.Kertész，A.L.Barabási，andJ.Saram？ki，Smallbutslowworld：Hownetworktopologyandburstinessslowdown spreading，PhysicalReviewE，vol.83，no.2，pp.025102，2011.

〔5〕BarthelemyM.Betweennesscentralityinlargecomplex networks［J］.TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems，2004，38（2）：163-168.

〔6〕汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論［M］.北京：高等教育出版社，2012.

O233

A

1673-260X（2016）08-0001-02

2016-05-05

重慶市教委科學(xué)技術(shù)研究項目（KJ1500515）