基于LeaderRank和節(jié)點(diǎn)相似度的復(fù)雜網(wǎng)絡(luò)重要節(jié)點(diǎn)排序算法

顧亦然，朱梓嫣

?

基于LeaderRank和節(jié)點(diǎn)相似度的復(fù)雜網(wǎng)絡(luò)重要節(jié)點(diǎn)排序算法

顧亦然，朱梓嫣

(南京郵電大學(xué)自動(dòng)化學(xué)院 南京 210023)

復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)對網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響引起了廣泛關(guān)注。本文在現(xiàn)有LeaderRank算法的基礎(chǔ)上，利用節(jié)點(diǎn)相似度來衡量節(jié)點(diǎn)間的相互作用，建立了SRank算法進(jìn)行重要節(jié)點(diǎn)排序。利用SIR傳播模型和斯皮爾曼等級(jí)相關(guān)系數(shù)在真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)上對本文算法與經(jīng)典的重要節(jié)點(diǎn)排序算法進(jìn)行仿真后，發(fā)現(xiàn)該算法在無向和有向網(wǎng)絡(luò)中均具有更高的準(zhǔn)確性。

復(fù)雜網(wǎng)絡(luò); 重要節(jié)點(diǎn); 相似度; SRank算法

隨著科學(xué)技術(shù)的發(fā)展，世界變得越來越小，也越來越復(fù)雜，涌現(xiàn)了大量難以用經(jīng)典概念解釋的問題，如微博中謠言通過少量節(jié)點(diǎn)快速傳播到整個(gè)網(wǎng)絡(luò)，傳染病通過交通網(wǎng)絡(luò)中的少量節(jié)點(diǎn)快速傳播擴(kuò)散[1]等。借助網(wǎng)絡(luò)科學(xué)的發(fā)展與進(jìn)步，學(xué)者們對這些問題進(jìn)行了定量化的描述和研究，將這些可以對整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)和功能產(chǎn)生巨大作用的少量節(jié)點(diǎn)，稱之為重要節(jié)點(diǎn)。挖掘這些重要節(jié)點(diǎn)并研究其內(nèi)在動(dòng)力學(xué)機(jī)理成為當(dāng)前的研究熱點(diǎn)之一。

近年來，學(xué)者在重要節(jié)點(diǎn)排序上提出了很多指標(biāo)和算法，主要有以下4個(gè)方面[2]：1) 基于節(jié)點(diǎn)鄰居節(jié)點(diǎn)的排序方法，如度中心性(degree centrality)[3]，即節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多其影響力越大，其缺點(diǎn)是僅僅考慮了節(jié)點(diǎn)的局部信息。2) 基于路徑的排序方法，如接近中心性(closeness centrality)[4]，通過計(jì)算節(jié)點(diǎn)與網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)距離平均值來衡量節(jié)點(diǎn)的重要性，缺點(diǎn)是時(shí)間復(fù)雜度比較高。3) 基于特征向量的排序方法，如PageRank算法[5]，該算法認(rèn)為每一個(gè)節(jié)點(diǎn)的重要性取決于指向它的其他節(jié)點(diǎn)的數(shù)量和質(zhì)量，缺點(diǎn)是容易陷入懸掛節(jié)點(diǎn)。LeaderRank[6-7]算法在PageRank算法的基礎(chǔ)上，通過加入一個(gè)背景節(jié)點(diǎn)，該節(jié)點(diǎn)與網(wǎng)絡(luò)的所有節(jié)點(diǎn)雙向連接，來替代PageRank算法中跳轉(zhuǎn)概率，從而提高了算法的收斂速度和魯棒性。4) 基于節(jié)點(diǎn)的移除和收縮的排序方法[8-9]，通過移除節(jié)點(diǎn)對網(wǎng)絡(luò)的破壞性來衡量節(jié)點(diǎn)的重要性，但計(jì)算復(fù)雜度高。

