張憲立，唐建新，曹來成

(蘭州理工大學 計算機與通信學院，蘭州 730050)

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，各種社交平臺不斷出現(xiàn)，如：Weibo、WeChat、Facebook等，這些社交平臺規(guī)模龐大，成為信息傳播的重要方式之一。同時，人與人之間的交互逐漸從線下轉(zhuǎn)移到線上，使得對傳統(tǒng)社交關系的獲取、追蹤更加容易，針對社會網(wǎng)絡的研究已經(jīng)成為一個熱點問題。其中，影響力最大化問題就是在網(wǎng)絡中尋找部分節(jié)點作為信息傳播的種子節(jié)點，使得信息的傳播范圍在網(wǎng)絡上最大化。研究該問題對于病毒式營銷具有重要的意義，考慮一家公司想要利用有限的資金在網(wǎng)絡上推廣它的產(chǎn)品，通過在網(wǎng)絡上選出部分有影響力的人，向他們提供一定的報酬，讓這些有影響力的人在網(wǎng)絡上推廣它的產(chǎn)品，使得網(wǎng)絡中更多的用戶知道，接受該產(chǎn)品，這就是影響力最大化。

Domingos等[1-2]首先將影響力最大化問題作為一個算法問題來研究。隨后，Kempe等[3]將該問題表示成離散的組合優(yōu)化問題，證明該問題在獨立級聯(lián)(Independent Cascade, IC)模型和線性閾值(Linear Threshold, LT)模型下是一個NP-hard問題，并提出一個貪心爬山算法，該算法的傳播范圍能夠達到最優(yōu)解的(1-1/e-ε)，其中e是自然對數(shù)，ε為誤差；然而貪心爬山算法利用蒙特卡洛模擬來評估節(jié)點的影響力，迭代選取影響力增益最大的節(jié)點，時間復雜度高，不適用于大規(guī)模網(wǎng)絡。

為了解決貪心算法的效率問題，Leskovec等[4]提出CELF(Cost-Effective Lazy-Forward)算法，該算法利用目標函數(shù)的子模特性，減少蒙特卡洛模擬的次數(shù)，實驗結(jié)果表明比貪心爬山算法快近700倍。Chen等[5]通過利用蒙特卡洛模擬的結(jié)果圖，提出NewGready和MixedGready，進一步優(yōu)化貪心算法。Cheng等[6]提出靜態(tài)貪婪算法StaticGready，時間效率提升兩個數(shù)量級?；跍p少蒙特卡洛模擬次數(shù)的思想，Ohsaka等[7]提出剪枝的蒙特卡洛(Pruned Monte-Carlo, PMC)模擬算法。上述基于貪心思想的改進算法，傳播范圍具有理論保證，但是依然需要蒙特卡洛模擬來計算節(jié)點的影響力，難以擴展到大規(guī)模網(wǎng)絡上。

針對貪心算法的低效性，一些學者提出大量的啟發(fā)式算法。Chen等[5]提出DegreeDiscount，該算法利用度中心性選擇種子節(jié)點，同時將種子節(jié)點的鄰居的度值打一定的折扣，實驗結(jié)果表明傳播范圍優(yōu)于度中心性算法；曹玖新等[8]提出一種基于k-核的啟發(fā)式算法——CCA(Core Covering Algorithm)；王雙等[9]提出一種基于社區(qū)的影響力最大化算法；楊書新等[10]介紹了一種基于度和影響力的混合啟發(fā)式(Degree and Influence Heuristic, DIH)算法。

