一種新的改進(jìn)的加權(quán)k—核分解方法

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

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

中圖分類號(hào)：TP393.0 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

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

2 理論方法（Theory and method）

2.1 k-核分解算法

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

圖1 k-核分解示例

Fig.1 An example of k-shell decomposition

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

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

（1）

（2）

（3）

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

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

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

（4）

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

3 實(shí)驗(yàn)結(jié)果與分析（Experiment result and analysis）

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

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

Tab.1 The data of SIR spreading

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

T改進(jìn) 9 13 5 10

T魏 9 13 5 9

N改進(jìn) 954 749 2.92 247

N魏 942 733 2.82 208

圖2 基于SIR模型的傳染病模擬實(shí)驗(yàn)

Fig.2 The experiment of SIR spreading

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

4 結(jié)論（Conclusion）

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

參考文獻(xiàn)（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)仿射傳播聚類的社團(tuán)發(fā)現(xiàn)求解[J].

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

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

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.

作者簡(jiǎn)介：

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