基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法

吳海林

【摘 要】為了解決傳統(tǒng)貪心算法不能有效解決大規(guī)模社會網(wǎng)絡(luò)影響力最大化的效率問題，采用模塊度將大規(guī)模的通信網(wǎng)絡(luò)劃分成較小的社區(qū)模塊，并通過改進(jìn)PageRank排名算法來評價(jià)有向復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的傳播能力，然后再利用KK算法挑選當(dāng)前帶來最大影響范圍的剩余種子節(jié)點(diǎn)，提出基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法。實(shí)驗(yàn)證明，該方法具有一定的擴(kuò)展性和有效性。

【關(guān)鍵詞】社區(qū)劃分 改進(jìn)PageRank KK算法 影響力最大化 傳播能力

1 引言

隨著各類移動(dòng)社交服務(wù)如Facebook、Twitter、微博、微信、QQ等對人類生活、社交的滲透，社交網(wǎng)絡(luò)在信息溝通、信息共享、信息傳播擴(kuò)散等方面起到了不可忽視的作用。伴隨移動(dòng)社交網(wǎng)絡(luò)節(jié)點(diǎn)的增長，核心節(jié)點(diǎn)作為信源，其傳播影響作用不容小覷，其中影響力最大化研究能夠?qū)ι鐣卜?、市場營銷等領(lǐng)域起到重要作用，因此得到了不少學(xué)者的追捧。比如：Luo[1]等人基于冪定律法則的影響力分布下，提出了PageRank的啟發(fā)式算法來尋找種子節(jié)點(diǎn)；Chen[2]等人考慮節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，提出了基于節(jié)點(diǎn)、最鄰近節(jié)點(diǎn)以及次近節(jié)點(diǎn)的多級鄰居指標(biāo)的節(jié)點(diǎn)重要性排序；Wang[3]等人提出了基于社區(qū)發(fā)現(xiàn)求解影響力的CGA算法；郭進(jìn)時(shí)[4]等人選取影響力傳播范圍和影響力傳播時(shí)延這兩個(gè)指標(biāo)衡量節(jié)點(diǎn)的影響力，提出了社區(qū)結(jié)構(gòu)的影響力最大化算法。在上述研究的基礎(chǔ)上，本文提出了基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法。該算法首先通過模塊度進(jìn)行社區(qū)劃分，然后通過改進(jìn)PageRank算法選取移動(dòng)通信有向加權(quán)復(fù)雜網(wǎng)絡(luò)的種子節(jié)點(diǎn)，再利用KK算法局部最優(yōu)的特性選取當(dāng)前帶來最大影響范圍的剩余種子節(jié)點(diǎn)，以期盡可能地?cái)U(kuò)展算法的傳播影響范圍。

2 網(wǎng)絡(luò)影響力最大化研究

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

影響力最大化初始定義是在所有網(wǎng)絡(luò)節(jié)點(diǎn)中選取最具有影響力的節(jié)點(diǎn)作為初始活躍節(jié)點(diǎn)，使其經(jīng)過影響傳播，網(wǎng)絡(luò)最終被影響的節(jié)點(diǎn)數(shù)最多。但在實(shí)際應(yīng)用過程中，處理網(wǎng)絡(luò)影響力的關(guān)鍵包括如下：

（1）在有限的資源下種子節(jié)點(diǎn)的選取問題；

（2）如何在節(jié)點(diǎn)的影響力信息的級聯(lián)下，通過貪心算法求出k個(gè)節(jié)點(diǎn)的影響力最大范圍。

傳統(tǒng)的種子節(jié)點(diǎn)選取使用靜態(tài)的啟發(fā)式節(jié)點(diǎn)選擇策略，一般采用度中心性、介數(shù)、緊密度等指標(biāo)進(jìn)行衡量，通過這些指標(biāo)或者組合指標(biāo)來確定節(jié)點(diǎn)的影響力，然后采用影響力排序的方法選取種子節(jié)點(diǎn)，以便實(shí)現(xiàn)網(wǎng)絡(luò)傳播最大化的目的；另外一種是動(dòng)態(tài)的影響力最大化算法，首先構(gòu)建網(wǎng)絡(luò)傳播模型，然后通過貪心算法求出最大傳播范圍的k個(gè)種子節(jié)點(diǎn)。

無論采取上述哪種算法，都有本身的缺陷。靜態(tài)啟發(fā)式的算法雖然處理速度較高、計(jì)算復(fù)雜度低，但是不能保證種子節(jié)點(diǎn)的傳播影響力最大化；貪心算法由于計(jì)算復(fù)雜度太高，所以并不擅長處理大型的復(fù)雜網(wǎng)絡(luò)。

因此，本文在總結(jié)上述兩種算法的優(yōu)點(diǎn)的基礎(chǔ)上，結(jié)合社區(qū)劃分的方法、改進(jìn)PageRank以及KK局部最優(yōu)算法來解決有向加權(quán)復(fù)雜網(wǎng)絡(luò)影響力最大化的問題。

3 基于社區(qū)劃分和改進(jìn)PageRank的影響

力最大化算法

3.1 有向加權(quán)復(fù)雜網(wǎng)絡(luò)模型