李閱志等[11]提出一種基于獨立級聯(lián)模型的k-核過濾算法，該算法通過在k-核子圖上運行現(xiàn)有的影響力最大化算法，降低時間復雜度。李敏佳等[12]結(jié)合結(jié)構(gòu)洞和度折扣的優(yōu)勢，設計SHDD(Structure Hole and Degree Discount)算法。孫子力等[13]考慮信息傳播中的衰減現(xiàn)象，設計一種基于社群結(jié)構(gòu)的影響力最大化(Influence Maximization on Internal Decay, IMID)算法。這些基于啟發(fā)式的算法時間效率高，但是關于傳播范圍缺乏理論保證，沒有考慮傳播特性，在不同的網(wǎng)絡和傳播模型下傳播范圍不穩(wěn)定。

為了避免大量的蒙特卡洛模擬，Kimura等[14]提出基于傳播路徑的影響力算法——SPM(Shortest-Path Model)，該算法認為節(jié)點的影響力只在最短路徑之間傳播。進一步考慮傳播特性，Chen等[15]提出節(jié)點之間的影響力只在最大影響路徑上傳播，設計PMIA(Prefix excluding Maximum Influence Path)算法?？紤]所有傳播路徑，Kim等[16]提出IPA(Independent Path Algorithm)。Wu等[17]提出LAIM(Linear time iterative Approach for efficient Influence Maximization)，該算法首先基于多層鄰居迭代計算節(jié)點的影響力，然后利用貪心思想選擇影響力增益最大的節(jié)點。這類算法將影響力傳播限制在特殊的路徑上或者局部范圍來快速計算節(jié)點影響力，時間效率要優(yōu)于貪心算法，但是關于傳播范圍缺乏理論保證。

最近Borgs等[18]提出反向抽樣(Reverse Influence Sampling, RIS)的思想來解決影響力最大化問題，時間復雜度接近線性，傳播范圍具有理論保證。進一步，Tang等提出TIM/TIM+(Two-phase Influence Maximization)[19]、IMM(Influence Maximization based on Martingale)[20]等基于RIS思想的算法。Nguyen等[21]提出SSA(Stop-and-State Algorithm)和D-SSA(Dynamic Stop-and-State Algorithm)算法。Wang等[22]將抽樣順利引入RIS中，設計BKRIS(Bottom-K sketch based on Reverse Influence Sampling)算法。據(jù)悉，這類算法目前是解決影響力最大化問題最好的算法之一，能夠獲得高的傳播范圍，時間效率高，然而這類算法需要存儲大量的抽樣樣本，內(nèi)存消耗嚴重。

針對現(xiàn)有影響力最大化算法在大規(guī)模網(wǎng)絡上難以同時滿足傳播范圍、時間效率和空間效率的問題，本文首先介紹反向PageRank的思想，然后設計一種混合反向PageRank和度中心性的啟發(fā)式算法(heuristic algorithm of Mixed PageRank and Degree, MPRD)，最后為了避免選出的種子節(jié)點影響力傳播范圍重合，利用相似性方法過濾掉影響范圍重合嚴重的節(jié)點，進一步提高算法的傳播范圍。實驗結(jié)果表明,MPRD在傳播范圍上接近貪心算法和基于反向抽樣的算法，優(yōu)于現(xiàn)有的啟發(fā)式算法；在運行時間上比貪心算法提高四、五個數(shù)量級；同時在內(nèi)存消耗上優(yōu)于基于反向抽樣的算法。

1 背景知識

在本文中，網(wǎng)絡表示成圖G=(V,E),其中：V為節(jié)點集合，表示個體；E為邊集，表示個體之間的關系。

1.1 傳播模型

傳播模型就是描述信息在網(wǎng)絡中傳播的規(guī)則，本文主要介紹三種主流的影響力傳播模型：獨立級聯(lián)模型、權(quán)重級聯(lián)(Weighted Cascade, WC)模型和線性閾值模型[3]。在這些模型中，節(jié)點有激活和未激活兩種狀態(tài)，激活狀態(tài)表示該節(jié)點已經(jīng)接受信息，未激活狀態(tài)表明該節(jié)點沒有接受信息，即未被影響。同時，激活過程不可逆，節(jié)點只能從未激活狀態(tài)變?yōu)榧せ顮顟B(tài)。

