摘 要：k-核分解算法是一種優(yōu)秀的評估復(fù)雜網(wǎng)絡(luò)節(jié)點重要性的方法，然而該方法對于復(fù)雜網(wǎng)絡(luò)節(jié)點的排序還存在一些問題。本文提出了一種改進的加權(quán)k-核分解算法，通過改進節(jié)點加權(quán)度的計算對已提出的方法進行改進。然后在四個真實網(wǎng)絡(luò)上利用SIR傳染病模型進行了實驗仿真。實驗結(jié)果表明，改進后的算法比原有方法在評估節(jié)點重要性方面更具有優(yōu)越性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；節(jié)點重要度；k-核分解；SIR

中圖分類號：TP393.0 文獻標識碼：A

1 引言（Introduction）

復(fù)雜網(wǎng)絡(luò)是一門多學科交叉的領(lǐng)域，研究網(wǎng)絡(luò)節(jié)點重要度在很多領(lǐng)域都具有重要的理論意義和實際意義。經(jīng)典的評估節(jié)點重要度的指標有度中心性、介數(shù)中心性、近鄰中心性等[1-3]。最近幾年有一些研究學者陸續(xù)提出了一些新的評估方法，比如PageRank、LeaderRank、半局部中心性、k-核分解等[4]。k-核分解由Kitsak在2010年提出，Kitsak認為節(jié)點的重要度不是由節(jié)點度來決定的，也不是由介數(shù)決定的，而是由k-核（k-shell）決定的[5]。文獻[5]的實驗表明，k-核分解比度中心性和介數(shù)中心性更能有效地評估節(jié)點重要度。k-核分解的優(yōu)越性逐漸被人們認識，然而該方法也存在一定的缺陷，研究學者們相繼對其進行改進。文獻[6]中提出了一種新的加權(quán)k-核分解算法，該算法改進了節(jié)點度的計算，很大程度上有效地解決了k-核分解單調(diào)性的問題。本文基于文獻[6]進行改進，改進后的算法一定程度上優(yōu)越于魏等人的方法。

2 理論方法（Theory and method）

2.1 k-核分解算法

k-核分解是一個層層推進的過程，好像剝洋蔥。第一步，去掉度為1的節(jié)點，剩下一個子圖，如果該子圖中依然有度為1的點則繼續(xù)刪除這些點，直到最后剩下一個不含度為1的節(jié)點的子圖。那些被刪除的節(jié)點則屬于ks=1的核。第二步，跟第一步類似，刪除子圖中度為2的節(jié)點，最后得到一個子圖，中所有點的度均大于2。以此類推，直到所有的點都被分解到某個核中[5]。圖1為k-核分解的示意圖。

圖1 k-核分解示例

Fig.1 An example of k-shell decomposition

2.2 加權(quán)k-核分解

魏等人于2015年提出了一種新的加權(quán)k-核分解[6]。在文獻[6]中，魏等人改進了k-核分解中加權(quán)度的計算，計算方法如下：

（1）

（2）

（3）

其中，表示節(jié)點i與節(jié)點j是連接的；反之，則表示節(jié)點i與節(jié)點j是斷開的。表示節(jié)點i的度。表示節(jié)點i與節(jié)點j之間鏈接邊的權(quán)重。表示節(jié)點i的加權(quán)度。魏的方法在計算每個節(jié)點的加權(quán)度之后，將加權(quán)度進行向上取整，然后按照經(jīng)典k-核分解對網(wǎng)絡(luò)進行分解。文獻[7]中的實驗表明該方法能有效解決經(jīng)典k-核分解中單調(diào)性等問題。

2.3 改進的加權(quán)k-核分解

本文提出了一種改進的加權(quán)k-核分解算法，該算法主要改進了文獻[6]中對加權(quán)度的計算。改進的加權(quán)度計算方法如下：

（4）

其中，α為調(diào)節(jié)因子，其取值范圍為[0，1]。當α=1時，則變?yōu)榻?jīng)典k-核分解；當α=0時，則節(jié)點完全依賴鄰居節(jié)點的重要性。計算加權(quán)度后，若加權(quán)度不為整數(shù)則向上取整。然后按照經(jīng)典k-核分解對網(wǎng)絡(luò)進行分解。

3 實驗結(jié)果與分析（Experiment result and analysis）

