盛家燁

（哈爾濱工業(yè)大學(xué)建筑學(xué)院互動(dòng)媒體設(shè)計(jì)與服務(wù)創(chuàng)新文化和旅游部重點(diǎn)實(shí)驗(yàn)室，黑龍江 哈爾濱 150001）

1 重要節(jié)點(diǎn)發(fā)現(xiàn)

近年來(lái)，復(fù)雜網(wǎng)絡(luò)作為工具被廣泛地用于研究存在于自然界和人類(lèi)社會(huì)的各個(gè)領(lǐng)域的傳播現(xiàn)象，例如流行病在社會(huì)聯(lián)系網(wǎng)絡(luò)中傳播［1］、病毒在通信網(wǎng)絡(luò)中傳播［2］、謠言和信息在社交網(wǎng)絡(luò)中傳播［3］等。作為復(fù)雜網(wǎng)絡(luò)中的基本組成部分，節(jié)點(diǎn)在傳播過(guò)程中發(fā)揮著不可忽視的作用。因此，識(shí)別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)是促進(jìn)或抑制傳播的一個(gè)有效手段。

目前，已經(jīng)有大量用于識(shí)別重要節(jié)點(diǎn)的算法被提出，如度中心性（DC）、接近中心性（CC）、Katz中心性、介數(shù)中心性（BC）、LocalRank［4］、K-shell 算法［5］、PageRank［6］等。這些重要節(jié)點(diǎn)發(fā)現(xiàn)算法可以分為3 類(lèi)：基于網(wǎng)絡(luò)結(jié)構(gòu)的中心性算法、基于迭代的中心性算法和貪婪算法。

基于網(wǎng)絡(luò)結(jié)構(gòu)的中心性算法普遍從節(jié)點(diǎn)的鄰居信息中識(shí)別該節(jié)點(diǎn)的重要性。度中心性簡(jiǎn)單地認(rèn)為一個(gè)節(jié)點(diǎn)的鄰居數(shù)越多，影響力越大，不足之處在于僅考慮了節(jié)點(diǎn)最局部的信息，因此實(shí)際表現(xiàn)并不理想。針對(duì)這一問(wèn)題，一個(gè)改進(jìn)方向是考慮更多的、更高階的鄰居信息。如LocalRank［4］就考慮了節(jié)點(diǎn)共4階的鄰居信息；CI［7］被廣泛地認(rèn)為是一種識(shí)別重要節(jié)點(diǎn)的優(yōu)秀中心性指標(biāo)之一，它通過(guò)節(jié)點(diǎn)的余度和節(jié)點(diǎn)第l階鄰居的余度之和來(lái)計(jì)算該節(jié)點(diǎn)的重要性。

此外，考慮到復(fù)雜網(wǎng)絡(luò)中的邊本身就是對(duì)節(jié)點(diǎn)之間相互關(guān)系的抽象，因此通過(guò)網(wǎng)絡(luò)中的路徑來(lái)計(jì)算節(jié)點(diǎn)的重要性是另一條路線。例如介數(shù)中心性的核心是節(jié)點(diǎn)對(duì)之間的最短路徑，它認(rèn)為通過(guò)某節(jié)點(diǎn)的最短路徑數(shù)越多，則這個(gè)節(jié)點(diǎn)的重要性也就越高。但是在現(xiàn)代網(wǎng)絡(luò)上運(yùn)行的許多應(yīng)用程序需要以幾乎實(shí)時(shí)的方式計(jì)算中介中心性，必須處理大量節(jié)點(diǎn)和邊。而中介中心性高昂的時(shí)間復(fù)雜度導(dǎo)致這幾乎無(wú)法實(shí)現(xiàn)。針對(duì)這一問(wèn)題，Bonchi等［8］選擇通過(guò)近似的方式來(lái)計(jì)算中介中心性；Fan 等［9］考慮到大部分應(yīng)用場(chǎng)景只需要top-k 的節(jié)點(diǎn)，基于圖神經(jīng)網(wǎng)絡(luò)在小規(guī)模網(wǎng)絡(luò)上訓(xùn)練出了模型，能夠?yàn)槿魏挝匆?jiàn)過(guò)的網(wǎng)絡(luò)的節(jié)點(diǎn)分配相對(duì)BC分?jǐn)?shù)，從而識(shí)別出高介數(shù)中心性節(jié)點(diǎn)。

另一類(lèi)基于網(wǎng)絡(luò)結(jié)構(gòu)的中心性算法利用節(jié)點(diǎn)的位置信息來(lái)識(shí)別該節(jié)點(diǎn)的重要性。K-shell 算法通過(guò)迭代地剝?nèi)ゾW(wǎng)絡(luò)外圍的節(jié)點(diǎn)（度最?。﹣?lái)獲取節(jié)點(diǎn)的位置信息，并認(rèn)為節(jié)點(diǎn)的位置越處于網(wǎng)絡(luò)核心，則節(jié)點(diǎn)越重要，傳播能力越強(qiáng)。然而K-shell 算法也有其不足，例如劃分粒度太粗，會(huì)給大量節(jié)點(diǎn)分配相同的K-shell 值［10］。因此，有不少算法針對(duì)這個(gè)問(wèn)題進(jìn)行了改進(jìn)［10-11］。

基于迭代的中心性算法考慮了節(jié)點(diǎn)間的相互增強(qiáng)效應(yīng)，在迭代的過(guò)程中不斷優(yōu)化節(jié)點(diǎn)的重要性。這類(lèi)經(jīng)典算法除了PageRank 外，還包括HITs［12］和LeaderRank［13］等。事實(shí)上，盡管不同方法的具體實(shí)現(xiàn)細(xì)節(jié)不同，但都遵循著一個(gè)基本思想：節(jié)點(diǎn)的重要性取決于指向它的其他節(jié)點(diǎn)的數(shù)量和質(zhì)量。例如，以PageRank及其改進(jìn)［14-15］為代表的一類(lèi)方法，通過(guò)迭代來(lái)模擬隨機(jī)游走的過(guò)程，并假設(shè)節(jié)點(diǎn)的鄰居越重要，其本身重要性也越高。這類(lèi)算法適用于有向網(wǎng)絡(luò)，面對(duì)無(wú)向網(wǎng)絡(luò)時(shí)表現(xiàn)不佳［16］。

貪婪算法的目標(biāo)是在尋找種子節(jié)點(diǎn)的過(guò)程中，保證種子集的每一次增加都可以使影響力的增量最大化［17］。例如Kempe等［18］用蒙特卡洛模擬法反復(fù)選擇產(chǎn)生最大邊際影響力增量的節(jié)點(diǎn)作為種子集。顯然，貪婪算法的每一次搜索都需要對(duì)每一個(gè)節(jié)點(diǎn)重新計(jì)算一遍影響，因此時(shí)間復(fù)雜度極高。針對(duì)這一問(wèn)題，Mugisha 等［19］通過(guò)迭代基于置信度傳播設(shè)計(jì)的自洽方程，一次性計(jì)算出所有節(jié)點(diǎn)的影響，提出了BPD 算法；Li［20］提出了BPD 在因子圖上的擴(kuò)展形式；而CoreHD 算法［21］則是另辟蹊徑，啟發(fā)式地不斷刪除網(wǎng)絡(luò)2 核中度最大的節(jié)點(diǎn)，免于為每個(gè)節(jié)點(diǎn)計(jì)算刪除后的影響。盡管如此，貪婪算法的時(shí)間復(fù)雜度依然過(guò)高，以至于無(wú)法運(yùn)用到大規(guī)模網(wǎng)絡(luò)上。

近年來(lái)，有一種混合中心性方法作為中心性方法的改進(jìn)，在多維視角下量化節(jié)點(diǎn)的傳播影響力［22-23］。這類(lèi)算法從不同的角度將各類(lèi)網(wǎng)絡(luò)中節(jié)點(diǎn)的局部指數(shù)、半局部指數(shù)和全局指數(shù)結(jié)合。如Li 等［24］基于節(jié)點(diǎn)的K-shell 值，將一個(gè)節(jié)點(diǎn)的鄰居分成4 類(lèi)，并加以不同的權(quán)重。Sheng 等［25］使用共同鄰居數(shù)來(lái)衡量節(jié)點(diǎn)與鄰居之間信息共享的緊密程度，并依此對(duì)鄰居區(qū)分。Mo 等［26］基于證據(jù)理論考慮了現(xiàn)有的度中心性、介數(shù)中心性、效率中心性和相關(guān)中心性，然而，如何選擇維度指數(shù)，在準(zhǔn)確性和簡(jiǎn)單性之間達(dá)到一個(gè)很好的平衡，仍是一個(gè)挑戰(zhàn)。

總之，現(xiàn)有的算法很難在準(zhǔn)確性和簡(jiǎn)單性之間達(dá)到平衡。有些算法表現(xiàn)得非常簡(jiǎn)單，但限制了準(zhǔn)確性，如DC 和K-shell 分解算法，而其他具有高準(zhǔn)確性的算法無(wú)法應(yīng)用于大規(guī)模網(wǎng)絡(luò)，如BC 和貪婪算法?；卩従有畔⒌乃惴榻鉀Q上述問(wèn)題提供了一個(gè)很好的思路。雖然現(xiàn)有的算法已經(jīng)全面考慮了鄰居的順序、位置和重要性，但仍然沒(méi)有對(duì)鄰居在傳播中的作用進(jìn)行具體描述，也沒(méi)有區(qū)分鄰居在不同維度上的貢獻(xiàn)。

本文提出一種新的算法來(lái)識(shí)別重要節(jié)點(diǎn)。該算法從2 個(gè)方面對(duì)鄰居在傳播中的貢獻(xiàn)進(jìn)行了分類(lèi)：1）加強(qiáng)了節(jié)點(diǎn)所在的緊密連接的局部區(qū)域的傳播效果；2）通過(guò)鄰居將信息擴(kuò)展到網(wǎng)絡(luò)的其他區(qū)域。本文提出的算法的排名是通過(guò)結(jié)合共同鄰居的數(shù)量和節(jié)點(diǎn)的K-shell 值產(chǎn)生的。在8 個(gè)基于標(biāo)準(zhǔn)SIR 模型的真實(shí)網(wǎng)絡(luò)上模擬了傳播過(guò)程。實(shí)驗(yàn)結(jié)果表明，本文提出的算法比其他廣泛使用的算法表現(xiàn)得更好，而且計(jì)算復(fù)雜度更低。

2 方 法

任何傳播過(guò)程總是從幾個(gè)初始種子節(jié)點(diǎn)開(kāi)始。種子節(jié)點(diǎn)將信息或病毒傳播給其鄰居。鄰居節(jié)點(diǎn)被激活后，再進(jìn)一步傳播給鄰居的鄰居。顯然，節(jié)點(diǎn)的鄰居是其傳播能力的重要組成部分。因此，若能明白節(jié)點(diǎn)的鄰居在傳播過(guò)程中扮演著什么角色，就能更加有效地識(shí)別出網(wǎng)絡(luò)中的超級(jí)傳播者?；谶@一思想，本文提出一個(gè)基于節(jié)點(diǎn)鄰居信息，稱(chēng)之為Semi-local Centrality based on Common Neighbors（SCCN）的重要節(jié)點(diǎn)發(fā)現(xiàn)算法。

本文算法受到了PageRank（PR）算法的啟發(fā)。PageRank 算法認(rèn)為萬(wàn)維網(wǎng)中一個(gè)頁(yè)面的重要性取決于指向它的其他頁(yè)面的數(shù)量和質(zhì)量，如果一個(gè)頁(yè)面被很多高質(zhì)量頁(yè)面指向，則這個(gè)頁(yè)面的質(zhì)量也高。初始時(shí)刻，賦予每個(gè)節(jié)點(diǎn)相同的PR 值，然后進(jìn)行迭代，每一步把每個(gè)節(jié)點(diǎn)當(dāng)前的PR值平分給它所指向的所有節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的新PR值為它所獲得的PR值之和，于是得到節(jié)點(diǎn)i在時(shí)刻t的PR值為：

式中，代表指向節(jié)點(diǎn)i的節(jié)點(diǎn)集合；代表節(jié)點(diǎn)j的出度之和；N代表網(wǎng)絡(luò)中所有節(jié)點(diǎn)的數(shù)量；c代表隨機(jī)跳轉(zhuǎn)概率，防止出現(xiàn)出度為0 的節(jié)點(diǎn)不斷吸收PR值的情況。PageRank 算法實(shí)際上是馬爾科夫鏈上隨機(jī)游走過(guò)程，模擬了用戶(hù)瀏覽網(wǎng)頁(yè)的動(dòng)態(tài)過(guò)程。雖然PageRank 并沒(méi)有明確鄰居節(jié)點(diǎn)的具體作用，但是其考慮傳播動(dòng)態(tài)過(guò)程的思路是值得借鑒的。因此，SCCN 算法在探究鄰居節(jié)點(diǎn)的貢獻(xiàn)時(shí)，考慮了傳播本身的動(dòng)態(tài)特點(diǎn)。

假設(shè)存在一個(gè)具有N個(gè)節(jié)點(diǎn)與M條邊的網(wǎng)絡(luò)G。對(duì)任意一個(gè)節(jié)點(diǎn)i，Γi代表節(jié)點(diǎn)i的最近鄰居集合。當(dāng)節(jié)點(diǎn)i 被激活時(shí)，它會(huì)以概率β嘗試去激活每一個(gè)鄰居節(jié)點(diǎn)。

首先，如果節(jié)點(diǎn)i存在鄰居節(jié)點(diǎn)j和k，且j激活成功，k激活失敗。根據(jù)相互增強(qiáng)效應(yīng)［27］，如果節(jié)點(diǎn)k是i和j的共同鄰居，那么j也會(huì)嘗試激活k。這表示通過(guò)節(jié)點(diǎn)j，節(jié)點(diǎn)i成功激活兩者共同鄰居k的概率實(shí)際上是大于β的。此時(shí)，鄰居節(jié)點(diǎn)j起到了放大器的作用，加強(qiáng)了節(jié)點(diǎn)i在本地區(qū)域內(nèi)的傳播效果。

其次，如果節(jié)點(diǎn)i存在鄰居節(jié)點(diǎn)j，節(jié)點(diǎn)j存在鄰居節(jié)點(diǎn)k，且i與k無(wú)關(guān)。信息只能通過(guò)節(jié)點(diǎn)j和k之間的連接對(duì)外傳播，否則將被限制在節(jié)點(diǎn)i和j所在的本地區(qū)域。此時(shí)，節(jié)點(diǎn)j在信息傳播過(guò)程中扮演了掮客的角色，將信息傳輸?shù)骄W(wǎng)絡(luò)更廣泛的區(qū)域。

區(qū)分鄰居節(jié)點(diǎn)j具體做出何種貢獻(xiàn)的關(guān)鍵是節(jié)點(diǎn)i與j是否享有共同鄰居。因此，SCCN 使用共同鄰居數(shù)（common neighbors）來(lái)度量鄰居節(jié)點(diǎn)j這2 種貢獻(xiàn)的比例。這里給出節(jié)點(diǎn)i與節(jié)點(diǎn)j的共同鄰居數(shù)cnij為：

式中，Γi是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合。

SCCN 算法在K-shell 的基礎(chǔ)上度量鄰居節(jié)點(diǎn)的第一貢獻(xiàn)，即在節(jié)點(diǎn)所處的緊密連接的局部區(qū)域加強(qiáng)傳播效果。K-shell 算法是通過(guò)逐層剝離外圍節(jié)點(diǎn)來(lái)衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的中心位置，位于最內(nèi)層的節(jié)點(diǎn)被認(rèn)為是最重要的節(jié)點(diǎn)［5］。這種分解方式有一個(gè)很有意思的特性，即如果一個(gè)節(jié)點(diǎn)的K-shell 值等于x，那么這個(gè)節(jié)點(diǎn)一定至少處于一個(gè)有x+1 個(gè)節(jié)點(diǎn)組成的全連通子圖中。此特性可以方便地估計(jì)一個(gè)節(jié)點(diǎn)所在的連接緊密的本地區(qū)域范圍的大小，即包括節(jié)點(diǎn)的數(shù)量。因此，SCCN 定義網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn)i，基于其鄰居節(jié)點(diǎn)的第一種貢獻(xiàn)所獲得的影響力為：

式中，Γi是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合，cnij是節(jié)點(diǎn)i和節(jié)點(diǎn)j 的共同鄰居數(shù)，kj是節(jié)點(diǎn)j的度值，ksj是節(jié)點(diǎn)的k殼數(shù)。代表的是鄰居節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i重要性的貢獻(xiàn)度，屬于加強(qiáng)節(jié)點(diǎn)i在本地區(qū)域內(nèi)傳播效果的比例。同時(shí)，考慮到節(jié)點(diǎn)所處的本地區(qū)域大小和緊密程度都是有上限的，隨著與節(jié)點(diǎn)i具有共同鄰居的鄰居節(jié)點(diǎn)j增多，鄰居節(jié)點(diǎn)j對(duì)i的貢獻(xiàn)會(huì)逐漸衰減，因此SCCN對(duì)這一部分的影響取了對(duì)數(shù)。

對(duì)于鄰居節(jié)點(diǎn)的第二種貢獻(xiàn)，擴(kuò)展節(jié)點(diǎn)所攜帶的信息至網(wǎng)絡(luò)其他區(qū)域，SCCN 選擇基于節(jié)點(diǎn)的度值和共同鄰居數(shù)去度量。與第一貢獻(xiàn)相比，第二貢獻(xiàn)是為了促進(jìn)信息在整個(gè)網(wǎng)絡(luò)中的傳播，其作用應(yīng)該更加重要，所以取指數(shù)形式。因此，SCCN定義網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn)i，基于其鄰居節(jié)點(diǎn)的第二種貢獻(xiàn)所獲得的影響力為：

最終，網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)i基于其鄰居計(jì)算得出的影響力為上述2種貢獻(xiàn)的組合：

接下來(lái)，為了更清楚地闡述SCCN 的計(jì)算流程，本文將以圖1中的節(jié)點(diǎn)v5為例展示計(jì)算過(guò)程。

圖1 一個(gè)具有11個(gè)節(jié)點(diǎn)與17條邊的示例網(wǎng)絡(luò)

節(jié)點(diǎn)v5的鄰居節(jié)點(diǎn)包括節(jié)點(diǎn)v4、v2、v6和v10。根據(jù)公式（2），計(jì)算出節(jié)點(diǎn)v5與其鄰居節(jié)點(diǎn)之間的共同鄰居數(shù)：cn5，4=2、cn5，2=2、cn5，6=1、cn5，10=1。根據(jù)公式（3），計(jì)算出節(jié)點(diǎn)v5基于其鄰居第一種貢獻(xiàn)所獲得的影響力為：

根據(jù)公式（4），計(jì)算出節(jié)點(diǎn)v5基于其鄰居第二種貢獻(xiàn)所獲得的影響力為：

最后，根據(jù)公式（5），可以計(jì)算出節(jié)點(diǎn)v5的SCCN值為：

示例網(wǎng)絡(luò)中其他節(jié)點(diǎn)的SCCN 值按照相同的流程計(jì)算。表1 展示了示例中每個(gè)節(jié)點(diǎn)的DC、BC、Kshell、PR和SCCN值。

表1 示例網(wǎng)絡(luò)11個(gè)節(jié)點(diǎn)不同中心性的值

從這個(gè)示例網(wǎng)絡(luò)來(lái)看，按照SCCN 值的排序結(jié)果為v2、v6、v5、v4、v7、v3、v8、v10、v11、v1、v9；按照BC 的排序結(jié)果為v6、v4、v2、v7、v3、v5、v9、v8、v1、v10、v11；按照PR 的排序結(jié)果為v4、v7、v5、v6、v2、v8、v3、v11、v10、v9、v1。在SCCN 排序結(jié)果中，排名第一的節(jié)點(diǎn)是v2，其在按BC和PR 的排序結(jié)果中分別排名第3 和第5。節(jié)點(diǎn)v1和v9的計(jì)算結(jié)果是0，因?yàn)槭纠W(wǎng)絡(luò)中不存在以它們?yōu)轫旤c(diǎn)的三角形，導(dǎo)致local1和local9等于0。事實(shí)上，這2 個(gè)節(jié)點(diǎn)在按照BC 和PR 的排序結(jié)果中也處于較后的位置。此外，在這個(gè)示例網(wǎng)絡(luò)上，有許多節(jié)點(diǎn)享有相同的度值和K-shell 值，粒度較粗，但是SCCN 不存在這一問(wèn)題。

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集

為了驗(yàn)證SCCN 的有效性，本文選取8 個(gè)真實(shí)世界網(wǎng)絡(luò)樣本對(duì)SCCN與同類(lèi)算法進(jìn)行對(duì)比：

