王 安，顧益軍

中國人民公安大學(xué) 信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院，北京102600

1 引言

隨著復(fù)雜系統(tǒng)科學(xué)的研究與發(fā)展，同時受到信息技術(shù)的推動作用，人們發(fā)現(xiàn)了現(xiàn)實(shí)世界中的許多具備關(guān)系的事物或以復(fù)雜網(wǎng)絡(luò)的形式存在、或能被轉(zhuǎn)化成復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)在結(jié)構(gòu)和功能上承擔(dān)著不同作用。復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序問題也吸引了越來越多的科研人員的關(guān)注。復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序問題應(yīng)用較為廣泛，在特定群體內(nèi)找出關(guān)鍵人物，進(jìn)行社交推薦，甚至對一篇文章進(jìn)行關(guān)鍵詞抽取等等都或多或少涉及到節(jié)點(diǎn)重要性的排序。因此，對復(fù)雜網(wǎng)絡(luò)的重要節(jié)點(diǎn)進(jìn)行排序非常重要。

復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要排序已有若干經(jīng)典的算法[1-2]，如復(fù)雜網(wǎng)絡(luò)的度中心性、接近中心性、介數(shù)中心性[3-4]、PageRank[5-6]、K-shell[7]等方法。這些方法從不同角度測定了節(jié)點(diǎn)的重要程度。

近年來相關(guān)研究與改進(jìn)有以下幾類：

（1）發(fā)掘網(wǎng)絡(luò)中新的特征

韓忠明等人[8]采用關(guān)注節(jié)點(diǎn)間的三角形結(jié)構(gòu)，同時考慮了周邊鄰居節(jié)點(diǎn)規(guī)模方法評估節(jié)點(diǎn)的重要性。顧亦然等人[9]利用節(jié)點(diǎn)間的相似度來評估節(jié)點(diǎn)間的相互關(guān)系，進(jìn)而得到節(jié)點(diǎn)的重要性表示。馬潤年等人[10]結(jié)合信息論的知識以節(jié)點(diǎn)所包含的信息量來評估節(jié)點(diǎn)的重要性。發(fā)掘新特征的方法還有很多，這些方法的優(yōu)點(diǎn)是對節(jié)點(diǎn)的不同特征進(jìn)行了探究，以新的特征作為節(jié)點(diǎn)重要性排序的依據(jù)。然而這樣的方法或許過于關(guān)注這些單個特征，在全面性上有一定的不足。

（2）對已有方法進(jìn)行結(jié)合

于會等人[11]利用TOPSIS決策方法，融合多個指標(biāo)，對節(jié)點(diǎn)的重要性進(jìn)行綜合計(jì)算。Bian 等人[12]利用證據(jù)理論將多種中心性方法進(jìn)行結(jié)合，有效地結(jié)合了多種算法的優(yōu)點(diǎn)。將多種方法進(jìn)行結(jié)合的方式本質(zhì)上是對已有的方法進(jìn)行加權(quán)，考慮得更加全面，但是如果擴(kuò)充的方法過多，或者其中一些方法的排序結(jié)果存在較大的沖突，便不能很好地平衡各個算法的權(quán)重，算法的復(fù)雜度也較高，不適合于規(guī)模較大的網(wǎng)絡(luò)。

（3）對已有方法進(jìn)行改進(jìn)

現(xiàn)有算法或多或少都存在一定的局限性，作為復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序最經(jīng)典的算法——PageRank 備受國內(nèi)外研究人員的關(guān)注。Lü 等人[6]在PageRank 算法的基礎(chǔ)之上增加了背景節(jié)點(diǎn)，形成了比PageRank 收斂更加迅速，抗干擾能力更強(qiáng)的LeaderRank算法。

以上各方法得到的重要節(jié)點(diǎn)都較為集中，忽略了復(fù)雜網(wǎng)絡(luò)重要節(jié)點(diǎn)集合的整體的傳播影響力。同時部分算法也存在時間復(fù)雜度過大的問題，無法在大規(guī)模網(wǎng)絡(luò)上進(jìn)行應(yīng)用。