這些算法大多考慮節(jié)點(diǎn)在全局中的重要性或者局部重要性，忽略了節(jié)點(diǎn)間相互作用對整個(gè)網(wǎng)絡(luò)的影響。本文考慮在現(xiàn)實(shí)生活中，人們更信任那些和自己關(guān)系更為相似的人，即節(jié)點(diǎn)之間的相似度越高則節(jié)點(diǎn)間的影響力越大。共同鄰居節(jié)點(diǎn)相似度[10]表明，如果兩個(gè)節(jié)點(diǎn)的共同鄰居越多，這兩個(gè)節(jié)點(diǎn)的相似度越高。因此，本文引入節(jié)點(diǎn)相似度指標(biāo)作為節(jié)點(diǎn)局部重要性的衡量指標(biāo)，在LeaderRank的基礎(chǔ)上綜合考慮節(jié)點(diǎn)的局部重要性和全局重要性，提出SRank算法。將該算法和其他幾種經(jīng)典算法進(jìn)行比較，仿真結(jié)果表明，該算法在有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)的重要節(jié)點(diǎn)排序結(jié)果均優(yōu)于其他算法。

1 重要節(jié)點(diǎn)排序方法

1.1 LeaderRank算法

LeaderRank通過在原網(wǎng)絡(luò)中加入一個(gè)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)雙向連接的背景節(jié)點(diǎn)，增強(qiáng)網(wǎng)絡(luò)的連通性，從而提高了算法的收斂速度。

(2)

1.2 SRank算法

PageRank算法和LeaderRank算法中，每個(gè)節(jié)點(diǎn)跳轉(zhuǎn)到鄰居節(jié)點(diǎn)的概率是相等的，但是現(xiàn)實(shí)生活中，人們更信任那些和自己關(guān)系更為相似的人。在有向社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)的出邊代表該節(jié)點(diǎn)的興趣所向，入邊代表了其他節(jié)點(diǎn)對其興趣的一種認(rèn)可。可以認(rèn)為，若兩個(gè)節(jié)點(diǎn)共同指向的節(jié)點(diǎn)數(shù)越多，其興趣越相似，相似度值越高；指向兩個(gè)節(jié)點(diǎn)的其他節(jié)點(diǎn)數(shù)越多，代表其他人認(rèn)為這兩個(gè)節(jié)點(diǎn)的興趣越相似，其相似度值越高。因此，兩個(gè)節(jié)點(diǎn)的相似度，不僅和其共同指向的節(jié)點(diǎn)數(shù)有關(guān)，也和共同指向其的節(jié)點(diǎn)數(shù)有關(guān)。

對于一個(gè)簡單有向網(wǎng)絡(luò)如圖1a所示，考慮節(jié)點(diǎn)4不存在的情況，節(jié)點(diǎn)1、2、3的影響力是相同的，可得兩兩節(jié)點(diǎn)之間的相似度一致。節(jié)點(diǎn)4加入后，直接提高了節(jié)點(diǎn)1、2的影響力，對節(jié)點(diǎn)3的貢獻(xiàn)低，間接削弱了節(jié)點(diǎn)3的影響力，即節(jié)點(diǎn)對1、2相似度要高于節(jié)點(diǎn)對1、3和節(jié)點(diǎn)對2、3，符合拓?fù)浣Y(jié)構(gòu)。因此，節(jié)點(diǎn)間相似度和共同指向其的節(jié)點(diǎn)數(shù)有關(guān)，即兩個(gè)節(jié)點(diǎn)受其他節(jié)點(diǎn)共同指向的個(gè)數(shù)越多，其相似度越高。對與圖1b來說，由于節(jié)點(diǎn)1、2同時(shí)指向節(jié)點(diǎn)4，提高了節(jié)點(diǎn)4的影響力，節(jié)點(diǎn)4的影響力提高，也會(huì)提高節(jié)點(diǎn)1、2的影響力，因而節(jié)點(diǎn)1、2的相似度會(huì)高于圖1a中的相似度。因此，節(jié)點(diǎn)間相似度和其共同指向的節(jié)點(diǎn)數(shù)有關(guān)。兩個(gè)節(jié)點(diǎn)共同指向的節(jié)點(diǎn)數(shù)越多，其相似度越高。

a. 節(jié)點(diǎn)4的單向影響

b. 節(jié)點(diǎn)4的的雙向影響

圖1 簡單網(wǎng)絡(luò)