1)獨立級聯(lián)模型和權(quán)重級聯(lián)模型。在獨立級聯(lián)模型中，初始在第0步只有種子集合S是激活狀態(tài)，即S0=S，對于在第t步激活的節(jié)點u∈St都有且僅有一次機會以puv的概率去激活u周圍未激活的每一個鄰居節(jié)點v，無論成功與否，u都不會再去激活v。當有多個激活節(jié)點嘗試去激活同一個節(jié)點時，激活過程是彼此獨立的，嘗試激活的順序是隨機的。當沒有更多的節(jié)點被激活，傳播過程結(jié)束。權(quán)重級聯(lián)模型是獨立級聯(lián)模型的一個特例，唯一的不同之處是節(jié)點激活概率puv在獨立級聯(lián)模型中通常是一個常數(shù)，如0.01,0.05等，而在權(quán)重級聯(lián)模型中puv設置如下：

(1)

1.2 問題定義

定義1 影響力最大化。給定一個網(wǎng)絡G=(V,E)，一個正整數(shù)k?|V|，影響力最大化問題就是從網(wǎng)絡中找出k個節(jié)點作為種子節(jié)點集合T，使得這些節(jié)點在某個傳播模型的影響力傳播范圍σ(T)最大化，表示如下：

(2)

其中：T為網(wǎng)絡中任意k個節(jié)點集合；S為選出的種子節(jié)點集合；σ(T)表示將T作為初始節(jié)點所能激活的預期節(jié)點數(shù)。

2 混合PageRank和Degree的影響力最大化算法

2.1 反向PageRank的思想

PageRank算法[23]是Google公司用來衡量網(wǎng)頁等級和重要性的一種方法，該方法的基本思想是一個網(wǎng)頁的重要性取決于指向它的其他頁面的數(shù)量和質(zhì)量。初始時給所有網(wǎng)頁賦一個初始的PageRank值PR，滿足式(3):

(3)

其中，n為網(wǎng)頁總數(shù)，然后將每個網(wǎng)頁的PageRank值迭代平均分配給其所指向的網(wǎng)頁。同時為了避免指向網(wǎng)頁為0的網(wǎng)頁始終將PageRank值分配給自己，設置一個比例因子α將每個節(jié)點的PageRank值進行縮減，再把1-α平均分配給每個網(wǎng)頁，以保持網(wǎng)絡總的PageRank值為1，即通過如式(4)進行迭代計算：

(4)

其中:Nin(u)表示指向網(wǎng)頁u的其他網(wǎng)頁集合;Nout(v)表示網(wǎng)頁v指向的其他網(wǎng)頁集合;相應的|Nout(v)|表示這個集合的大小;α通常設為0.85。當?shù)螖?shù)足夠多時，所有網(wǎng)頁的PageRank值將會收斂。

直接將PageRank算法應用到影響力最大化問題上通常傳播范圍有限，特別是在有向圖中。因為PageRank算法是尋找重要的節(jié)點，而影響力最大問題是尋找好的信息傳播源。受PageRank算法思想的啟發(fā)，一個節(jié)點的影響力不僅與其指向的節(jié)點數(shù)量有關(度中心性)，而且與其指向節(jié)點的質(zhì)量，即影響力有關。為此一個節(jié)點u的影響力Infu可以表示成該節(jié)點所指向的鄰居節(jié)點的影響力的和，即：

(5)

其中puv表示節(jié)點u激活節(jié)點v的概率。基于PageRank算法，為每一個節(jié)點分配一個初始的影響力，當更新一個節(jié)點的影響力時，應該將該節(jié)點所指向的每個節(jié)點的影響力按照一定的比例進行累加(如式(5))。換言之，每個節(jié)點應該將其影響力按照激活概率分配給它的入度鄰居，即反向PageRank的思想，影響力迭代計算如下：

(6)

其中:Nout(u)表示節(jié)點u的出度鄰居集合，prouv表示v的入度鄰居u激活v的概率在v的入度鄰居中所占的比例，如式(7)所示：

(7)

其中Nin(v)表示節(jié)點v的入度鄰居集合。

2.2 MPRD

實驗中發(fā)現(xiàn)反向PageRank算法在有向圖，權(quán)重級聯(lián)模型下傳播效果好，但是在無向圖或者獨立級聯(lián)模型下傳播范圍不穩(wěn)定。為了提高算法對于模型的魯棒性，本文結(jié)合反向PageRank和度中心算法，提出一種混合的啟發(fā)式算法MPRD。該算法首先利用反向PageRank的思想，計算節(jié)點的影響力(式(6))，然后將節(jié)點的度歸一化，使用如式(8)表示節(jié)點最終的影響力：

(8)

由于網(wǎng)絡的聚集效應，影響力高的節(jié)點經(jīng)常聚集在一起，形成富人俱樂部現(xiàn)象。啟發(fā)式算法選出的種子節(jié)點之間影響力范圍容易重合，使得總體的影響力傳播局限在網(wǎng)絡局部，導致算法的傳播范圍有限。為了減少選出的種子節(jié)點之間影響力重合，本文利用相似性方法[24]來去掉影響力重合嚴重的節(jié)點，進一步提高算法的傳播范圍。該相似性方法定義節(jié)點u的相似性Su如下:

(9)

其中:N(S)和N(u)分別表示種子集合S和節(jié)點u的一階鄰居;|N(S)∩N(u)|表示它們之間交集的大小，|N(u)|是節(jié)點u的一階鄰居數(shù)量。該方法在選擇種子節(jié)點時，先基于啟發(fā)式算法選出候選節(jié)點，然后計算該候選節(jié)點的相似性，如果相似性小于給定的閾值θ，則將該節(jié)點加入種子集合，否則丟棄，迭代選擇下一個節(jié)點。加入相似性方法，提出的MPRD的偽代碼如下。

輸入：網(wǎng)絡G，種子節(jié)點數(shù)k，調(diào)節(jié)參數(shù)s，比例因子α;相似性閾值θ。

輸出：選出的種子節(jié)點集合S。

1)

初始化操作

2)

迭代計算每個節(jié)點的影響力

3)

對每一個節(jié)點u計算

4)

fori=1 tokdo

5)

6)

7)

ifSu<θ

8)

S=S∪{u}

9)

end for

10)

returnS

其中n為網(wǎng)絡中的節(jié)點數(shù)目，MPRD首先初始化每一個節(jié)點的相似性和影響力值(第1)行)。然后基于反向PageRank的思想迭代計算每一個節(jié)點的影響力(第2)行)，接著結(jié)合度中心性和PageRank計算的影響力作為最終節(jié)點的影響力(3)行)。最后基于相似性方法，選出當前影響力值最大的節(jié)點計算其相似性，如果相似性小于設置的閾值，則將該節(jié)點加入種子集合；否則丟棄，繼續(xù)上述過程直到選出k個種子節(jié)點(行4)～10))。

算法復雜度分析 MPRD基于反向PageRank迭代計算節(jié)點的影響力，通過遍歷節(jié)點的入度和出度鄰居來計算分配的影響力，需要的時間為O(r*(n+m))，其中r表示迭代的次數(shù)，n和m分別表示網(wǎng)絡中節(jié)點的數(shù)目和邊的數(shù)目。使用堆來存儲節(jié)點影響力，選取種子節(jié)點需要的時間為O(nlogn+n*max_d)，其中max_d表示節(jié)點的最大度，因此算法總的時間復雜度為O((r+logn+max_d)*n+rm)。本文使用鄰接鏈表存儲網(wǎng)絡，MPRD的空間復雜度為O(n+m)。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)和算法