本文研究的數(shù)據(jù)是移動(dòng)通信網(wǎng)絡(luò)的用戶業(yè)務(wù)數(shù)據(jù)，因此在介紹算法之前，必須先介紹移動(dòng)通信網(wǎng)絡(luò)模型。

移動(dòng)通信網(wǎng)絡(luò)模型可以認(rèn)為是有向加權(quán)網(wǎng)絡(luò)，其模型可用G表示，G=（V， E）。其中，V表示網(wǎng)絡(luò)節(jié)點(diǎn)集合，可表示為V={v1， v2， …， vn}；E表示網(wǎng)絡(luò)有向邊集合，可表示為E={e1， e2， …， en}V×V。w（vi， vj）表示有向邊（vi， vj）的權(quán)值（或稱連接強(qiáng)度）。

3.2 基于模塊度的社區(qū)劃分方法

眾所周知，復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)之間的信息得以傳播是因?yàn)楣?jié)點(diǎn)在某種程度上具有相似性?；谀K度劃分社區(qū)的思想是社區(qū)內(nèi)部的節(jié)點(diǎn)相似度較高，而在社區(qū)外部的節(jié)點(diǎn)相似度較低。因此，本文在社區(qū)劃分的基礎(chǔ)上，將社區(qū)的逐漸擴(kuò)散等效于信息傳播的過程，借助于連接緊密的社區(qū)內(nèi)部節(jié)點(diǎn)具有相似性這一思想，信息傳播在連接緊密的相似節(jié)點(diǎn)進(jìn)行傳播。

3.4 KK算法

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

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

根據(jù)上述步驟對劃分的重要社區(qū)進(jìn)行激活節(jié)點(diǎn)的影響范圍計(jì)算，再對各個(gè)種子節(jié)點(diǎn)的影響范圍進(jìn)行排序，進(jìn)而確定最終的k個(gè)種子節(jié)點(diǎn)。

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

本文采用某市移動(dòng)運(yùn)營商的用戶通話數(shù)據(jù)，驗(yàn)證基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法的有效性。該復(fù)雜網(wǎng)絡(luò)共由5 000個(gè)節(jié)點(diǎn)組成，有90 663條有向邊，有向邊表示用戶之間滿足特定的通話關(guān)系和通話時(shí)長的條件（一個(gè)月內(nèi)大于4次通話，或每次平均通話時(shí)長約為30 s）。以用戶之間通話次數(shù)的比例乘以通話時(shí)長的比例作為權(quán)值。

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

通過上述結(jié)果可知，如果需要對該網(wǎng)絡(luò)選取10個(gè)種子，那么根據(jù)表1選取的種子用戶為15、101、19、132、187、55、199、54、34、487。

本文采用度中心性算法進(jìn)行種子節(jié)點(diǎn)的選取，得到的影響節(jié)點(diǎn)數(shù)量與本文設(shè)計(jì)的算法進(jìn)行對比，具體結(jié)果如圖1所示。

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

5 結(jié)束語

本文提出了一種基于社區(qū)劃分的移動(dòng)通信有向加權(quán)復(fù)雜網(wǎng)絡(luò)影響力最大化算法——基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法，與之前關(guān)于影響力最大化研究不同的是首先基于模塊度將移動(dòng)通信網(wǎng)絡(luò)劃分成社區(qū)，實(shí)現(xiàn)了化整為零的效果，然后采用改進(jìn)PageRank算法評估用戶傳播能力，并以此來選擇k-[ck]個(gè)種子節(jié)點(diǎn)，再利用KK算法挑選當(dāng)前帶來最大影響范圍增量的剩余[ck]個(gè)種子節(jié)點(diǎn)，以達(dá)到影響力最大化的目標(biāo)。經(jīng)過實(shí)驗(yàn)驗(yàn)證了該算法的有效性和高效性，通過社區(qū)劃分能夠在一定程度上提高算法的效率，可以很好地適應(yīng)大規(guī)模的社會網(wǎng)絡(luò)環(huán)境。

參考文獻(xiàn)：

[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ìn)時(shí)，湯紅波，吳凱，等. 基于社區(qū)結(jié)構(gòu)的影響力最大化算法[J]. 計(jì)算機(jī)應(yīng)用， 2013，33（9）： 2436-2439.

[5] 張益. 一種定量評估復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度的算法[J]. 計(jì)算機(jī)工程， 2011，37（20）： 87-88.

[6] 李建華，汪曉鋒，吳鵬. 基于局部優(yōu)化的社區(qū)發(fā)現(xiàn)方法研究現(xiàn)狀[J]. 中國科學(xué)院院刊， 2015，30（2）： 238-247.

[7] 張琨，李配配，朱保平，等. 基于PageRank的有向加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估方法[J]. 南京航空航天大學(xué)學(xué)報(bào)， 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] 王雙，李斌，劉學(xué)軍，等. 基于社區(qū)劃分的影響力最大化算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2016，52（19）： 42-47.

[10] 吳萍. 移動(dòng)社交網(wǎng)絡(luò)中的信息傳播最大化問題研究[D]. 濟(jì)南： 濟(jì)南大學(xué)， 2015.