一種新的改進的加權k—核分解方法

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

關鍵詞：復雜網絡；節點重要度；k-核分解；SIR

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

1 引言（Introduction）

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

2 理論方法（Theory and method）

2.1 k-核分解算法

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

圖1 k-核分解示例

Fig.1 An example of k-shell decomposition

2.2 加權k-核分解

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

（1）

（2）

（3）

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

2.3 改進的加權k-核分解

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

（4）

其中，α為調節因子，其取值范圍為[0，1]。當α=1時，則變為經典k-核分解；當α=0時，則節點完全依賴鄰居節點的重要性。計算加權度后，若加權度不為整數則向上取整。然后按照經典k-核分解對網絡進行分解。

3 實驗結果與分析（Experiment result and analysis）

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

表1 基于SIR傳染病模型實驗數據統計表

Tab.1 The data of SIR spreading

網絡 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個節點在SIR模型進行傳播實驗后得到更多的恢復節點，也就是說改進的方法SIR實驗中曾經被感染的節點更多。因此可以看出改進的方法所得到的前30個重要節點有更強的傳播能力。由此可以認為改進的節點所排序得出的節點重要性更強。

4 結論（Conclusion）

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

參考文獻（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] 穆寶良，李晉.基于自適應仿射傳播聚類的社團發現求解[J].

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

[4] 任曉龍，呂琳媛.網絡重要節點排序方法綜述[J].科學通報，

2014，13：004.

[5] M.Kitsak，L.K.Gallos，S.Havlin，F.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，Forrest S，Balthrop J.Email networks and the

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

035-101.

作者簡介：

宋起超（1989-），女，碩士生.研究領域：復雜網絡.