在復(fù)雜網(wǎng)絡(luò)分析中，網(wǎng)絡(luò)中的某些節(jié)點(diǎn)傾向于形成一些緊密聯(lián)系的小團(tuán)體，即這些網(wǎng)絡(luò)呈現(xiàn)了一定的社區(qū)結(jié)構(gòu)特征，社區(qū)內(nèi)的節(jié)點(diǎn)相比于社區(qū)外部的節(jié)點(diǎn)具有更強(qiáng)的相互作用[13]，聯(lián)系更加緊密。

社區(qū)發(fā)現(xiàn)有助于解決其他的復(fù)雜網(wǎng)絡(luò)問題[14]，Hu Qingcheng 等人[15]結(jié)合FN 算法對K-shell 進(jìn)行了改進(jìn)，解決了K-shell精度低的問題。Sheikhahmadi A等人[16]應(yīng)用社區(qū)發(fā)現(xiàn)將用戶之間的交互量作為權(quán)重，提高了在線社交網(wǎng)絡(luò)的用戶影響力識別效果。付立東等人[17]以模塊密度函數(shù)來度量節(jié)點(diǎn)對不同社團(tuán)的貢獻(xiàn)度，對社團(tuán)的貢獻(xiàn)越大，該節(jié)點(diǎn)的重要性越高，然而這樣的方法與K-shell類似，很多節(jié)點(diǎn)具有同樣的重要度，差異程度較低。本文嘗試從復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)出發(fā)，同時考慮節(jié)點(diǎn)所屬社區(qū)，社區(qū)間的連接關(guān)系，以及某一節(jié)點(diǎn)在所屬社區(qū)內(nèi)部的重要性，量化某一節(jié)點(diǎn)在整個復(fù)雜網(wǎng)絡(luò)重要性。這種融合社區(qū)劃分的節(jié)點(diǎn)重要性評估方法相對于其他一些方法更加準(zhǔn)確。

2 PageRank算法

PageRank 是一種評估某一頁面質(zhì)量的算法，可以認(rèn)為其是一種概率表示。PageRank 算法的主要思想如下：若某一網(wǎng)頁被鏈入的數(shù)目越高，那么這個頁面的重要性就越高;而鏈接到該網(wǎng)頁的頁面質(zhì)量越高，則該頁面的重要性同樣就越高。PageRank 方法可應(yīng)用至任何具備相互引用特性的實(shí)體集。在復(fù)雜網(wǎng)絡(luò)中可以使用它對節(jié)點(diǎn)的重要性進(jìn)行排序。該算法計(jì)算公式如下：

其中，PR(Vi)為待評價節(jié)點(diǎn)Vi的PageRank 值；d 為阻尼因子，1-d 可以理解為隨機(jī)跳轉(zhuǎn)到其他節(jié)點(diǎn)的概率，一般取d=0.85；In(Vi)表示指向節(jié)點(diǎn)Vi的所有節(jié)點(diǎn)的集合；Out(Vj)表示節(jié)點(diǎn)vj所有指向節(jié)點(diǎn)的集合。在復(fù)雜網(wǎng)絡(luò)中，PageRank的策略是：某一個節(jié)點(diǎn)的鄰節(jié)點(diǎn)越重要，則這個節(jié)點(diǎn)越重要。

3 LPA算法

標(biāo)簽傳播算法LPA[18-19]的思想十分簡單，與社區(qū)劃分中模塊度優(yōu)化有關(guān)算法不同，LPA算法不需要設(shè)定目標(biāo)函數(shù)，它是一種基于已有節(jié)點(diǎn)的社區(qū)標(biāo)簽信息來判定尚未標(biāo)記節(jié)點(diǎn)的社區(qū)標(biāo)簽所屬，通過不斷地迭代計(jì)算，最終使得每個節(jié)點(diǎn)和其多數(shù)相鄰節(jié)點(diǎn)所屬同一個社區(qū)。

LPA算法的具體步驟為：

（1）初始化標(biāo)簽分配，令每個節(jié)點(diǎn)隨機(jī)被分配唯一的社區(qū)所屬標(biāo)簽；

（2）更新節(jié)點(diǎn)的社區(qū)所屬標(biāo)簽，令其社區(qū)所屬和其多數(shù)相鄰節(jié)點(diǎn)的社區(qū)所屬相同，如果具有多個同樣數(shù)量的社區(qū)所屬，則對其進(jìn)行隨機(jī)選擇。

其中，Cn為社區(qū)所屬標(biāo)簽，Nkn表示節(jié)點(diǎn)n 的鄰居中標(biāo)簽為k 的所有節(jié)點(diǎn)構(gòu)成的集合，δ 表示節(jié)點(diǎn)n,m 的連邊權(quán)重。

（3）重復(fù)步驟（1）、（2）直到所有節(jié)點(diǎn)的社區(qū)所屬不再發(fā)生變化。

Papadopoulos等人[20]通過大量的實(shí)驗(yàn)比較了現(xiàn)有社區(qū)發(fā)現(xiàn)算法的時空間復(fù)雜度以及應(yīng)用社區(qū)規(guī)模大小，發(fā)現(xiàn)標(biāo)簽傳播算法的時間復(fù)雜度為O(n)。相比于以優(yōu)化模塊度Q 為代表的優(yōu)化特定函數(shù)的方式進(jìn)行社區(qū)劃分，標(biāo)簽傳播算法無論是空間復(fù)雜度還是時間復(fù)雜度都不高。標(biāo)簽傳播算法具備少量迭代計(jì)算后即可收斂、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。這些優(yōu)點(diǎn)使得標(biāo)簽傳播算法對于解決大規(guī)模網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題有著較好的效果。

4 引入社區(qū)劃分的CD-PR算法

4.1 CD-PR算法流程

按照PageRank 算法的排序過程，若某一個節(jié)點(diǎn)最終的PR 值越大，那么一切連接到該節(jié)點(diǎn)的其余節(jié)點(diǎn)最終的PR 值同樣也會很大，同時，如果網(wǎng)絡(luò)較大，每個節(jié)點(diǎn)所能分配的Rank 值會較小，這會導(dǎo)致使用PageRank方法進(jìn)行節(jié)點(diǎn)重要性排序的結(jié)果較為集中?？梢詫ageRank 的這種特性稱之為重要節(jié)點(diǎn)聚集效應(yīng)。然而，在一些領(lǐng)域的研究，例如傳銷打擊問題、犯罪團(tuán)伙分析中，更加傾向于找出小團(tuán)體的核心。這使得PageRank在這一問題上存在一些局限性。

基于上述想法，本文提出一種引入社區(qū)劃分的節(jié)點(diǎn)重要性排序改進(jìn)方法CD-PR（Community Detection based PageRank）。算法總體分為以下流程：預(yù)先將網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，將網(wǎng)絡(luò)裁剪為多個子網(wǎng)絡(luò)。把社區(qū)劃分與選擇看作是概率，在每個小的社區(qū)中分別進(jìn)行PageRank排序，最后進(jìn)行歸一化處理，得到節(jié)點(diǎn)的綜合排序結(jié)果。

具體而言，CD-PR算法的流程有以下步驟：

（1）對待節(jié)點(diǎn)排序的復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)劃分

利用前文提到的LPA 算法對復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，迭代至具備穩(wěn)定的非重疊社區(qū)劃分結(jié)果后，將復(fù)雜網(wǎng)絡(luò)分割為若干子網(wǎng)絡(luò)，即G={G1,G2,…,Gn}，其中子圖Gi=(Vi,Ei)為社區(qū)集，n 為社區(qū)數(shù)量，它們滿足以下條件：

（2）求取各節(jié)點(diǎn)在各自社區(qū)內(nèi)的PageRank值

利用PageRank算法分別計(jì)算每個子圖的每一節(jié)點(diǎn)的PageRank值。

實(shí)際上由于圖G(V,E)被分割為多個獨(dú)立的子圖G={G1,G2,…,Gn}，這使得每一個社區(qū)子圖的PageRank值計(jì)算都是相對獨(dú)立的。在實(shí)際進(jìn)行計(jì)算時可以將計(jì)算PageRank 的任務(wù)采用并行計(jì)算的方式，分?jǐn)偟蕉鄠€線程上并同時進(jìn)行計(jì)算，提高迭代收斂的速度。

（3）對復(fù)雜網(wǎng)絡(luò)G=(V,E)構(gòu)造超節(jié)點(diǎn)聚合鄰接矩陣

將同一社區(qū)的節(jié)點(diǎn)聚合為一個超節(jié)點(diǎn)，使每一社區(qū)Cn對應(yīng)超節(jié)點(diǎn)sn，構(gòu)造超節(jié)點(diǎn)聚合鄰接矩陣S,S 的元素Sij表示超節(jié)點(diǎn)連邊的權(quán)重，即Sij為連接社區(qū)i 到社區(qū)j 所有的節(jié)點(diǎn)對的邊權(quán)重之和，由于G=(V,E)為非帶權(quán)圖，所以超節(jié)點(diǎn)聚合鄰接矩陣連邊的權(quán)重Sij便是兩個社區(qū)的連邊總數(shù)。

其中Tij為社區(qū)i 與社區(qū)j 的連邊總數(shù)。當(dāng)i=j 時為同一個社區(qū)，所以此時

（4）計(jì)算社區(qū)結(jié)構(gòu)系數(shù)

受節(jié)點(diǎn)互信息[10]的啟發(fā)，本文在衡量社區(qū)對節(jié)點(diǎn)重要性的影響時，主要關(guān)注了社區(qū)內(nèi)的連邊結(jié)構(gòu)特征，被劃分社區(qū)的內(nèi)部連邊數(shù)量與社區(qū)間的連邊的數(shù)量可以表示消息在社區(qū)內(nèi)外流轉(zhuǎn)傳播的情況，如果內(nèi)部連邊數(shù)量較多，則消息傾向于在社區(qū)內(nèi)部傳播，若與其他社區(qū)的連邊數(shù)量較多，則消息傾向于向其他社區(qū)進(jìn)行傳播，因此本文將社區(qū)內(nèi)部與社區(qū)間的連接情況看作是社區(qū)結(jié)構(gòu)系數(shù)，具體計(jì)算方式由可以參照以下步驟：

記Knin為社區(qū)Cn內(nèi)部度之和，Knout為社區(qū)Cn外部度之和，公式（9）（10）分別計(jì)算了社區(qū)內(nèi)外度之和：

其中Aij為圖G(V,E)鄰接矩陣的元素，表示節(jié)點(diǎn)i 和節(jié)點(diǎn)j 之間連邊的權(quán)重。對上述公式化簡，則它們對于超節(jié)點(diǎn)聚合鄰接矩陣S 有：

分別計(jì)算社區(qū)Cn的內(nèi)部度和外部度，計(jì)算社區(qū)結(jié)構(gòu)系數(shù)向量I=(I(1),I(2),…,I(n))T，其中每一分量I(n)為各個社區(qū)Cn社區(qū)結(jié)構(gòu)系數(shù)，可按照公式（13）進(jìn)行計(jì)算：

由于向量I 是由一個社區(qū)的內(nèi)外連邊數(shù)量計(jì)算得到，所以向量I 可以表示一個社區(qū)內(nèi)部連接和外部連接的緊密程度，衡量消息在社區(qū)內(nèi)外的流轉(zhuǎn)情況，從而衡量某一社區(qū)的連通情況。社區(qū)的內(nèi)外連接情況都會影響一個社區(qū)的傳播能力。因此用這樣的社區(qū)結(jié)構(gòu)系數(shù)便可以衡量一個社區(qū)在復(fù)雜網(wǎng)絡(luò)中的地位。

（5）對社區(qū)結(jié)構(gòu)系數(shù)進(jìn)行歸一化

在步驟（4）中得到了表示每個社區(qū)內(nèi)外連接情況的結(jié)構(gòu)系數(shù)，然而，社區(qū)結(jié)構(gòu)系數(shù)的取值存在接近零的情況，同時各個系數(shù)總和不為1，這會導(dǎo)致無法從各個社區(qū)分別抽取相應(yīng)數(shù)量的候選節(jié)點(diǎn)。因此需要將社區(qū)結(jié)構(gòu)系數(shù)進(jìn)行歸一化。

對于這樣的問題，在歸一化處理時應(yīng)用歸一化指數(shù)函數(shù)SOFTMAX是最為合適的，SOFTMAX可以將任意實(shí)數(shù)值映射到（0，1）的區(qū)間，使其和為1，方便從各個社區(qū)抽取相應(yīng)比例的重要節(jié)點(diǎn)。

其中，N 為社區(qū)數(shù)量，z 為n 維向量。 I?為社區(qū)選擇概率向量，每一分量為社區(qū)Cn的社區(qū)選擇概率。

圖1 展示了社區(qū)內(nèi)外連接情況轉(zhuǎn)化為概率表示的過程，在使用SOFTMAX 函數(shù)后，社區(qū)的內(nèi)外連接情況便轉(zhuǎn)化為概率的表示，從而可以按照社區(qū)選擇概率分別貢獻(xiàn)出相應(yīng)比例的候選節(jié)點(diǎn)，使得重要節(jié)點(diǎn)的獲取更加分散。這種方式得到的重要節(jié)點(diǎn)更利于復(fù)雜網(wǎng)絡(luò)中信息的傳播。

圖1 社區(qū)選擇概率向量計(jì)算示意圖

（6）各社區(qū)分別貢獻(xiàn)相應(yīng)比例的候選節(jié)點(diǎn)

根據(jù)排序節(jié)點(diǎn)總數(shù)在各自社區(qū)內(nèi)利用PR抽取到相應(yīng)比例的節(jié)點(diǎn)數(shù)量。每一社區(qū)按照公式（16）分別抽取相應(yīng)數(shù)量的節(jié)點(diǎn)，組成候選節(jié)點(diǎn)集。

（7）重新將節(jié)點(diǎn)進(jìn)行排序，得到最終結(jié)果

將候選節(jié)點(diǎn)集利用公式計(jì)算綜合Rank值后再進(jìn)行排序：

其中，PRCw(w)為節(jié)點(diǎn)w 在其社區(qū)Cw內(nèi)的PageRank值， ||Cw為w 所在社區(qū)規(guī)模，這里指社區(qū)內(nèi)節(jié)點(diǎn)的數(shù)量，為節(jié)點(diǎn)所在社區(qū)Cw對應(yīng)的社區(qū)選擇概率向量的分量。

通過以上步驟便可以到Top-K 個重要節(jié)點(diǎn)的排序。

4.2 時間復(fù)雜度分析

令復(fù)雜網(wǎng)絡(luò)G(V,E)的節(jié)點(diǎn)數(shù)為n，連邊數(shù)為m 。劃分平均社區(qū)數(shù)為k，每個社區(qū)平均所具有的節(jié)點(diǎn)數(shù)記為n′，每個社區(qū)平均所具有的內(nèi)部連邊數(shù)記為m′。

CD-PR 首先通過標(biāo)簽傳播算法得到網(wǎng)絡(luò)的社區(qū)劃分，此時所產(chǎn)生的時間復(fù)雜度為O(n)，隨后分別計(jì)算每個社區(qū)內(nèi)每個節(jié)點(diǎn)的PageRank 值，這一階段需要的時間復(fù)雜度為O(km′l)，其中l(wèi) 是平均迭代次數(shù)。而計(jì)算社區(qū)選擇概率，貢獻(xiàn)相應(yīng)比例的候選節(jié)點(diǎn)，以及對結(jié)果的重新排序相比于計(jì)算PageRank 來說都是極小的數(shù)，因此可以忽略不計(jì)，所以最終CD-PR 算法的時間復(fù)雜度為O(n+km′l)。

