基于社區劃分的節點重要性評估方法

王 安，顧益軍

中國人民公安大學 信息技術與網絡安全學院，北京102600

1 引言

隨著復雜系統科學的研究與發展，同時受到信息技術的推動作用，人們發現了現實世界中的許多具備關系的事物或以復雜網絡的形式存在、或能被轉化成復雜網絡。復雜網絡的節點在結構和功能上承擔著不同作用。復雜網絡中節點重要性排序問題也吸引了越來越多的科研人員的關注。復雜網絡節點重要性排序問題應用較為廣泛，在特定群體內找出關鍵人物，進行社交推薦，甚至對一篇文章進行關鍵詞抽取等等都或多或少涉及到節點重要性的排序。因此，對復雜網絡的重要節點進行排序非常重要。

復雜網絡的節點重要排序已有若干經典的算法[1-2]，如復雜網絡的度中心性、接近中心性、介數中心性[3-4]、PageRank[5-6]、K-shell[7]等方法。這些方法從不同角度測定了節點的重要程度。

近年來相關研究與改進有以下幾類：

（1）發掘網絡中新的特征

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

（2）對已有方法進行結合

于會等人[11]利用TOPSIS決策方法，融合多個指標，對節點的重要性進行綜合計算。Bian 等人[12]利用證據理論將多種中心性方法進行結合，有效地結合了多種算法的優點。將多種方法進行結合的方式本質上是對已有的方法進行加權，考慮得更加全面，但是如果擴充的方法過多，或者其中一些方法的排序結果存在較大的沖突，便不能很好地平衡各個算法的權重，算法的復雜度也較高，不適合于規模較大的網絡。

（3）對已有方法進行改進

現有算法或多或少都存在一定的局限性，作為復雜網絡節點重要性排序最經典的算法——PageRank 備受國內外研究人員的關注。Lü 等人[6]在PageRank 算法的基礎之上增加了背景節點，形成了比PageRank 收斂更加迅速，抗干擾能力更強的LeaderRank算法。

以上各方法得到的重要節點都較為集中，忽略了復雜網絡重要節點集合的整體的傳播影響力。同時部分算法也存在時間復雜度過大的問題，無法在大規模網絡上進行應用。

在復雜網絡分析中，網絡中的某些節點傾向于形成一些緊密聯系的小團體，即這些網絡呈現了一定的社區結構特征，社區內的節點相比于社區外部的節點具有更強的相互作用[13]，聯系更加緊密。

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

2 PageRank算法

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

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

3 LPA算法

標簽傳播算法LPA[18-19]的思想十分簡單，與社區劃分中模塊度優化有關算法不同，LPA算法不需要設定目標函數，它是一種基于已有節點的社區標簽信息來判定尚未標記節點的社區標簽所屬，通過不斷地迭代計算，最終使得每個節點和其多數相鄰節點所屬同一個社區。

LPA算法的具體步驟為：

（1）初始化標簽分配，令每個節點隨機被分配唯一的社區所屬標簽；

（2）更新節點的社區所屬標簽，令其社區所屬和其多數相鄰節點的社區所屬相同，如果具有多個同樣數量的社區所屬，則對其進行隨機選擇。

其中，Cn為社區所屬標簽，Nkn表示節點n 的鄰居中標簽為k 的所有節點構成的集合，δ 表示節點n,m 的連邊權重。

（3）重復步驟（1）、（2）直到所有節點的社區所屬不再發生變化。

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

4 引入社區劃分的CD-PR算法

4.1 CD-PR算法流程

按照PageRank 算法的排序過程，若某一個節點最終的PR 值越大，那么一切連接到該節點的其余節點最終的PR 值同樣也會很大，同時，如果網絡較大，每個節點所能分配的Rank 值會較小，這會導致使用PageRank方法進行節點重要性排序的結果較為集中。可以將PageRank 的這種特性稱之為重要節點聚集效應。然而，在一些領域的研究，例如傳銷打擊問題、犯罪團伙分析中，更加傾向于找出小團體的核心。這使得PageRank在這一問題上存在一些局限性。

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

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

（1）對待節點排序的復雜網絡進行社區劃分

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

（2）求取各節點在各自社區內的PageRank值

利用PageRank算法分別計算每個子圖的每一節點的PageRank值。

實際上由于圖G(V,E)被分割為多個獨立的子圖G={G1,G2,…,Gn}，這使得每一個社區子圖的PageRank值計算都是相對獨立的。在實際進行計算時可以將計算PageRank 的任務采用并行計算的方式，分攤到多個線程上并同時進行計算，提高迭代收斂的速度。

（3）對復雜網絡G=(V,E)構造超節點聚合鄰接矩陣

將同一社區的節點聚合為一個超節點，使每一社區Cn對應超節點sn，構造超節點聚合鄰接矩陣S,S 的元素Sij表示超節點連邊的權重，即Sij為連接社區i 到社區j 所有的節點對的邊權重之和，由于G=(V,E)為非帶權圖，所以超節點聚合鄰接矩陣連邊的權重Sij便是兩個社區的連邊總數。

其中Tij為社區i 與社區j 的連邊總數。當i=j 時為同一個社區，所以此時

（4）計算社區結構系數

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

記Knin為社區Cn內部度之和，Knout為社區Cn外部度之和，公式（9）（10）分別計算了社區內外度之和：

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

分別計算社區Cn的內部度和外部度，計算社區結構系數向量I=(I(1),I(2),…,I(n))T，其中每一分量I(n)為各個社區Cn社區結構系數，可按照公式（13）進行計算：

由于向量I 是由一個社區的內外連邊數量計算得到，所以向量I 可以表示一個社區內部連接和外部連接的緊密程度，衡量消息在社區內外的流轉情況，從而衡量某一社區的連通情況。社區的內外連接情況都會影響一個社區的傳播能力。因此用這樣的社區結構系數便可以衡量一個社區在復雜網絡中的地位。

（5）對社區結構系數進行歸一化

在步驟（4）中得到了表示每個社區內外連接情況的結構系數，然而，社區結構系數的取值存在接近零的情況，同時各個系數總和不為1，這會導致無法從各個社區分別抽取相應數量的候選節點。因此需要將社區結構系數進行歸一化。

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

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

圖1 展示了社區內外連接情況轉化為概率表示的過程，在使用SOFTMAX 函數后，社區的內外連接情況便轉化為概率的表示，從而可以按照社區選擇概率分別貢獻出相應比例的候選節點，使得重要節點的獲取更加分散。這種方式得到的重要節點更利于復雜網絡中信息的傳播。

圖1 社區選擇概率向量計算示意圖

（6）各社區分別貢獻相應比例的候選節點

根據排序節點總數在各自社區內利用PR抽取到相應比例的節點數量。每一社區按照公式（16）分別抽取相應數量的節點，組成候選節點集。

（7）重新將節點進行排序，得到最終結果

將候選節點集利用公式計算綜合Rank值后再進行排序：

其中，PRCw(w)為節點w 在其社區Cw內的PageRank值， ||Cw為w 所在社區規模，這里指社區內節點的數量，為節點所在社區Cw對應的社區選擇概率向量的分量。

通過以上步驟便可以到Top-K 個重要節點的排序。

4.2 時間復雜度分析

令復雜網絡G(V,E)的節點數為n，連邊數為m 。劃分平均社區數為k，每個社區平均所具有的節點數記為n′，每個社區平均所具有的內部連邊數記為m′。

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

5 實驗及分析

考慮到不同網絡具有不同結構與特征，為了評估算法的有效性，本文采用多種方式對不同網絡進行仿真實驗，所實驗網絡均為開源數據，統計數據如表1所示。

表1 數據集相關統計情況說明

5.1 各方法排序結果對比

本文將CD-PR方法與PageRank方法、基于互信息[10]（MI）的方法，以及復雜網絡中常用的中心性方法[1]、度中心性（DC）、接近中心性（CC）、介數中心性（BC），分別對Club、Dolphin、Football、Soc-wiki-Vote網絡進行對比實驗，應用這些算法分別取前10個重要節點，結果如表2（a）與（b）所示。

5.2 調節因子的確定

在對各社區分別貢獻相應比例的候選節點的步驟中，為了進一步確定調節因子的取值對重要節點排序影響，本文對調節因子不同取值進行了對比。結果如表3所示。

在使用LPA對網絡進行劃分時，會產生一些規模較小的社區，而CD-PR 的策略是分別從每個社區抽取一定比例的候選節點，候選節點數目應大于最終需求的數量topk，λ 不宜過小或者過大，因此本文將λ 定為0.5以確保足夠數量的候選節點被抽取出。

5.3 排序結果相關性分析

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

圖2顯示，CD-PR與PageRank的結果具有一定相似性，這是因為本文所提出的CD-PR算法改進自PageRank算法，在PageRank的基礎之上加入了社區的約束，存在一定的衍生關系。

表2（a）Club與Dolphin網絡各方法排序結果

表3 λ=0～0.7,topk=10 時各社區貢獻節點數量對比

圖2 各方法肯德爾相關系數矩陣熱力圖

5.4 SIR傳播性能實驗

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

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

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

圖3 Club網絡SIR傳播實驗結果

圖4 Dolphin網絡SIR傳播實驗結果

圖5 Football網絡SIR傳播實驗結果

圖6 Wiki-Vote網絡SIR傳播實驗結果

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

多節點傳播性能實驗結果如圖3（b）到圖6（b）所示，在進行實驗時，Club、Dolphin、Football 網絡都取前5 個的感染源，考慮到Wiki-Vote 網絡節點數量比較多，這里將排序前10的節點都作為感染源，進行多次實驗，測試節點序列整體的傳播能力。可以看出本文提出的CD-PR 方法在多個節點同時作為感染源時傳播性能在不同網絡均優于PageRank 算法。原因在于，本文所提出的方法排序的結果更加傾向于各個社區內部排名較高的節點，同時也關注了多個社區，而PageRank產生部分排名較高的節點會出現在一個社區的內部的結果。導致其社區間的傳播影響力較低。

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

6 結束語

本文主要的貢獻是在求取節點重要性算法的基礎上引入了社區劃分的方法，綜合考慮節點的社區結構特征和其節點連接特征，提出了一種基于社區劃分的節點重要性排序算法CD-PR。本文對多種開源的真實復雜網絡進行了節點重要性的排序，利用SIR傳播模型對單一節點以及全部節點進行了實驗，驗證了CD-PR 方法對重要節點排序的有效性。

本文提出的方法還有一定的不足之處。應用的標簽傳播算法雖然速度較快，但是對社區劃分存在一定的隨機性，這樣的隨機性會使節點重要性具有一些不穩定性。今后的工作將包括如何減少不穩定性，更加高效準確地對復雜網絡的節點的排序重要性進行排序。