為探究改進算法的有效性和可行性，我們在四個真實網(wǎng)絡(luò)上進行了SIR傳染病模擬實驗[7]。這四個真實網(wǎng)絡(luò)分別是Blogs、Email、Netscience和USAir[8-10]。我們分別將改進的方法所排序的前30個節(jié)點和魏的方法排序得出的前30個節(jié)點進行SIR傳播實驗。實驗結(jié)果如圖2和表1所示。圖2中紅色虛線表示改進方法中感染（Infected）節(jié)點的數(shù)目，紅色實線表示改進方法中恢復(fù)（Recovered）節(jié)點的數(shù)目，藍色虛線表示魏的方法中感染（Infected）節(jié)點的數(shù)目，藍色實線表示魏的方法中恢復(fù)（Recovered）節(jié)點的數(shù)目。表1中表示改進方法，SIR模型達到平衡后所需的時間。表示魏的方法，SIR模型達到平衡后所需要的時間。表示改進的方法，SIR模型達到平衡后，從感染狀態(tài)恢復(fù)到健康狀態(tài)的所有節(jié)點數(shù)目。表示魏的方法，SIR模型達到平衡后，從感染狀態(tài)恢復(fù)到健康狀態(tài)的所有節(jié)點數(shù)目。

表1 基于SIR傳染病模型實驗數(shù)據(jù)統(tǒng)計表

Tab.1 The data of SIR spreading

網(wǎng)絡(luò) Blogs Email Netscience USAir

T改進 9 13 5 10

T魏 9 13 5 9

N改進 954 749 2.92 247

N魏 942 733 2.82 208

圖2 基于SIR模型的傳染病模擬實驗

Fig.2 The experiment of SIR spreading

由圖2和表1可以看出，改進的方法比魏的方法所得前30個節(jié)點在SIR模型進行傳播實驗后得到更多的恢復(fù)節(jié)點，也就是說改進的方法SIR實驗中曾經(jīng)被感染的節(jié)點更多。因此可以看出改進的方法所得到的前30個重要節(jié)點有更強的傳播能力。由此可以認為改進的節(jié)點所排序得出的節(jié)點重要性更強。

4 結(jié)論（Conclusion）

本文在魏等人的基礎(chǔ)上提出了一種改進的加權(quán)k-核分解方法。本文的方法主要通過改進計算加權(quán)度的方法對魏等人的k-核分解方法進行改進。通過實驗進一步驗證了該方法的可行性和優(yōu)越性。當然，任何方法都不是完美的，該方法計算量較大，比較耗時。對于節(jié)點重要度的排序算法仍需不斷完善和改進。

參考文獻（References）

[1] L.C.Freeman，A set of measures of centrality based on betweenness，

Sociometry，1977：35-41.

[2] M.E.Newman.The mathematics of networks.The new palgrave

encyclopedia of economics 2，2008：1-12.

[3] 穆寶良，李晉.基于自適應(yīng)仿射傳播聚類的社團發(fā)現(xiàn)求解[J].

軟件工程師，2013（6）：32-34.

[4] 任曉龍，呂琳媛.網(wǎng)絡(luò)重要節(jié)點排序方法綜述[J].科學通報，

2014，13：004.

[5] M.Kitsak，L.K.Gallos，S.Havlin，F(xiàn).Liljeros，L.Muchnik，H.E.Stanley，

H.A.Makse.Identification of influential spreaders in complex

networks，Nature Physics 6，2010：888-893.

[6] B.Wei，J.Liu，D.Wei，C.Gao，Y.Deng.Weighted k-shell decompositionfor

complex networks based on potential edge weights，Physica

A：Statistical Mechanics and its Applications 420，2015：277-283.

[7] F.Fu，D.I.Rosenbloom，L.Wang，M.A.Nowak.Imitation dynamicsof

vaccination behaviour on social networks，Proceedings of the

RoyalSociety of London B：Biological Sciences 278，2011：42-49.

[8] Du Y，et al.A new closeness centrality measure via effective

distance in complex networks[J].Chaos：An Interdisciplinary

Journal of Nonlinear Science，2015，25（3）：033-112.

[9] Chen D，et al.Identifying influential nodes in complex

networks[J].Physica a：Statistical mechanics and its applications，

2012，391（4）：1777-1787.

[10] Newman M E J，F(xiàn)orrest S，Balthrop J.Email networks and the

spread of computer viruses[J].Physical Review E，2002，66（3）：

035-101.

作者簡介：

宋起超（1989-），女，碩士生.研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò).