基于社區劃分和改進PageRank的影響力最大化算法

吳海林

【摘 要】為了解決傳統貪心算法不能有效解決大規模社會網絡影響力最大化的效率問題，采用模塊度將大規模的通信網絡劃分成較小的社區模塊，并通過改進PageRank排名算法來評價有向復雜網絡節點的傳播能力，然后再利用KK算法挑選當前帶來最大影響范圍的剩余種子節點，提出基于社區劃分和改進PageRank的影響力最大化算法。實驗證明，該方法具有一定的擴展性和有效性。

【關鍵詞】社區劃分 改進PageRank KK算法 影響力最大化 傳播能力

1 引言

隨著各類移動社交服務如Facebook、Twitter、微博、微信、QQ等對人類生活、社交的滲透，社交網絡在信息溝通、信息共享、信息傳播擴散等方面起到了不可忽視的作用。伴隨移動社交網絡節點的增長，核心節點作為信源，其傳播影響作用不容小覷，其中影響力最大化研究能夠對社會安防、市場營銷等領域起到重要作用，因此得到了不少學者的追捧。比如：Luo[1]等人基于冪定律法則的影響力分布下，提出了PageRank的啟發式算法來尋找種子節點；Chen[2]等人考慮節點的拓撲結構，提出了基于節點、最鄰近節點以及次近節點的多級鄰居指標的節點重要性排序；Wang[3]等人提出了基于社區發現求解影響力的CGA算法；郭進時[4]等人選取影響力傳播范圍和影響力傳播時延這兩個指標衡量節點的影響力，提出了社區結構的影響力最大化算法。在上述研究的基礎上，本文提出了基于社區劃分和改進PageRank的影響力最大化算法。該算法首先通過模塊度進行社區劃分，然后通過改進PageRank算法選取移動通信有向加權復雜網絡的種子節點，再利用KK算法局部最優的特性選取當前帶來最大影響范圍的剩余種子節點，以期盡可能地擴展算法的傳播影響范圍。

2 網絡影響力最大化研究

網絡影響力最大化這個問題要追溯到2002年，Richardson和Domings如何尋找社會網絡中最具影響力的成員，并發放免費樣品，通過這些最具影響力的成員口口相傳，使這些樣品的相關信息在社會網絡中順利傳播，以達到波及范圍廣和成本低廉的營銷目的。

影響力最大化初始定義是在所有網絡節點中選取最具有影響力的節點作為初始活躍節點，使其經過影響傳播，網絡最終被影響的節點數最多。但在實際應用過程中，處理網絡影響力的關鍵包括如下：

（1）在有限的資源下種子節點的選取問題；

（2）如何在節點的影響力信息的級聯下，通過貪心算法求出k個節點的影響力最大范圍。

傳統的種子節點選取使用靜態的啟發式節點選擇策略，一般采用度中心性、介數、緊密度等指標進行衡量，通過這些指標或者組合指標來確定節點的影響力，然后采用影響力排序的方法選取種子節點，以便實現網絡傳播最大化的目的；另外一種是動態的影響力最大化算法，首先構建網絡傳播模型，然后通過貪心算法求出最大傳播范圍的k個種子節點。

無論采取上述哪種算法，都有本身的缺陷。靜態啟發式的算法雖然處理速度較高、計算復雜度低，但是不能保證種子節點的傳播影響力最大化；貪心算法由于計算復雜度太高，所以并不擅長處理大型的復雜網絡。

因此，本文在總結上述兩種算法的優點的基礎上，結合社區劃分的方法、改進PageRank以及KK局部最優算法來解決有向加權復雜網絡影響力最大化的問題。

3 基于社區劃分和改進PageRank的影響

力最大化算法

3.1 有向加權復雜網絡模型

本文研究的數據是移動通信網絡的用戶業務數據，因此在介紹算法之前，必須先介紹移動通信網絡模型。

移動通信網絡模型可以認為是有向加權網絡，其模型可用G表示，G=（V， E）。其中，V表示網絡節點集合，可表示為V={v1， v2， …， vn}；E表示網絡有向邊集合，可表示為E={e1， e2， …， en}V×V。w（vi， vj）表示有向邊（vi， vj）的權值（或稱連接強度）。

3.2 基于模塊度的社區劃分方法

眾所周知，復雜網絡的節點之間的信息得以傳播是因為節點在某種程度上具有相似性。基于模塊度劃分社區的思想是社區內部的節點相似度較高，而在社區外部的節點相似度較低。因此，本文在社區劃分的基礎上，將社區的逐漸擴散等效于信息傳播的過程，借助于連接緊密的社區內部節點具有相似性這一思想，信息傳播在連接緊密的相似節點進行傳播。