5 實(shí)驗(yàn)及分析

考慮到不同網(wǎng)絡(luò)具有不同結(jié)構(gòu)與特征，為了評估算法的有效性，本文采用多種方式對不同網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，所實(shí)驗(yàn)網(wǎng)絡(luò)均為開源數(shù)據(jù)，統(tǒng)計(jì)數(shù)據(jù)如表1所示。

表1 數(shù)據(jù)集相關(guān)統(tǒng)計(jì)情況說明

5.1 各方法排序結(jié)果對比

本文將CD-PR方法與PageRank方法、基于互信息[10]（MI）的方法，以及復(fù)雜網(wǎng)絡(luò)中常用的中心性方法[1]、度中心性（DC）、接近中心性（CC）、介數(shù)中心性（BC），分別對Club、Dolphin、Football、Soc-wiki-Vote網(wǎng)絡(luò)進(jìn)行對比實(shí)驗(yàn)，應(yīng)用這些算法分別取前10個重要節(jié)點(diǎn)，結(jié)果如表2（a）與（b）所示。

5.2 調(diào)節(jié)因子的確定

在對各社區(qū)分別貢獻(xiàn)相應(yīng)比例的候選節(jié)點(diǎn)的步驟中，為了進(jìn)一步確定調(diào)節(jié)因子的取值對重要節(jié)點(diǎn)排序影響，本文對調(diào)節(jié)因子不同取值進(jìn)行了對比。結(jié)果如表3所示。

在使用LPA對網(wǎng)絡(luò)進(jìn)行劃分時，會產(chǎn)生一些規(guī)模較小的社區(qū)，而CD-PR 的策略是分別從每個社區(qū)抽取一定比例的候選節(jié)點(diǎn)，候選節(jié)點(diǎn)數(shù)目應(yīng)大于最終需求的數(shù)量topk，λ 不宜過小或者過大，因此本文將λ 定為0.5以確保足夠數(shù)量的候選節(jié)點(diǎn)被抽取出。

5.3 排序結(jié)果相關(guān)性分析

為了進(jìn)一步評測本文算法和其他算法排序結(jié)果的相似程度，本文采用了肯德爾相關(guān)系數(shù)對相關(guān)算法進(jìn)行兩兩對比，肯德爾相關(guān)系數(shù)可以測量兩個隨機(jī)序列的相關(guān)性，其值域?yàn)?1 到1之間。當(dāng)τ=1 時，表示兩個序列具有完全一致的相關(guān)性；當(dāng)τ=-1 時，表示兩個序列擁有完全相反的相關(guān)性；當(dāng)τ=0 時，表示這對序列組是不相關(guān)的，而τ ≠0 則可以認(rèn)為兩個序列具有一定的相關(guān)性。形成肯德爾相關(guān)系數(shù)τ 矩陣，這里以Club網(wǎng)絡(luò)排序結(jié)果為例，計(jì)算各個方法肯德爾系數(shù)，各方法結(jié)果序列相關(guān)性熱力圖如圖2所示。

圖2顯示，CD-PR與PageRank的結(jié)果具有一定相似性，這是因?yàn)楸疚乃岢龅腃D-PR算法改進(jìn)自PageRank算法，在PageRank的基礎(chǔ)之上加入了社區(qū)的約束，存在一定的衍生關(guān)系。

表2（a）Club與Dolphin網(wǎng)絡(luò)各方法排序結(jié)果

表3 λ=0～0.7,topk=10 時各社區(qū)貢獻(xiàn)節(jié)點(diǎn)數(shù)量對比

圖2 各方法肯德爾相關(guān)系數(shù)矩陣熱力圖

5.4 SIR傳播性能實(shí)驗(yàn)