式(4)表明：1) 與節(jié)點(diǎn)連接的鄰居節(jié)點(diǎn)個(gè)數(shù)越多，節(jié)點(diǎn)的重要度越高，這與直觀判斷相符。2) 節(jié)點(diǎn)的鄰居節(jié)點(diǎn)重要度越高，節(jié)點(diǎn)的重要性越高。3) 節(jié)點(diǎn)對之間的相互影響力不同，鄰居節(jié)點(diǎn)數(shù)多的一方對另一方的影響力更大。符合現(xiàn)實(shí)網(wǎng)絡(luò)中，當(dāng)兩個(gè)人的共同好友數(shù)一致時(shí)，好友數(shù)少的一方對認(rèn)為另一方和其的關(guān)系會(huì)比好友數(shù)多的一方認(rèn)為對方和其的關(guān)系更為親密。4) 節(jié)點(diǎn)對的相似度為0時(shí)，節(jié)點(diǎn)之間仍然有相互作用。

SRank算法步驟：

1) 使用LeaderRank算法，即使用式(1)得到每個(gè)節(jié)點(diǎn)的值；2) 使用式(3)計(jì)算節(jié)點(diǎn)對之間的相似度；3) 使用式(4)得到節(jié)點(diǎn)的值。

2 算法仿真與分析

2.1 仿真數(shù)據(jù)

本文選取了4種真實(shí)網(wǎng)絡(luò)，Zachary空手道網(wǎng)絡(luò)、海豚社會(huì)網(wǎng)絡(luò)(Dolphins)、線性蟲神經(jīng)網(wǎng)絡(luò)(Neural)及美國政治家博客網(wǎng)絡(luò)(Polblogs)，其網(wǎng)絡(luò)參數(shù)如表1所示。本文節(jié)點(diǎn)相似度計(jì)算時(shí)選取參數(shù)。

2.2 排序結(jié)果與分析

Zachary空手道網(wǎng)絡(luò)和海豚網(wǎng)絡(luò)如圖2所示，分別用度中心性、接近中心性、PageRank算法、LeaderRank算法、SRank算法進(jìn)行節(jié)點(diǎn)重要性排序，所得排序結(jié)果如表2、表3所示。

a. Zachary空手道網(wǎng)絡(luò)

b. Dolphins海豚網(wǎng)絡(luò)

圖2 兩個(gè)無權(quán)無向網(wǎng)絡(luò)

表1 4種網(wǎng)絡(luò)的參數(shù)

表2 Zachary網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序

由表2可知，相較于其他算法排名，SRank算法認(rèn)為節(jié)點(diǎn)1比節(jié)點(diǎn)34更為重要。節(jié)點(diǎn)1和節(jié)點(diǎn)34的共同鄰居節(jié)點(diǎn)為節(jié)點(diǎn)9、14、20、32，其重要性不同是因?yàn)閮晒?jié)點(diǎn)特有的鄰居節(jié)點(diǎn)。對于節(jié)點(diǎn)1而言，其鄰居節(jié)點(diǎn)中節(jié)點(diǎn)2、3、4的重要性在其他算法中排名靠前，而節(jié)點(diǎn)34的鄰居節(jié)點(diǎn)中只有節(jié)點(diǎn)33的重要性在其他算法中比較高，因此，本文算法認(rèn)為節(jié)點(diǎn)34重要性低于節(jié)點(diǎn)1更為合理。本文算法認(rèn)為節(jié)點(diǎn)8的重要性比節(jié)點(diǎn)32高，因?yàn)楣?jié)點(diǎn)8的鄰居節(jié)點(diǎn)為節(jié)點(diǎn)1、2、3、4，這些節(jié)點(diǎn)重要性在其他算法中也比較高，而節(jié)點(diǎn)32的鄰居節(jié)點(diǎn)為節(jié)點(diǎn)1、25、26、29、33、34，雖然節(jié)點(diǎn)32的部分鄰居節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性比較高，但由于節(jié)點(diǎn)32的鄰居節(jié)點(diǎn)個(gè)數(shù)比較多，弱化了重要性較強(qiáng)的鄰居節(jié)點(diǎn)如節(jié)點(diǎn)33、34對其的作用。因此，本文算法認(rèn)為節(jié)點(diǎn)32重要性低于節(jié)點(diǎn)8更接近事實(shí)。

由表3可知，SRank算法選出的10個(gè)節(jié)點(diǎn)和其他算法結(jié)果相似，區(qū)別在于節(jié)點(diǎn)的重要性排序不同，說明本文算法具有一定合理性。本文算法和度中心性都認(rèn)為節(jié)點(diǎn)46比節(jié)點(diǎn)38重要。從網(wǎng)絡(luò)結(jié)構(gòu)中可以看出兩個(gè)節(jié)點(diǎn)相互連接，其影響力不同在于其存在不同的鄰居節(jié)點(diǎn)，節(jié)點(diǎn)46的鄰居節(jié)點(diǎn)為節(jié)點(diǎn)16、19、24、25、30、51、52、60，節(jié)點(diǎn)38的鄰居節(jié)點(diǎn)為節(jié)點(diǎn)15、17、34、35、37、41、44、62，可以看出，節(jié)點(diǎn)46的鄰居節(jié)點(diǎn)的影響力在其他算法中沒有節(jié)點(diǎn)38的鄰居節(jié)點(diǎn)高。但在網(wǎng)絡(luò)結(jié)構(gòu)上，節(jié)點(diǎn)46與其鄰居節(jié)點(diǎn)的相似性比節(jié)點(diǎn)38的高，例如節(jié)點(diǎn)16與節(jié)點(diǎn)46有3個(gè)共同鄰居節(jié)點(diǎn)而節(jié)點(diǎn)17與節(jié)點(diǎn)38只有兩個(gè)。因此，本文算法認(rèn)為節(jié)點(diǎn)38重要性低于節(jié)點(diǎn)46更為合理。

表3 Dolphins網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序

2.3 SIR傳播驗(yàn)證

通常采用傳染病模型評價(jià)節(jié)點(diǎn)重要性排序方法，本文采用SIR模型[1-2,11]。SIR模型中，一個(gè)節(jié)點(diǎn)的傳播能力被定義為該節(jié)點(diǎn)的平均傳播范圍，如果一個(gè)排序方法的結(jié)果使得網(wǎng)絡(luò)流傳播又快又廣，則說明該重要節(jié)點(diǎn)排序方法優(yōu)于其他方法。

定義4 節(jié)點(diǎn)的傳播重要度矩陣IR定義為多次傳播仿真網(wǎng)絡(luò)中I狀態(tài)和R狀態(tài)的節(jié)點(diǎn)占整個(gè)網(wǎng)絡(luò)的比例的平均值。分別對網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)進(jìn)行傳播仿真，即每一次仿真只有一個(gè)節(jié)點(diǎn)處于I狀態(tài)，其他節(jié)點(diǎn)都為S狀態(tài)，選取傳播時(shí)間步為10，對每個(gè)節(jié)點(diǎn)進(jìn)行100次傳播仿真，因此節(jié)點(diǎn)的傳播重要度為：

首先，選取Nerual網(wǎng)絡(luò)對其進(jìn)行仿真，將本文算法和度中心性、接近中心性、PageRank和LeaderRank進(jìn)行對比，得到每個(gè)算法的節(jié)點(diǎn)重要度和傳播重要度關(guān)系如圖3所示。由圖3明顯看出，PageRank、LeaderRank和SRank節(jié)點(diǎn)重要度和傳播重要度的線性程度表現(xiàn)更好。換而言之，本文算法在重要節(jié)點(diǎn)排序上要優(yōu)于度中心性和接近中心性。圖3c、3d、3e圖中圓圈標(biāo)注的部分中，LeaderRank、PageRank算法排名值高的其值低，而本文算法線性程度好，可知本文算法發(fā)現(xiàn)重要性低的節(jié)點(diǎn)，比另外兩種算法優(yōu)秀；此外，圖3中橢圓標(biāo)注中，本文算法在節(jié)點(diǎn)重要性高的部分其離散程度低于其他兩種算法，可知本文算法在發(fā)現(xiàn)網(wǎng)絡(luò)重要節(jié)點(diǎn)更為有效。

其次選取Polblogs網(wǎng)絡(luò)進(jìn)行仿真，將本文算法和度中心性、接近中心性、PageRank算法和LeaderRank算法進(jìn)行對比，得到每個(gè)算法的節(jié)點(diǎn)重要度和傳播重要度關(guān)系如圖4所示，PageRank、LeaderRank和SRank節(jié)點(diǎn)重要度和傳播重要度的線性程度比其他算法表現(xiàn)更好。換而言之，本文算法在重要節(jié)點(diǎn)排序上要優(yōu)于度中心性和接近中心性。