3.4 KK算法

Kempe和Kleinberg首次采用一種貪心算法來解決社會網絡影響力最大化的問題，通過KK算法[8]來尋找種子節點組合。KK算法是一種局部最優的算法，通過遍歷每個節點的影響范圍，然后采用影響力降序的排名算法來挑選當前影響力最大范圍的節點作為種子節點，但是這種局部改進的算法并不能保證最終得到的種子節點的影響范圍最優。因此，本文采用改進PageRank算法來選擇k-[ck]個種子節點，然后通過節點來激活由模塊度劃分的重要社區，在激活階段利用貪心算法來選取剩余[ck]個種子節點。

其中，w（u，v）表示用戶v獲得用戶源u的邊權重。如果w（u，v）大于所設定的閾值，那么說明用戶v被激活。

根據上述步驟對劃分的重要社區進行激活節點的影響范圍計算，再對各個種子節點的影響范圍進行排序，進而確定最終的k個種子節點。

4 實驗分析

本文采用某市移動運營商的用戶通話數據，驗證基于社區劃分和改進PageRank的影響力最大化算法的有效性。該復雜網絡共由5 000個節點組成，有90 663條有向邊，有向邊表示用戶之間滿足特定的通話關系和通話時長的條件（一個月內大于4次通話，或每次平均通話時長約為30 s）。以用戶之間通話次數的比例乘以通話時長的比例作為權值。

首先對該數據進行社區劃分，得到8個社區；然后采用PageRank算法對每個社區進行用戶傳播能力排名，再用KK算法選擇剩余種子節點來激活的社區，最終算出每個社區的k（k≤10）個種子的影響范圍，得到每個社區選取的種子數量如表1所示。

通過上述結果可知，如果需要對該網絡選取10個種子，那么根據表1選取的種子用戶為15、101、19、132、187、55、199、54、34、487。

本文采用度中心性算法進行種子節點的選取，得到的影響節點數量與本文設計的算法進行對比，具體結果如圖1所示。

由圖1可知，采用基于社區劃分和改進PageRank的影響力最大化算法具有較大的傳播范圍。并且本文提出的算法與度中心性算法在不同規模的種子節點上的擴散速率是相吻合的，從而驗證了該算法的有效性。

5 結束語

本文提出了一種基于社區劃分的移動通信有向加權復雜網絡影響力最大化算法——基于社區劃分和改進PageRank的影響力最大化算法，與之前關于影響力最大化研究不同的是首先基于模塊度將移動通信網絡劃分成社區，實現了化整為零的效果，然后采用改進PageRank算法評估用戶傳播能力，并以此來選擇k-[ck]個種子節點，再利用KK算法挑選當前帶來最大影響范圍增量的剩余[ck]個種子節點，以達到影響力最大化的目標。經過實驗驗證了該算法的有效性和高效性，通過社區劃分能夠在一定程度上提高算法的效率，可以很好地適應大規模的社會網絡環境。

參考文獻：

[1] Luo Z L， Cai W D， Li Y J， et al. A PageRank-Based Heuristic Algorithm for Influence Maximization in the Social Network[C]//Recent Progress in Data Engineering and Internet Technology. Berlin Heidelberg： Springer， 2012： 485-490.

[2] Chen D， Lv L， Shang M， et al. Identifying influential nodes in complex networks[J]. Physica A Statistical Mechanics & Its Applications， 2012，391（4）： 1777-1787.

[3] Wang Y， Cong G， Song G， et al. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington， DC： ACM， 2010： 1039-1048.

[4] 郭進時，湯紅波，吳凱，等. 基于社區結構的影響力最大化算法[J]. 計算機應用， 2013，33（9）： 2436-2439.

[5] 張益. 一種定量評估復雜網絡節點重要度的算法[J]. 計算機工程， 2011，37（20）： 87-88.

[6] 李建華，汪曉鋒，吳鵬. 基于局部優化的社區發現方法研究現狀[J]. 中國科學院院刊， 2015，30（2）： 238-247.

[7] 張琨，李配配，朱保平，等. 基于PageRank的有向加權復雜網絡節點重要性評估方法[J]. 南京航空航天大學學報， 2013，45（3）： 429-434.

[8] Kempe D， Kleinberg J， Tardos E. Maximizing the spread of influence in a social network[C]//Proceeding of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM New York， 2003： 137-146.

[9] 王雙，李斌，劉學軍，等. 基于社區劃分的影響力最大化算法[J]. 計算機工程與應用， 2016，52（19）： 42-47.

[10] 吳萍. 移動社交網絡中的信息傳播最大化問題研究[D]. 濟南： 濟南大學， 2015.