為了進(jìn)一步評測CD-PR方法的有效性，比較CD-PR方法與PageRank 方法的差異，本文采用對排序結(jié)果的節(jié)點(diǎn)做傳播性能情況的分析。這里使用SIR 傳染病模型進(jìn)行傳播性能的實(shí)驗(yàn)。SIR 傳染病模型可以有效地對某些節(jié)點(diǎn)的傳播性能進(jìn)行評估。本文對不同的復(fù)雜網(wǎng)絡(luò)，分別做單節(jié)點(diǎn)與多節(jié)點(diǎn)的傳播性能實(shí)驗(yàn)，選取感染源，以固定概率α 感染傳播，而被感染的節(jié)點(diǎn)以恢復(fù)概率β 還原到未受感染的初始狀態(tài)；如此下去，當(dāng)不再有未感染者的時候停止。

具體實(shí)驗(yàn)分為以下兩個方面：（1）單節(jié)點(diǎn)的傳播性能實(shí)驗(yàn)，即分別選取CD-PR 方法與PageRank 方法首次排序結(jié)果出現(xiàn)差異的節(jié)點(diǎn)作為感染源，取感染概率α=0.3，恢復(fù)概率β=0.000 1，即被感染節(jié)點(diǎn)幾乎不會恢復(fù)。（2）多節(jié)點(diǎn)的傳播性能實(shí)驗(yàn)，即將兩種方法挑選出的節(jié)點(diǎn)集合都作為感染源，在多節(jié)點(diǎn)的傳播實(shí)驗(yàn)中，取感染概率α=0.2，防止曲線過于陡峭。

表2 給出了CD-PR 與PageRank 方法排序前十名的節(jié)點(diǎn)序列。可以看出有著不同的排序結(jié)果，本文對兩種方法中排序不同的節(jié)點(diǎn)的傳播影響力進(jìn)行了比較，結(jié)果如圖3 到圖6 所示，由于SIR 傳播實(shí)驗(yàn)具有一定的隨機(jī)性，因此每個結(jié)果都進(jìn)行了多次實(shí)驗(yàn)。

圖3 Club網(wǎng)絡(luò)SIR傳播實(shí)驗(yàn)結(jié)果

圖4 Dolphin網(wǎng)絡(luò)SIR傳播實(shí)驗(yàn)結(jié)果

圖5 Football網(wǎng)絡(luò)SIR傳播實(shí)驗(yàn)結(jié)果

圖6 Wiki-Vote網(wǎng)絡(luò)SIR傳播實(shí)驗(yàn)結(jié)果

單節(jié)點(diǎn)傳播性能實(shí)驗(yàn)結(jié)果如圖3（a）到圖6（a）所示，在Club 網(wǎng)絡(luò)中，在重要性排第二的節(jié)點(diǎn)出現(xiàn)了不同，CD-PR 給出的排序?yàn)?2 而PageRank 給出的排序?yàn)?。對比兩者的SIR 傳播曲線可以看出在傳播前期CD-PR得到的結(jié)果比PageRank 略差，而在傳播后期則與PageRank相接近。在Dolphin網(wǎng)絡(luò)上，節(jié)點(diǎn)51和節(jié)點(diǎn)14排序有差異，使用本文提出的CD-PR 方法給出的排序分別為第一和第三，與PageRank算法相反，這里對它們進(jìn)行SIR傳播性能實(shí)驗(yàn)，可以發(fā)現(xiàn)本文給出排名第一的節(jié)點(diǎn)51 在傳播初期略優(yōu)于節(jié)點(diǎn)14，由于網(wǎng)絡(luò)規(guī)模比較小，所以在傳播一定輪數(shù)之后兩者傳播性能差異不大。兩者的傳播性能幾乎一致。在Football 網(wǎng)絡(luò)上，本文CD-PR方法給出的排序與其他方法給出的排序都有較大的差異?？梢钥闯?，本文給出的排名第一的節(jié)點(diǎn)18在傳播性能上略優(yōu)于PageRank給出的節(jié)點(diǎn)5。在實(shí)驗(yàn)中，發(fā)現(xiàn)排名二三的節(jié)點(diǎn)與其他方法給出的節(jié)點(diǎn)傳播性能差異不大。究其原因，如表1，此網(wǎng)絡(luò)節(jié)點(diǎn)連邊之比較高，平均聚類系數(shù)也較大，更利于傳播，在這樣的網(wǎng)絡(luò)中，各個排名靠前的節(jié)點(diǎn)傳播性能差異不大。在Wiki-Vote網(wǎng)絡(luò)上，本文CD-PR 方法與其他方法在節(jié)點(diǎn)重要性排首位的節(jié)點(diǎn)出現(xiàn)了不同，對比PageRank算法，本文給出的節(jié)點(diǎn)273排名第一，而PageRank則認(rèn)為431排第一。對比其SIR傳播性能可以發(fā)現(xiàn)，節(jié)點(diǎn)273具有更好的傳播能力。