為了分析不同排名節(jié)點(diǎn)段的重要性排序結(jié)果，本文分別選擇PageRank、LeaderRank和SRank算法的重要性排序并對每個(gè)重要性排序算法的排名前10%、前20%以及所有節(jié)點(diǎn)分別進(jìn)行考慮。相關(guān)性系數(shù)對比結(jié)果如表4所示。由表4可知，無論是整個(gè)網(wǎng)絡(luò)的重要度排序還是節(jié)點(diǎn)重要性排名比較高的排序結(jié)果，本文算法的相似性程度更高，表明本文算法更優(yōu)秀。

表4 節(jié)點(diǎn)重要性排序相關(guān)性系數(shù)對比結(jié)果

表4 節(jié)點(diǎn)重要性排序相關(guān)性系數(shù)對比結(jié)果

算法Polblogsneural 全部前10%前20%全部前10%前20% DC0.823 10.993 60.977 40.444 70.950 10.876 0 CC0.429 30.944 40.888 3-0.181 80.828 20.690 0 PR0.937 60.998 60.996 40.847 50.987 20.972 7 LR0.960 90.997 70.993 60.878 40.977 60.956 3 SR0.963 90.999 30.997 90.879 50.996 70.989 4

對各算法在線性蟲神經(jīng)網(wǎng)絡(luò)、美國政治家博客網(wǎng)絡(luò)的重要節(jié)點(diǎn)排序結(jié)果進(jìn)行傳播仿真。選取傳播時(shí)間步為50，觀察網(wǎng)絡(luò)中I狀態(tài)節(jié)點(diǎn)個(gè)數(shù)SI占網(wǎng)絡(luò)的比例隨時(shí)間的變化。針對本文算法所得排名前10%節(jié)點(diǎn)，選取其中節(jié)點(diǎn)排名高于PageRank的節(jié)點(diǎn)作為傳播節(jié)點(diǎn)；同理，針對PageRank所得排名前10%節(jié)點(diǎn)，選取其中節(jié)點(diǎn)排名結(jié)果高于本文算法的節(jié)點(diǎn)作為傳播節(jié)點(diǎn)。為了保證算法對比時(shí)，不同方式選擇傳播節(jié)點(diǎn)個(gè)數(shù)相同，傳播節(jié)點(diǎn)個(gè)數(shù)較多的去除排名低的部分節(jié)點(diǎn)。其次，分別選取本文算法排名前20%和全部節(jié)點(diǎn)進(jìn)一步驗(yàn)證本文算法對比PageRank的有效性。本文算法與LeaderRank的對比亦如是。線性蟲神經(jīng)網(wǎng)絡(luò)、美國政治家博客網(wǎng)絡(luò)的傳播仿真結(jié)果分別如圖5、圖6所示。

圖5a～圖5c為本文算法與PageRank的對比結(jié)果。圖5a、圖5b中，本文算法的I狀態(tài)比例I最大值超過0.5，高于PageRank算法，且前者增長時(shí)后者已經(jīng)下降了，表明本文算法的傳播深度高于后者，也證明了本文算法選取該網(wǎng)絡(luò)的核心節(jié)點(diǎn)上表現(xiàn)比PageRank優(yōu)越。圖5c中，兩者的相差比例更加明顯，本文算法的斜率高于后者，表明本文算法傳播速度高于后者，說明了本文算法在整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)重要度排序要優(yōu)于PageRank。同理，由圖5d～圖5f本文算法與LeaderRank的對比結(jié)果可知，本文算法I狀態(tài)的最大值和斜率都高于后者，說明本文算法無論是在發(fā)現(xiàn)該網(wǎng)絡(luò)的核心節(jié)點(diǎn)上還是整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)重要度排序上，都要優(yōu)于LeaderRank。由圖6a～圖6c本文算法與PageRank的對比結(jié)果可得，本文算法的I狀態(tài)比例的最大值超過后者，且增長時(shí)其斜率高于后者，表明本文算法的傳播深度、深度高于后者，本文算法無論是在發(fā)現(xiàn)該網(wǎng)絡(luò)的核心節(jié)點(diǎn)上還是整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)重要度排序上，都要優(yōu)于PageRank。同理，由圖6d～圖6f本文算法與LeaderRank的對比結(jié)果可得，本文算法要優(yōu)于LeaderRank。

3 結(jié)束語