本文使用6個真實世界的數(shù)據(jù)集進行實驗，這些數(shù)據(jù)集都是來自由Jure Leskovec維護的網(wǎng)站(http://snap.stanford.edu/data/)。這些數(shù)據(jù)集從幾千節(jié)點到幾十萬節(jié)點，類型豐富，3個無權(quán)無向圖和3個無權(quán)有向圖，詳細信息如表1所示。

表1 6個真實世界數(shù)據(jù)集信息匯總 Tab.1 Information of six real-world datasets

本文將反向PageRank算法在有向圖上記作RPageRank，在無向圖中反向PageRank退化為PageRank，RPageRank迭代計算1 000次。在MPRD中，依據(jù)原作者建議設置α=0.85，相似性閾值θ=0.9。本文從傳播范圍、運行時間，內(nèi)存消耗三個方面來驗證所提算法的性能，并選擇如下6個富有代表性的算法在獨立級聯(lián)模型和權(quán)重級聯(lián)模型下進行對比實驗。算法的時間復雜度和空間復雜度如表2所示。

CELF 該算法利用目標函數(shù)的子模特性，減少蒙特卡洛模擬的次數(shù)，迭代選出影響力增益最大的節(jié)點作為種子節(jié)點，本文設置蒙特卡洛模擬次數(shù)R=10 000。

Degree 利用度中心性直接選出k個度值最大的節(jié)點作為種子節(jié)點。

PageRank 利用PageRank迭代1 000次計算節(jié)點的PR值，選擇k個PR值最大的節(jié)點。

PMC 基于剪枝的蒙特卡洛模擬算法，該算法基于節(jié)點的權(quán)重有向循環(huán)圖快速近似計算節(jié)點影響力增益，貪心思想選擇種子節(jié)點。

IMM 據(jù)我們所知，該算法是目前最好的算法之一。IMM基于反向抽樣的思想，具有近線性的時間復雜度，利用鞅分析計算達到理論保證所需要的樣本數(shù)量，本文設置ε=0.1，δ=0.01。

LAIM 該算法基于多層鄰居迭代計算節(jié)點的影響力，利用貪心思想選擇增益最大的節(jié)點，然后將選出的節(jié)點和相關的邊刪掉，重新計算節(jié)點的影響力。

表2 算法的時間復雜度和空間復雜度對比 Tab.2 Comparison of time complexity and space complexity of different algorithms

本文所有算法用C++編寫，在裝有Linux4.15系統(tǒng)的PC上運行，其硬件配置為3.6 GHz Inter i7- 4970處理器、8 GB內(nèi)存。

3.2 參數(shù)設置

本文計算的傳播范圍就是算法選出的種子節(jié)點在某個傳播模型下通過10 000次的蒙特卡洛模擬得出的最終網(wǎng)絡中的激活節(jié)點數(shù)目。圖1展示了MPRD選取50個種子節(jié)點在不同s值時，兩種傳播模型下傳播范圍對比的部分結(jié)果。從圖中可以看出，總體上在獨立級聯(lián)模型下，傳播范圍隨著s值的增加而不斷增加，當s=0.8時，傳播范圍在大部分網(wǎng)絡中能夠達到最大；而在權(quán)重級聯(lián)模型下，傳播范圍隨著s值的增加而不斷減少，當s=0.2時，傳播范圍在大部分網(wǎng)絡中能夠達到最大，因此，在本文中，在獨立級聯(lián)模型下設置s=0.8，在權(quán)重級聯(lián)模型下設置s=0.2。

圖1 不同s值的傳播范圍對比Fig. 1 Comparison of propagation range of different s values

3.3 傳播范圍對比

在傳播影響圖中，X軸表示種子節(jié)點數(shù)目，Y軸表示對應種子節(jié)點數(shù)下激活的節(jié)點數(shù)目。沒有特別說明，下文提到的百分比都是在k=50的情況下得出的。

圖2展示了不同算法在6個網(wǎng)絡上，在獨立級聯(lián)模型，傳播概率p=0.01的情況下，選擇50個種子節(jié)點的傳播范圍。從圖中可以發(fā)現(xiàn)，CELF算法總是取得最高的傳播范圍，提出的MPRD和IMM、Degree、PMC在除圖(c)之外的其他五個網(wǎng)絡上取得和CELF幾乎一樣的傳播范圍，而在圖(c)上，提出的MPRD傳播范圍僅僅比CELF少2.7%，但是優(yōu)于其他所有算法，例如MPRD比Degree、IMM、LAIM、PMC、PageRank的傳播范圍分別提高14.2%、2.4%、3%、4.8%、10.3%。IMM算法可能是參數(shù)設置太大導致傳播范圍不理想，需要說明的是IMM在圖(a)上由于內(nèi)存消耗太大沒有進行實驗。

圖2 IC模型下傳播范圍對比(p=0.01)Fig. 2 Comparison of propagation range under IC model(p=0.01)

PageRank算法在所有的網(wǎng)絡上總是表現(xiàn)很差，但是RPageRank在(d)、(e)、(f)三個有向圖上傳播范圍接近最優(yōu)的算法，表明反向PageRank思想的有效性。需要說明的是LAIM算法只適用于無向圖，從結(jié)果可以發(fā)現(xiàn)，這種基于局部鄰居迭代計算節(jié)點影響力的方法并不準確，在(a)、(b)和(c)上比最優(yōu)的CELF傳播范圍分別低29%、4.7%、5.6%?？傊?，從IC模型的傳播影響圖上，證明提出的反向PageRank思想在有向圖上能夠取得高的傳播范圍，提出的MPRD在傳播范圍上接近CELF算法，優(yōu)于其他所有算法。

圖3為不同算法在6個真實網(wǎng)絡中WC模型下的傳播范圍。

圖3 WC模型下傳播范圍對比Fig. 3 Comparison of propagation range under WC model

從圖3中可以看出，提出的MPRD和CELF、IMM、PMC在所有的網(wǎng)絡上幾乎都取得最高的傳播范圍。Degree算法在6個數(shù)據(jù)集上的傳播范圍都低于MPRD，例如在(a)、(b)、(c)、(e)上比MPRD的傳播范圍低7.4%、15.7%、22.6%、8.7%。PageRank算法在(a)和(b)上傳播范圍接近CELF算法，但是在其他4個網(wǎng)絡上表現(xiàn)較差，表明該算法的不穩(wěn)定性；然而RPageRank算法在(d)、(e)、(f)三個有向圖上傳播范圍接近CELF算法，表明RPageRank算法在有向圖，WC模型下的有效性。LAIM算法在(b)和(c)上選取50個節(jié)點的傳播范圍接近最優(yōu)算法，但是在其他種子節(jié)點數(shù)目下表現(xiàn)不穩(wěn)定，例如在(c)上選擇10個種子節(jié)點的傳播范圍比CELF低28.2%。

總之，實驗結(jié)果表明，RPageRank算法在有向圖上的傳播范圍接近最優(yōu)算法，提出的MPRD在所有的網(wǎng)絡上，兩種傳播模型下都能和當前最優(yōu)的CELF取得接近的傳播范圍，而優(yōu)于其他算法，證明混合反向PageRank和度中心性的MPRD對于網(wǎng)絡和模型的魯棒性。從結(jié)果也可以看出，Degree算法在IC模型下表現(xiàn)良好，但是在WC模型下表現(xiàn)一般，因此在IC模型下s的值設置較大，MPRD偏向選擇度大的節(jié)，而在WC模型下s的值較小，算法偏向選擇反向PageRank值大的節(jié)點，綜合兩者的優(yōu)勢，提出的MPRD在傳播范圍上表現(xiàn)穩(wěn)定。

3.4 運行時間對比

圖4顯示了不同算法在6個網(wǎng)絡，兩種傳播模型下，選擇50個種子節(jié)點所需要的時間。X軸表示不同網(wǎng)絡和算法，Y軸表示以10為底的對數(shù)坐標下的運行時間。提出的MPRD和RPageRank和PageRank運行時間相似，統(tǒng)一記作MRPD。從圖中可以看出：CELF算法的運行時間遠遠高于其他算法，例如在CA-HepPh網(wǎng)絡，IC模型下，CELF需要53 144 s，而本文提出的MPRD只需要2.2 s。Degree是運行最快的算法，而提出的MPRD的運行時間和其他算法類似，都略高于Degree。除CELF之外的所有算法在所有的網(wǎng)絡，兩種傳播模型下，運行時間都在100 s之內(nèi)，遠遠優(yōu)于CELF算法，表明這些算法能夠處理大規(guī)模的網(wǎng)絡。

圖4 不同算法在兩種模型上的運行時間對比Fig. 4 Running time comparison of different algorithms on two models

3.5 運行空間對比

圖5展示了不同算法在6個網(wǎng)絡，兩種傳播模型下，選擇50個種子節(jié)點需要的內(nèi)存空間，X軸表示網(wǎng)絡和算法，Y軸表示內(nèi)存消耗。從圖中可以看出IMM和PMC都是內(nèi)存消耗的算法，例如在email網(wǎng)絡，IC模型下，IMM和PMC分別需要2.3 GB和1.4 GB內(nèi)存，而本文提出的MPRD只需要0.099 GB內(nèi)存，而且IMM算法在dblp網(wǎng)絡，IC模型下由于內(nèi)存消耗超過機器內(nèi)存而沒有進行實驗。通過內(nèi)存空間對比，證明本文的MPRD相比IMM和PMC，在內(nèi)存消耗方面更容易擴展到大規(guī)模的網(wǎng)絡上。

圖5 不同算法在兩種模型上的運行空間對比Fig. 5 Memory usage comparison of different algorithms on two models

通過在6個網(wǎng)絡，兩種傳播模型下，將提出的MPRD與CELF、Degree、PageRank、IMM、LAIM、PMC 6種算法從傳播范圍、運行時間、運行空間三個方面進行對比實驗。結(jié)果表明提出MPRD：在傳播范圍上接近最優(yōu)的CELF算法；但是時間效率上與其他算法接近，比CELF快四、五個數(shù)量級；內(nèi)存消耗上比IMM，PMC更容易擴展到大規(guī)模網(wǎng)絡上?？傊?，提出的MPRD能夠在傳播范圍、時間效率和內(nèi)存消耗三個方面取得良好的平衡，能夠擴展到大規(guī)模網(wǎng)絡上。

4 結(jié)語

本文提出一種混合反向PageRank和度中心性的啟發(fā)式算法MPRD來解決大規(guī)模網(wǎng)絡上影響力最大化問題。該算法從啟發(fā)式算法的角度，結(jié)合反向PageRank和度中心性評估節(jié)點影響力，然后使用相似性方法選擇種子節(jié)點。實驗結(jié)果表明所提出的MPRD在傳播范圍上接近最優(yōu)的算法，而且時間效率高，內(nèi)存消耗小。該算法不足之處是參數(shù)太多。接下來的工作將從以下幾個方面進行。首先，不同網(wǎng)絡中最優(yōu)的s是不同的，在IC模型中設置為0.8，WC模型中設置0.2只是大多數(shù)情況下最優(yōu)的選擇，未來將探索最優(yōu)的s值與網(wǎng)絡特性之間的關系，為不同網(wǎng)絡設置更合理的s值；其次，將探索MPRD在其他模型下的表現(xiàn)，例如LT模型和投票模型；最后將在網(wǎng)絡中加入主題信息，探索更實用的影響力最大化算法。