多節(jié)點(diǎn)傳播性能實(shí)驗(yàn)結(jié)果如圖3（b）到圖6（b）所示，在進(jìn)行實(shí)驗(yàn)時，Club、Dolphin、Football 網(wǎng)絡(luò)都取前5 個的感染源，考慮到Wiki-Vote 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量比較多，這里將排序前10的節(jié)點(diǎn)都作為感染源，進(jìn)行多次實(shí)驗(yàn)，測試節(jié)點(diǎn)序列整體的傳播能力?？梢钥闯霰疚奶岢龅腃D-PR 方法在多個節(jié)點(diǎn)同時作為感染源時傳播性能在不同網(wǎng)絡(luò)均優(yōu)于PageRank 算法。原因在于，本文所提出的方法排序的結(jié)果更加傾向于各個社區(qū)內(nèi)部排名較高的節(jié)點(diǎn)，同時也關(guān)注了多個社區(qū)，而PageRank產(chǎn)生部分排名較高的節(jié)點(diǎn)會出現(xiàn)在一個社區(qū)的內(nèi)部的結(jié)果。導(dǎo)致其社區(qū)間的傳播影響力較低。

上述實(shí)驗(yàn)表明，針對Club、Dolphin、Football、Wiki-Vote 四個規(guī)模不一、參數(shù)差異較大的實(shí)際復(fù)雜網(wǎng)絡(luò)，本文提出的CD-PR方法在單節(jié)點(diǎn)和多節(jié)點(diǎn)傳播影響力上都比PageRank 方法挑選出的節(jié)點(diǎn)具有更好的傳播性能，特別是規(guī)模越大的網(wǎng)絡(luò)，CD-PR 的多節(jié)點(diǎn)傳播性能越好，反映了使用CD-PR方法，更加適合于對規(guī)模較大的復(fù)雜網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)重要性排序，得到的結(jié)果在多個節(jié)點(diǎn)整體的傳播性能要優(yōu)于PageRank 方法。此外，由于SIR傳播性能實(shí)驗(yàn)具有一定的隨機(jī)性，以上實(shí)驗(yàn)均為多次實(shí)驗(yàn)的平均結(jié)果。

6 結(jié)束語

本文主要的貢獻(xiàn)是在求取節(jié)點(diǎn)重要性算法的基礎(chǔ)上引入了社區(qū)劃分的方法，綜合考慮節(jié)點(diǎn)的社區(qū)結(jié)構(gòu)特征和其節(jié)點(diǎn)連接特征，提出了一種基于社區(qū)劃分的節(jié)點(diǎn)重要性排序算法CD-PR。本文對多種開源的真實(shí)復(fù)雜網(wǎng)絡(luò)進(jìn)行了節(jié)點(diǎn)重要性的排序，利用SIR傳播模型對單一節(jié)點(diǎn)以及全部節(jié)點(diǎn)進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了CD-PR 方法對重要節(jié)點(diǎn)排序的有效性。

本文提出的方法還有一定的不足之處。應(yīng)用的標(biāo)簽傳播算法雖然速度較快，但是對社區(qū)劃分存在一定的隨機(jī)性，這樣的隨機(jī)性會使節(jié)點(diǎn)重要性具有一些不穩(wěn)定性。今后的工作將包括如何減少不穩(wěn)定性，更加高效準(zhǔn)確地對復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)的排序重要性進(jìn)行排序。