本文主要工作是在LeaderRank算法的基礎(chǔ)上引入了節(jié)點(diǎn)相似度的概念，綜合考慮節(jié)點(diǎn)的局部特征和全局特征，提出了SRank節(jié)點(diǎn)重要性排序算法。對四種真實(shí)網(wǎng)絡(luò)進(jìn)行重要性排序，在通過分析網(wǎng)絡(luò)結(jié)構(gòu)來說明本文算法在無向網(wǎng)絡(luò)的節(jié)點(diǎn)重要度排序的合理性同時(shí)，利用傳播仿真成功驗(yàn)證了本文算法在有向網(wǎng)絡(luò)節(jié)點(diǎn)重要度排序的有效性。

本文研究工作還存在一些不足。提出的算法主要針對于連通網(wǎng)絡(luò)，對不連通網(wǎng)絡(luò)還存在一定的不確定性。今后的工作需要更全面、科學(xué)地考慮不連通網(wǎng)絡(luò)節(jié)點(diǎn)重要性的排序和驗(yàn)證方法。

[1] 周濤, 韓筱璞, 閆小勇, 等. 人類行為時(shí)空特性的統(tǒng)計(jì)力學(xué)[J]. 電子科技大學(xué)學(xué)報(bào), 2013, 04(4): 481-540.

ZHOU Tao, HAN Xiao-pu, YAN Xiao-yong. Statistical mechanics on temporal and spatial activities of human[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(4): 481-540.

[2] 任曉龍, 呂琳媛. 網(wǎng)絡(luò)重要節(jié)點(diǎn)排序方法綜述[J]. 科學(xué)通報(bào), 2014, 59(13): 1175-1197.

REN Xiao-long, Lü Lin-yuan. Review of ranking nodes in complex networks[J]. Chin Sci Bull, 2014, 59(13): 1175-1197.

[3] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1): 113-120.

[4] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1978, 1(3): 215-239.

[5] BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks & Isdn Systems, 1998, 30(98): 107-117.

[6] Lü L, ZHANG Y C, YEUNG C H, et al. Leaders in social networks, the delicious case[J]. Plos One, 2011, 6(6): e21202.

[7] LI Q, ZHOU T, Lü L. Identifying influential spreaders by weighted LeaderRank[J]. Physica A Statistical Mechanics & Its Applications, 2014, 404(24): 47-55.

[8] 李鵬翔, 任玉晴, 席酉民. 網(wǎng)絡(luò)節(jié)點(diǎn)(集)重要性的一種度量指標(biāo)[J]. 系統(tǒng)工程, 2004, 22(4): 13-20.

LI Peng-xiang, REN Yu-qing, XI You-min. An importance measure of actors (set) within a network[J]. Systems Engineering, 2004, 22(4): 13-20.

[9] DANGALCHEV C. Residual closeness in networks[J]. Physica A, 2006, 365: 556-564.

[10] LIU Z, ZHANG Q M, Lü L, et al. Link prediction in complex networks: a local naive Bayes model[J]. Epl, 2011, 96(4): 48007.

[11] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. J Math Sociol, 1972, 2: 113-120.

[12] 馬俊, 周剛, 許斌, 等. 一種基于話題傳播的微博用戶影響力分析方法[J]. 信息工程大學(xué)學(xué)報(bào), 2013, 14(6): 735-742.

MA Jun, ZHOU Gang, XU Bin. User influence analysis in microblog based on topic diffusion[J]. Journal of Information Engineering University, 2013, 14(6): 735-742.

編 輯 蔣 曉

Node Ranking in Complex Networks Based on LeaderRank and Modes Similarity

GU Yi-ran and ZHU Zi-yan

(College of Automation, Nanjing University of Posts and Telecommunications Nanjing 210023)

The effect of important nodes in complex networks on the structure and function of the networks causes widespread concern. This paper presents a SRank algorithm based on LeaderRank and nodes similarity which is used to measure the interaction between nodes. The simulation of SIR model and Spearman’s correlation coefficient on real social networks show that the SRankalgorithm preforms better on identifying influential nodes both in directed and undirected networks, compared with the other four classical algorithms.

complex networks; important nodes; nodes similarity; SRank algorithm

TP311，N94

A

10.3969/j.issn.1001-0548.2017.02.020

2015-12-09；

2016-05-03

教育部人文社會(huì)科學(xué)研究規(guī)劃基金(15YJZH016)

顧亦然(1972-)，女，博士，教授，主要從事復(fù)雜網(wǎng)絡(luò)理論與應(yīng)用、嵌入式系統(tǒng)及通信網(wǎng)絡(luò)等方面的研究.