1）power，一個(gè)代表美國(guó)西部州電網(wǎng)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)。

2）Email-Enron，一個(gè)來(lái)自Enron 公司的電子郵件通訊網(wǎng)絡(luò)。網(wǎng)絡(luò)的節(jié)點(diǎn)是電子郵件地址，如果一個(gè)地址i至少向地址j發(fā)送了一封郵件，那么該圖就包含一條從i到j(luò)的無(wú)向邊。

3）Wiki-Vote，一個(gè)包括維基百科投票數(shù)據(jù)的網(wǎng)絡(luò)。

4）musae-squirrel，一個(gè)Facebook 網(wǎng)站的頁(yè)-頁(yè)圖。節(jié)點(diǎn)代表Facebook的官方網(wǎng)頁(yè)，而鏈接是網(wǎng)站之間的相互喜歡。該圖是在2017 年11 月通過(guò)Facebook Graph API收集的。

5） CA-CondMat，一個(gè)協(xié)作網(wǎng)絡(luò)，數(shù)據(jù)涵蓋了1993年1月至2003年4月（124個(gè)月）期間提交給Condense Matter Physics的論文作者之間的科學(xué)合作。

6）CA-HepPh，一個(gè)協(xié)作網(wǎng)絡(luò)，數(shù)據(jù)涵蓋1993 年1 月至2003 年4 月（124 個(gè)月）期間提交給High Energy Physics-Phenomenology 的論文作者之間的科學(xué)合作。

7）p2p-Gnutella24，一個(gè)2002 年8 月24 日收集的Gnutella點(diǎn)對(duì)點(diǎn)文件傳輸網(wǎng)絡(luò)。

8）p2p-Gnutella25，一個(gè)2002 年8 月25 日收集的Gnutella點(diǎn)對(duì)點(diǎn)文件傳輸網(wǎng)絡(luò)。

上述這些網(wǎng)絡(luò)樣本均來(lái)自Stanford Large Network Dataset Collection。在實(shí)驗(yàn)過(guò)程中，如果發(fā)現(xiàn)某一網(wǎng)絡(luò)并不是連通的，則使用其最大連通分量。這些網(wǎng)絡(luò)的高級(jí)特征由表2（其中N表示節(jié)點(diǎn)數(shù)、M表示邊數(shù)、D表示平均度、L表示平均最短路徑、C表示平均聚類(lèi)系數(shù)）展示。

表2 8個(gè)真實(shí)世界網(wǎng)絡(luò)的結(jié)構(gòu)特征

3.2 實(shí)驗(yàn)結(jié)果

一般來(lái)講，越重要的節(jié)點(diǎn)在傳播過(guò)程中能夠激活越多的節(jié)點(diǎn)。因此，為了驗(yàn)證本文提出算法的準(zhǔn)確性，本文選擇使用標(biāo)準(zhǔn)SIR 模型來(lái)計(jì)算不同重要節(jié)點(diǎn)發(fā)現(xiàn)算法在多個(gè)真實(shí)世界網(wǎng)絡(luò)上的模擬結(jié)果。

在標(biāo)準(zhǔn)SIR模型中，網(wǎng)絡(luò)上的節(jié)點(diǎn)被分為3類(lèi)：

1）易感者（S），此類(lèi)節(jié)點(diǎn)沒(méi)有被感染，但是其缺乏免疫力能被鄰居節(jié)點(diǎn)中的感染節(jié)點(diǎn)以特定概率β感染。

2）感染者（I），此類(lèi)節(jié)點(diǎn)已經(jīng)被感染，同時(shí)以一定的概率感染其鄰居節(jié)點(diǎn)。

3）恢復(fù)者（R），此類(lèi)節(jié)點(diǎn)從感染中恢復(fù)并得到免疫能力，在后續(xù)傳播過(guò)程中不會(huì)再被感染。

在開(kāi)始階段，k個(gè)節(jié)點(diǎn)被設(shè)為種子節(jié)點(diǎn)，是感染源。所有其他節(jié)點(diǎn)被設(shè)置為易感節(jié)點(diǎn)。在接下來(lái)的每一個(gè)單位時(shí)間步長(zhǎng)內(nèi)，感染者節(jié)點(diǎn)都以特定的概率β去感染易感鄰居節(jié)點(diǎn)。同時(shí)，感染者節(jié)點(diǎn)以特定的概率γ恢復(fù)。重復(fù)此過(guò)程，直到網(wǎng)絡(luò)中沒(méi)有易受影響的節(jié)點(diǎn)為止。這里定義關(guān)于時(shí)間步長(zhǎng)t的函數(shù)F（t），表示在時(shí)間t內(nèi)網(wǎng)絡(luò)上感染節(jié)點(diǎn)與恢復(fù)節(jié)點(diǎn)之和占總節(jié)點(diǎn)的比重，即代表了傳播規(guī)模。顯然，F(xiàn)（t）的值會(huì)隨著時(shí)間t逐漸收斂，最終達(dá)到一個(gè)穩(wěn)定狀態(tài)，此時(shí)傳播過(guò)程結(jié)束。F（t）越高，表明種子節(jié)點(diǎn)的影響力就越大。通過(guò)選擇不同節(jié)點(diǎn)作為初始種子節(jié)點(diǎn)，并比較傳播結(jié)束時(shí)的F（t）值，可以得出不同種子節(jié)點(diǎn)的影響力大小。

在這些實(shí)驗(yàn)中，根據(jù)度中心性（DC），K-shell（KS），介數(shù)中心性（BC），PageRank（PR）和SCCN 計(jì)算出每個(gè)真實(shí)網(wǎng)絡(luò)上節(jié)點(diǎn)的重要性順序。由于本文的研究更關(guān)注網(wǎng)絡(luò)中的超級(jí)傳播者，因此選擇重要性排名前10的節(jié)點(diǎn)作為初始種子節(jié)點(diǎn)，根據(jù)標(biāo)準(zhǔn)SIR模型進(jìn)行數(shù)值模擬。最終的F（t）是在重復(fù)計(jì)算1000 次后取的平均值。

表3 中的數(shù)據(jù)表明，在power 中，SCCN 計(jì)算排名第1 的節(jié)點(diǎn)是2553，在DC 和PR 中分別排名第1 和第4。SCCN 計(jì)算排名第2的節(jié)點(diǎn)是4458，在DC 和PR 中分別排名第2 和第1。在SCCN 中排名第3 和第5～第8 的節(jié)點(diǎn)則在DC、BC 和PR 中均未出現(xiàn)。在CAHepPh 中，SCCN 認(rèn)為排名第2 的節(jié)點(diǎn)是19732，在BC和PR 中都排名第1。SCCN 認(rèn)為排名第2 的節(jié)點(diǎn)是29392，在BC 和PR 中都排名第5。SCCN 認(rèn)為排名第5 的節(jié)點(diǎn)是28271，在BC 和PR 中都排名第3。而SCCN 中排名第1、第4和第6～第7的節(jié)點(diǎn)均未在其他算法中出現(xiàn)。這些跡象表示SCCN 能夠識(shí)別出在其他同類(lèi)算法中排名較前，出現(xiàn)次數(shù)較多的節(jié)點(diǎn)，又能發(fā)現(xiàn)其它算法無(wú)法識(shí)別的潛在重要節(jié)點(diǎn)。

表3 根據(jù)DC、BC、K-shell、PageRank和SCCN排序得出的top-10節(jié)點(diǎn)編號(hào)

圖2（圖中橫坐標(biāo)表示SIR 模擬的時(shí)間步長(zhǎng)，縱坐標(biāo)表示感染節(jié)點(diǎn)與恢復(fù)節(jié)點(diǎn)所占的比例）清楚地表明，通過(guò)SCCN 選擇出的種子節(jié)點(diǎn)，相比于其他算法，在SIR 模擬的整個(gè)傳播過(guò)程中能夠感染更多的節(jié)點(diǎn)，這表示通過(guò)SCCN 選擇出來(lái)的節(jié)點(diǎn)更加重要，SCCN具有更高的精確性。在圖2（b）中，迭代停止時(shí)，（I+R）/N最大的是代表SCCN的曲線。這代表SCCN算法在Email-Enron 上表現(xiàn)得最優(yōu)。DC 的表現(xiàn)弱于SCCN，再之后則是BC、PR 和K-shell。在圖2（e）中，同樣是SCCN 表現(xiàn)得最優(yōu)，之后是PR、BC、DC 和Kshell。這說(shuō)明SCCN選擇的種子節(jié)點(diǎn)有效地?cái)U(kuò)大了信息的傳播規(guī)模。

圖2 DC、BC、K-Shell、PageRank和SCCN在8個(gè)真實(shí)世界網(wǎng)絡(luò)上的SIR模擬結(jié)果

此外，在一些網(wǎng)絡(luò)上，迭代停止時(shí)，BC 與PageRank二者之間（I+R）/N更大的是BC，這說(shuō)明BC表現(xiàn)得比PageRank 更優(yōu)，如圖2（f）和圖2（h）所示；在另一些網(wǎng)絡(luò)上，PageRank 表現(xiàn)得比BC 更優(yōu)，如圖2（a）和圖2（c）所示；也有一些網(wǎng)絡(luò)，兩者表現(xiàn)的差不多，如圖2（b）所示。而SCCN 雖然在圖2（c）和圖2（d）中與BC、PageRank 很接近，但在各個(gè)網(wǎng)絡(luò)樣本上都能保證處于最優(yōu)水平。這些現(xiàn)象說(shuō)明，BC 和PageRank 在不同的網(wǎng)絡(luò)上的穩(wěn)定性不如SCCN。

最后，本文對(duì)SCCN 的時(shí)間復(fù)雜度進(jìn)行簡(jiǎn)要的分析。SCCN 的時(shí)間復(fù)雜度由3 個(gè)部分組成：1）計(jì)算節(jié)點(diǎn)之間共同鄰居數(shù)；2）計(jì)算節(jié)點(diǎn)K-shell值；3）計(jì)算節(jié)點(diǎn)度。對(duì)于第1 部分，算法需要遍歷每個(gè)節(jié)點(diǎn)鄰居的鄰居，因此其平均復(fù)雜度大致為O（N＜k＞2），其中N代表給定網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，＜k＞代表所有節(jié)點(diǎn)的平均度數(shù)。K-shell 算法的復(fù)雜度為O（N）。計(jì)算節(jié)點(diǎn)度數(shù)的復(fù)雜度為O（N）。那么SCCN 的總時(shí)間復(fù)雜度為O（N＜k＞2+N+N），相對(duì)于復(fù)雜度為O（MN）的介數(shù)中心性和復(fù)雜度為O（N2）的PageRank 來(lái)說(shuō)是比較低的。這代表SCCN能更好地適用于大規(guī)模網(wǎng)絡(luò)。

4 結(jié)束語(yǔ)

本文提出了一種基于節(jié)點(diǎn)鄰居信息的重要節(jié)點(diǎn)發(fā)現(xiàn)算法SCCN。相較之前的算法并沒(méi)有很清楚地劃分鄰居節(jié)點(diǎn)的具體作用，受到PageRank 算法的啟發(fā)，SCCN 算法進(jìn)一步結(jié)合節(jié)點(diǎn)的共同鄰居數(shù)和K-shell值去開(kāi)展度量。結(jié)合傳播過(guò)程的動(dòng)態(tài)特點(diǎn)，SCCN 算法將鄰居節(jié)點(diǎn)的作用分成2 類(lèi)：1）加強(qiáng)該節(jié)點(diǎn)所在的連接緊密的本地區(qū)域內(nèi)的傳播效果；2）擴(kuò)展該節(jié)點(diǎn)所攜帶的信息至網(wǎng)絡(luò)其他區(qū)域。此外，在真實(shí)世界網(wǎng)絡(luò)上進(jìn)行的大量實(shí)驗(yàn)明確表明，本文所提出的算法優(yōu)于現(xiàn)有的知名排序算法，同時(shí)具有較低的時(shí)間復(fù)雜度，讓SCCN 可適用于大規(guī)模網(wǎng)絡(luò)。SCCN 算法不足在于，其在衡量鄰居節(jié)點(diǎn)的第2 種作用時(shí)，基本上是平等地對(duì)待每一個(gè)節(jié)點(diǎn)。這么做雖然使得SCCN 的計(jì)算復(fù)雜度較低，但也令其損失了一部分精確性。下一步的工作將會(huì)考慮在保證相對(duì)較低的計(jì)算復(fù)雜度的前提下，基于網(wǎng)絡(luò)的局部結(jié)構(gòu)更精確地衡量鄰居節(jié)點(diǎn)的第2種作用。