成本控制下的快速影響最大化算法

劉院英，郭景峰，魏立東，胡心專

(1.燕山大學 信息科學與工程學院，河北 秦皇島 066004； 2.河北經(jīng)貿大學 信息技術學院，石家莊 050061)

(*通信作者電子郵箱slt115@126.com)

成本控制下的快速影響最大化算法

劉院英1,2*，郭景峰1，魏立東2，胡心專1

(1.燕山大學 信息科學與工程學院，河北 秦皇島 066004； 2.河北經(jīng)貿大學 信息技術學院，石家莊 050061)

(*通信作者電子郵箱slt115@126.com)

針對成本控制下影響最大化時間復雜度高的問題，提出一種快速的最大化算法BCIM。首先提出對初始節(jié)點進行多次傳播的傳播模型；其次選擇高影響力節(jié)點作為備用種子，并基于近距離影響減少計算節(jié)點影響范圍的工作量；最后利用動態(tài)規(guī)劃方法在每組備用種子中最多選擇一個種子。仿真實驗表明，與隨機算法Random、每輪取影響力增量最大的節(jié)點的貪心算法Greedy_MII、每輪取影響力增量與成本比值最大的節(jié)點的貪心算法Greedy_MICR相比，在影響范圍上，BICM接近或優(yōu)于Greedy_MICR及Greedy_MII，遠次于Random；在種子集合的質量上，BCIM、Greedy_MICR、Greedy_MII三者差距較小，但都遠遠好于Random；在運行時間上，BCIM是Random的幾倍，而兩個貪心算法都是BCIM的幾百倍。BCIM算法能在較短時間內找到更有效的種子集合。

影響最大化；在線社會網(wǎng)絡；成本控制；動態(tài)規(guī)劃；多次傳播模型

0 引言

社會網(wǎng)絡上的信息傳播大都基于“病毒式營銷”?！安《臼綘I銷”指的是當一個人接受了某種思想或購買了某種產(chǎn)品后，他會把這種信息傳播給他的朋友，他的朋友亦會再告訴自己的朋友，這種信息傳播方式能夠影響用戶的決策、購買等行為。

影響最大化問題是Domingos等[1]最先提出的，它定義為如何尋找K個初始節(jié)點，使得信息的最終傳播范圍最廣。Kempe等[2-3]第一次將最大化問題歸納為離散最優(yōu)化問題，并且證明了求最優(yōu)解是一個NP難問題，他們提出采用貪心算法求解，即每一步采用當前最優(yōu)解作為種子。針對貪心算法的時間復雜度非常高這一問題，后來的研究者又提出若干改進算法，如CELF(Cost-EffectiveLazyForward)算法[4]、新貪心算法NewGreedyIC[5]、混合貪心算法MixGreedyIC[5]等。雖然這些算法較貪心算法有所改進，但時間復雜度依然很高，無法適用于大型網(wǎng)絡。Chen等[6]提出了信息沿著最大生成樹傳播的MIA(MaximumInfluenceArborescence)算法，并將節(jié)點的影響范圍局限在以節(jié)點為根的局部樹狀結構中。本文在計算節(jié)點的影響力時認為影響只沿最短路徑傳播。

以前的研究沒有考慮營銷活動中的費用問題。實際上，在營銷活動中，商家往往采用支付廣告費用、贈送產(chǎn)品、打折等形式來激勵客戶的傳播積極性，這個過程需要一定的成本，所以商家會有意識地選擇某些“性價比”高的客戶進行廣告投放，以期通過用戶的影響力達到廣泛擴散信息的目的。針對這一目標，Zhan等[7]采用CELF算法思路，每次將影響增量與節(jié)點費用比值最大的節(jié)點納入種子集合。Wang等[8]采用貪心算法思路，選取四種不同類型的種子集合，分別是成本最低的、影響范圍最大的、影響范圍與成本比值最大的，以及成本與傳播增量比值最大的。上述算法都基于貪心算法來解決問題，時間復雜度高。為了降低時間復雜度，本文采用動態(tài)規(guī)劃的思路來解決問題。

在影響最大化領域，經(jīng)常采用的信息傳播模型是獨立級聯(lián)(IndependentCascade，IC)模型，該模型中假設種子節(jié)點和非種子節(jié)點都只能進行一次信息傳播。而在市場營銷活動中，得到一定經(jīng)濟利益的初始用戶會進行多次信息傳播，非初始用戶則只進行一次信息傳播。另外，Alon等[9]也提出，當初始用戶得到k份費用時，他就會向他的鄰居進行k次信息傳播。顯然，IC模型不適用于成本控制下的信息傳播情況，所以本文在IC模型的基礎上提出了初始節(jié)點進行多次傳播的MTIC(MultipleTransmissionmodelbasedonIC)模型，并證明了該模型具有單調性和子模性。Kempe等[2-3]已經(jīng)證明了具有子模性的影響范圍函數(shù)使用貪心算法求解，能取得最優(yōu)解的63%。

為解決基于成本的影響最大化問題，本文給出了綜合考慮成本預算和節(jié)點初始激活費用的最大化算法BCIM(InfluenceMaximizationwithBudgetandnodeCost)。此算法的基本思路是把節(jié)點分為若干組，按照動態(tài)分配的思路在每一組中選擇一個種子。為了提高程序的運行速度，從以下兩個方面進行優(yōu)化：1)將PageRank[10]排名靠前的節(jié)點選作備用種子節(jié)點，減少種子節(jié)點的搜索范圍；2)在計算節(jié)點的影響范圍時，只考慮此節(jié)點對它近距離鄰居的影響值，減少計算工作量。

1 傳播模型

定義1 設圖G=(V,E)表示一個社會網(wǎng)絡，其中：V表示節(jié)點集合，?v∈V表示節(jié)點；E表示邊集，?e(u,v)∈E表示節(jié)點u和v之間的關系。如果e(u,v)∈E，則u試圖激活v的概率用p(u,v)表示。

定義2 給定圖G=(V,E)，種子集合S?V，初始節(jié)點進行多次信息傳播的模型MTIC的工作過程如下：在t=0時，?s∈S會激活它的鄰居節(jié)點Num(s)次，每一次激活都是獨立的；當t≥1時，在t-1時刻被激活的節(jié)點會激活它的非活躍鄰居節(jié)點一次，此過程會級聯(lián)下去，直到?jīng)]有新節(jié)點被激活為止。整個激活過程中，節(jié)點u對節(jié)點v的激活概率為p(u,v)。節(jié)點一旦被激活，就會一直保持活躍狀態(tài)。

定理1 在社會網(wǎng)絡中采用MTIC模型進行信息傳播時，信息傳播影響范圍函數(shù)σ(·)具有單調性和子模性。

單調性指的是對于圖G=(V,E)，當A?V，v∈G且v?A時，有σ(A+v)≥σ(A)。

子模性指的是對于圖G，當S1?S2?V，且v?S2時，有σ(S1∪{v})-σ(S1)≥σ(S2∪{v})-σ(S2)。

Kempe等[2-3]已經(jīng)證明了IC模型上的信息傳播范圍函數(shù)σ(·)具有子模性。

證明 在任意圖G=(V,E)上用MTIC模型進行信息傳播是一個隨機事件。在實驗之前，將G分為兩部分G1和G2。其中：G1是圖G刪除節(jié)點集T及其所在邊形成的子圖；G2是節(jié)點集合T及其直接鄰居形成的子圖。

下面形成G1、G2中進行信息傳播的樣本空間。

對于G1中的任意邊(u1，v1)，u1將以概率p激活v1。在每一次可能的結果中，若v1被激活，則在u1和v1之間保留一條邊；否則，u1和v1之間沒有邊。每一個可能的結果就是一個樣本點，也是G1的一個子圖G1i。子圖中包含G1的所有節(jié)點和某些邊。所有的樣本點組成樣本空間X1：{G11,G12,G13，…}。

令T為初始節(jié)點集合，由于T中節(jié)點對其鄰居的影響次數(shù)為多次，所以在G2中求樣本點時都按如下方法設置：T中的某個節(jié)點u2對其鄰居v2進行多次激活時，只要有一次成功了，就認為在u2和v2之間存在一條邊。這些樣本點是G2的子圖G2i。所有的樣本點組成樣本空間X2：{G21,G22,G23，…}。

令X1和X2進行笛卡爾乘積，得到總的樣本空間X3={(G1i,G2j)|G1i∈X1,G2j∈X2}。對X3中的每個樣本點，把圖G1i和G2j合并成一個圖：把編號相同的節(jié)點看成是一個節(jié)點，把所有的邊都保留下來。這樣形成了樣本空間X。

現(xiàn)在取樣本空間X的一個樣本點x，令：σx(U)表示從節(jié)點集合U出發(fā)，能到達的節(jié)點集合的大小；R(v,x)表示從節(jié)點v出發(fā)能夠達到的節(jié)點集合，所以有:

1)證明在樣本點x上的單調性。

當A?T，v∈T且v?A時，用Rx1表示在樣本x上集合A影響到的節(jié)點集合，Rx2表示在樣本x上節(jié)點v影響到的節(jié)點集合。若Rx1∩Rx2=?，則σx(A+{v})=σx(A)+σx(v)，所以σx(A+{v})≥σx(A)；若Rx1∩Rx2≠?，則顯然σx(A+{v})≥σx(A)，得證。

2)證明在樣本點x上的子模性。

σ(S)是在整個樣本空間上求得，是所有樣本點上取值σx(S)的非負線性組合，所以σ(S)具有單調性和子模性。

2 問題定義

在營銷活動中，商家需要支付一定的成本費用；另外，向不同的客戶投放信息時，由于客戶的社會地位、知名度等原因的不同，所需費用也會不同。

定義3 在圖G=(V,E)中，假設B是給定的成本預算，Cost(u)表示商家為了使u接受某種產(chǎn)品或觀念所需付出的費用，S是種子集合，σ(S)是S的最終影響范圍，成本B控制下的影響最大化(Influence Maximization with Budget, BIM)定義為：

當每個節(jié)點的成本為1時，BIM問題就是傳統(tǒng)的社會網(wǎng)絡影響最大化問題。由于傳統(tǒng)的社會網(wǎng)絡影響最大化是NP難問題[2-3]，所以BIM也是NP難問題。

定義4 當以Cost(u)表示節(jié)點的費用，Degree(u)表示u的鄰居數(shù)時，u進行信息傳播的次數(shù)Num(u)定義為：

Num(u)=γ·Cost(u)/Degree(u)

(1)

其中γ是比例系數(shù)。

定理2 設w的入邊鄰居集合為Nin(v)，u的活躍概率為p(u)，從節(jié)點a出發(fā)經(jīng)過l步可達的節(jié)點集合為Tl(a)，則節(jié)點a對所有可達節(jié)點的預期影響值之和為:

inf(a)=

(2)

當u=a時，p(u)=1；T0(a)=a。

因此，節(jié)點a對所有可達節(jié)點的影響值之和為：

圖1給出的是節(jié)點A以及它的鄰居節(jié)點，當計算A的影響力時，節(jié)點B和C屬于T1(a)，節(jié)點D、E、F屬于T2(a)?；诤竺嫣岬降慕嚯x影響法，忽略邊(B,C)和(D,E)的影響。

圖1 節(jié)點A以及A的鄰居

定義5 對于圖G=(V,E)，假設G′=(CS,E′)，其中CS?V，E′?E。對于?u∈CS，group′(u)={u}∪{v|(u,v)∈E′}，則group(w)定義為：

group(w)∈{group′(u)|u∈CS}

根據(jù)定義5可以得出，分組group(w)中任意兩個節(jié)點u和v之間的距離不大于2。

3 影響最大化算法

3.1 貪心算法

本文給出了兩種貪心算法：1)在成本允許的情況下，每一步選取當前最具影響力的節(jié)點加入種子集合，稱為Greedy_MII，如算法1所示；2)在成本允許的前提下，每一步選取影響力與節(jié)點費用比值最大的節(jié)點加入種子集合，稱為Greedy_MICR，如算法2所示。

算法1Greedy_MII。

輸入G=(V,E)，成本B，節(jié)點費用C={Cost(i)|i∈V}；

輸出 種子集合S。

1)

S=?

2)

WhileB≥0

3)

V′={v|v∈V-SandCost(v)≤B}

4)

for each nodewinV′ do

5)

sw=0

6)

fori=1 toRdo

7)

sw+=σ(S∪{w})-σ(S)

8)

sw=sw/R

9)

10)

S=S ∪{u}

11)

B=B-Cost(u)

12)

OutputS

算法2Greedy_MICR

輸入G=(V,E)，成本B，節(jié)點費用C={Cost(i)|i∈V}；

輸出 種子集合S。

1)

S=?

2)

WhileB≥0

3)

V′={v|v∈V-SandCost(v)≤B}

4)

foreachnodewinV′do

5)

sw=0

6)

fori=1toRdo

7)

sw+=σ(S ∪{w})-σ(S)

8)

sw=sw/R

9)

10)

S=S∪ {u}

11)

B=B-Cost(u)

12)

OutputS

以上兩個算法的最大缺點是效率低，原因主要有兩點：1)每一步都要搜索V-S中的每個滿足成本要求的節(jié)點；2)求每個節(jié)點的邊際收益時，采用蒙特卡羅模擬法計算σ(·)需要重復計算R次，而R取值一般是10 000。

3.2 BCIM算法

3.2.1 減少搜索范圍

社會網(wǎng)絡中，有影響力的用戶或者意見領袖的言論更能影響他人。微博環(huán)境下，新用戶加入網(wǎng)絡時，也往往選擇大V進行關注。在線社會網(wǎng)絡通常采用PageRank值表示用戶的影響力排名，一般認為該值越大，用戶的影響力就越強[11]。

網(wǎng)絡中除了一部分有影響力的用戶之外，還存在大量的低影響力甚至沒什么影響力的用戶。在進行信息傳播時，這部分用戶幾乎沒有什么貢獻，所以不能作為種子。為了縮小種子的搜索范圍，選擇有影響力的用戶加入備用種子集合。

3.2.2 減少計算工作量

式(2)計算的是任意節(jié)點a對所有可達節(jié)點的影響力之和，在計算時需要遍歷整個網(wǎng)絡，計算量很大。為了減少計算工作量，提出近距離影響思路。

3.2.3BCIM算法實現(xiàn)

步驟1 計算每個節(jié)點的PageRank排名，然后按比例選取排名靠前的節(jié)點加入備用種子集合。

步驟2 按照定義5，把備用種子集合劃分為若干組。由于同一組內的節(jié)點之間距離不超過2，所以組內節(jié)點之間的相互影響力很強。

步驟3 在每組中最多選取一個節(jié)點作為種子。由于組內用戶相互影響力很強，且種子節(jié)點能進行多次傳播，所以組內其他節(jié)點被激活的概率會很高。被選作種子的節(jié)點必須滿足兩個條件：1)所有種子節(jié)點的費用之和不能超過成本預算B；2)種子集合的信息傳播范圍最廣。選擇種子的策略可以用以下表達式來描述：

f[k][b]=max{f[k-1][b],

f[k-1][b-Cost(v)]+σ(v)|v∈group(k)}

(3)

其中：f[k][b]表示當成本是b時，在前k個分組中尋找到的種子集合的信息傳播范圍；Cost(v)表示節(jié)點v的費用；σ(v)表示節(jié)點v的信息傳播范圍。

此問題可以轉換為在成本為b時，是否在第k個分組中尋找種子節(jié)點。如果在成本b的控制下，在前k-1個分組中尋找的種子集合的影響范圍大于在前k個分組中尋找的種子集合的影響范圍，則在前k-1個分組中尋找，函數(shù)變?yōu)閒[k-1][b]；否則，將在第k個分組中尋找一個種子v，然后在前k-1個分組中尋找剩余的種子節(jié)點，此時的成本預算值需要減去v的費用Cost(v)，整個種子集合的信息范圍需要加上節(jié)點v的傳播范圍σ(v)。

BCIM算法如算法3所示。

算法3BCIM。

輸入G=(V,E)，成本B，節(jié)點費用C={Cost(i)|i∈V}；

輸出 種子集合S。

1)

computePageRankofeverynode

2)

computespreadtimesofeverynode

3)

selecthighPageRankvaluenodesintothecandidatesetCS

4)

fori=0 to len(CS) do

5)

select a nodevand its direct neighbors intogroup(v)

6)

CS=CS-group(v)

7)

ifCS==null then

8)

break

9)

m=i

10)

fori=0 tom+1do

11)

forj=0 toB+1 do

12)

f[i][j]=0,g[i][j]=0

13)

fork=1 tom+1 do

14)

forb=Bto 0 do

15)

for each node ingroup[k]do

16)

w=Cost(node),v=inf(node)

17)

ifb-w<0 then

18)

continue

19)

iff[k-1][b]

20)

f[k][b]=f[k-1][b-w]+v

21)

g[k][b]=node

22)

else

23)

f[k][b]=f[k-1][b]

24)

j=B

25)

fori=1 tom+1 do

26)

ifg[i][j]!=0 do

27)

S.add(g[i][j])

28)

j=j-Cost(g[i][j])

29)

OutputS

第2)行中，節(jié)點的傳播次數(shù)可以根據(jù)式(1)求得。第4)～8)行，算法將備用種子集合劃分為m個分組。第10)～12)行，定義了兩個二維數(shù)組，初始值均為0：f[i][j]用來保存當成本預算為j時，在前i個分組中尋找的種子集合的信息傳播范圍；g[i][j]用來保存當成本為j時，在第i個分組尋找到的種子。第13)～23)行通過三層循環(huán)，應用式(3)在每個分組中尋找滿足要求節(jié)點。其中，第14)行表示剩余預算b是按照遞減的順序進行的；第16)行中的inf(node)值是根據(jù)式(2)計算的node節(jié)點的影響力，根據(jù)近距離影響思路，只計算node節(jié)點對兩步之內鄰居的影響力；17)、18)行用來排除費用大于剩余成本預算的節(jié)點；19)～21)行表示選擇一個節(jié)點，并保存到二維數(shù)組g中。 第25)～28)行，在數(shù)組g中選擇滿足成本要求的節(jié)點，并且每個分組至多選擇一個節(jié)點。

4 實驗與分析

本次實驗在兩個真實的數(shù)據(jù)集上進行，并比較了BCIM算法和Random算法、Greedy_MII算法、Greedy_MICR算法在種子集的最終影響范圍和種子質量，以及算法的運行時間等方面的性能。

4.1 數(shù)據(jù)集

實驗用到的兩個真實的數(shù)據(jù)集分別是NetHEPT和NetPHY。這兩個數(shù)據(jù)集與文獻[5]中用到的數(shù)據(jù)集一致。在這兩個數(shù)據(jù)集中，節(jié)點代表作者，邊表示作者之間的引用關系。這兩個數(shù)據(jù)集的統(tǒng)計特性如表1所示。

表1 數(shù)據(jù)集的統(tǒng)計特性

4.2 實驗設置

在Random算法中，每次隨機選擇節(jié)點費用不超過剩余成本的節(jié)點。在BCIM算法中，當采用式(2)計算節(jié)點的影響范圍時，只考慮對兩步之內鄰居的影響力。所有的算法都采用MTIC傳播模型并設置影響概率p=0.01。在求種子集合的傳播范圍時，采用蒙特卡羅模擬法，由于傳播模型的隨機性，每種方法都重復模擬10 000次，然后求平均值。

節(jié)點u的費用Cost(u)可以有多種設置方式，本文實驗中為了簡單，將其設置為PageRank排名值。所有的實驗均設置成本預算值B從0遞增到100，每次增加10，然后比較信息傳播范圍和種子質量。同時，實驗也比較了當成本預算值為100時，選擇種子所需要的時間。

所有的程序代碼都采用Python語言編寫，運行計算機的配置為：PentiumDual-coreCPUE6500 2.93GHz，2GB內存。

4.3 實驗結果

4.3.1 信息傳播范圍和種子質量

圖2給出的是NetHEPT數(shù)據(jù)集上的信息傳播范圍。從圖2中可以看到，Random算法信息傳播范圍明顯大于其他算法，BCIM算法與Greedy_MICR算法的差異不大，Greedy_MII算法的性能最差。

圖2 NetHEPT數(shù)據(jù)集上的傳播范圍

圖3給出的是在NetHEPT數(shù)據(jù)集上所選的種子個數(shù)。通過觀察圖3可以發(fā)現(xiàn)，Random算法選擇的種子個數(shù)明顯多于其他算法，而BCIM算法與Greedy_MICR的差異同樣很小，Greedy_MII算法選擇的種子數(shù)最少。

圖3 NetHEPT數(shù)據(jù)集上的種子數(shù)

圖4給出的是NetHEPT數(shù)據(jù)集上種子傳播范圍的增加值。從圖4中可以看到，兩個貪心算法的傳播范圍的增加值幾乎是一樣的，BCIM算法的增加值略小于兩個貪心算法，而Random算法的增加值非常小。

圖5給出的是NetPHY數(shù)據(jù)集上的信息傳播范圍。從圖5中可以看到，Random算法信息傳播范圍明顯大于其他算法，BCIM算法優(yōu)于Greedy_MICR和Greedy_MII算法。

圖6給出的是在NetPHY數(shù)據(jù)集上所選的種子個數(shù)。通過觀察圖6可以發(fā)現(xiàn)，Random算法選擇的種子個數(shù)明顯多于其他算法，BCIM算法所選種子數(shù)略多于Greedy_MICR算法，Greedy_MII算法選擇的種子數(shù)最少。

圖4 NetHEPT數(shù)據(jù)集上種子傳播范圍增加值

圖5 NetPHY數(shù)據(jù)集上的傳播范圍

圖6 NetPHY數(shù)據(jù)集上的種子數(shù)

圖7給出的是NetPHY數(shù)據(jù)集上種子傳播范圍的增加值。從圖7中可以看到，BCIM算法與Greedy_MII算法傳播范圍的增加值接近，Greedy_MICR算法的增加值小于上述兩個算法，而隨機算法Random的增加值依然非常低。

通過對圖2～7的綜合分析可以得出如下結論：1)Random算法所選種子對網(wǎng)絡中其他節(jié)點產(chǎn)生的影響最小，所以質量最差。有研究表明，在“病毒式營銷”方式中，公司傾向于尋找某個領域中的專家或最具影響力的人物進行推銷。這些人接受新產(chǎn)品后會以自身的影響力為公司帶來更大的客戶群體。如果選擇的初始用戶過多且沒有什么影響力，不僅會讓客戶產(chǎn)生厭煩情緒，不利于產(chǎn)品的推廣，而且也不利于對種子節(jié)點的管理。2)采用貪心算法進行種子選擇，每輪選擇傳播范圍增量與費用比值最高的節(jié)點的效果要好于選擇傳播范圍增量最大的節(jié)點，所以選擇“性價比”高的節(jié)點作為種子是一個很好的策略。3)BCIM算法所選種子的影響范圍接近或優(yōu)于兩個貪心算法，并且種子數(shù)量適中，利于產(chǎn)品的推廣。

圖7 NetPHY數(shù)據(jù)集上種子傳播范圍增加值

4.3.2 運行時間

表2給出了當成本預算值為100時，各個算法在兩個數(shù)據(jù)集上進行種子選擇所需要的時間。從表2中可以看到，Random算法的運行時間是最短的，BCIM算法也僅僅需要幾十秒，但兩個貪心算法在兩個數(shù)據(jù)集中都需要幾十分鐘甚至幾百分鐘，這是不能忍受的。

表2 各算法在兩個數(shù)據(jù)集上的運行時間 s

通過對種子集的傳播范圍和程序運行時間的分析表明，Random算法雖然很快，但是由于選擇的種子太多且傳播范圍增加值又太小，所以不適合解決成本控制下的影響最大化問題；兩個貪心算法運行時間太長，同樣不適合解決此問題；BCIM算法在傳播范圍方面不次于貪心算法，并且選擇的種子個數(shù)適中，運行時間又很短，所以更適合解決成本控制下的影響最大化問題。

5 結語

針對成本控制環(huán)境下影響最大化問題，首先提出初始節(jié)點進行多次傳播的信息傳播模型，然后通過縮減種子搜索范圍以及減少計算節(jié)點影響范圍的工作量，提出了基于動態(tài)規(guī)劃思路的最大化算法BCIM。仿真實驗表明BCIM算法比貪心算法更適合解決成本控制下的影響最大化問題。下一步的研究方向可以考慮如何實現(xiàn)利潤的最大化。

)

[1]DOMINGOSP,RICHARDSONM.Miningthenetworkvalueofcustomers[C]//KDD2001:Proceedingsofthe7thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDatamining.NewYork:ACM, 2001: 57-66.

[2]KEMPED,KLEINBERGJ,TARDOSé.Maximizingthespreadofinfluencethroughasocialnetwork[C]//KDD2003:Proceedingsofthe9thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2003: 137-146.

[3]KEMPED,KLEINBERGJ,TARDOSé.Influentialnodesinadiffusionmodelforsocialnetworks[C]//ICALP2005:Proceedingsofthe32ndInternationalColloquiumonAutomata,LanguagesandProgramming,LNCS3580.Berlin:Springer-Verlag, 2005: 1127-1138.

[4]LESKOVECJ,KRAUSEA,GUESTC,etal.Cost-effectiveoutbreakdetectioninnetworks[C]//KDD2007:Proceedingsofthe13thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2007: 420-429.

[5]CHENW,WANGY,YANGS.Efficientinfluencemaximizationinsocialnetworks[C]//KDD2009:Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2009: 199-208.

[6]CHENW,WANGC,WANGY.Scalableinfluencemaximizationforprevalentviralmarketinginlarge-scalesocialnetworks[C]//KDD2010:Proceedingsofthe16thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2010: 1029-1038.

[7]ZHANQ,YANGH,WANGC,etal.CPP-SNS:asolutiontoinfluencemaximizationproblemundercostcontrol[C]//ICTAI2013:Proceedingsof25thInternationalConferenceonToolswithArtificialIntelligence.Piscataway,NJ:IEEE, 2013: 849-856.

[8]WANGY,HUANGW,ZONGL,etal.Influencemaximizationwithlimitcostinsocialnetwork[J].ScienceChinaInformationSciences, 2013, 56(7): 1-14.

[9]ALONN,GAMZUI,TENNENHOLTZM.Optimizingbudgetallocationamongchannelsandinfluencers[C]//WWW2012:Proceedingsofthe21stAnnualConferenceonWorldWideWeb.NewYork:ACM, 2012: 381-388.

[10]BRINS,PAGEL.Theanatomyofalarge-scalehypertextualWebsearchengine[J].ComputerNetworksandISDNSystems, 1998, 30(1/2/3/4/5/6/7): 107-117.

[11]WENGJ,LIME-P,JIANGJ,etal.TwitterRank:findingtopic-sensitiveinfluentialtwitterers[C]//WSDM2010:Proceedingsofthe3rdACMInternationalConferenceonWebSearchandDataMining.NewYork:ACM, 2010: 261-270.

[12]LIUY,GUOJ,SHENJ.Influencemaximizationalgorithmbasedongeneticalgorithm[J].JournalofComputationalInformationSystems, 2014, 10(21): 9255-9262.

ThisworkispartiallysupportedbytheNationalNatureScienceFoundationofChina(61472340),theTechnologyPlanProjectsofHebeiProvince(15210913).

LIU Yuanying, born in 1977, Ph.D.candidate, lecturer.Her research interests include online social network.

GUO Jingfeng, born in 1962, Ph.D., professor.His research interests include data mining, online social network.

WEI Lidong, born in 1962, M.S., associate professor.His research interests include data mining.

HU Xinzhuan, born in 1978, Ph.D.candidate, associate professor.Her research interests include online social network.

Fast influence maximization algorithm in social network under budget control

LIU Yuanying1,2*, GUO Jingfeng1, WEI Lidong2, HU Xinzhuan1

(1.SchoolofInformationScienceandEngineering,YanshanUniversity,QinhuangdaoHebei066004,China;2.CollegeofInformationTechnology,HebeiUniversityofEconomicsandBusiness,ShijiazhuangHebei, 050061,China)

Concerning the high time complexity in influence maximization under budget control, a fast influence maximization algorithm, namely BCIM, was proposed.Firstly, a new information dissemination model which propagates the initial nodes for many times was proposed.Secondly, the nodes with high influence ranking value were selected as candidate seeds, and the calculation of node’s influence scope was decreased based on the short distance influence.Lastly, only one seed was selected at most in each set of candidate seeds by using the dynamic programming method.The experimental results show that, compared with Random (random algorithm), Greedy_MII (greedy algorithm based on the maximum influence increment) and Greedy_MICR (greedy algorithm based on the maximum of influence increment over cost ratio), the influence scope of BCIM is near to or a bit better than that of Greedy_MICR and Greedy_MII, but much worse than that of Random; the quality of seeds set of BCIM, Greedy_MICR and Greedy_MII is similar, but much better than that of Random; the running time of BCIM is several times of Random, while the running time of the both greedy algorithms are hundreds times of BCIM.In summary, BCIM algorithm can find a more effective seeds set in a short time.

influence maximization; online social network; budget control; dynamic programming; multi-propagation model

2016- 08- 12;

2016- 09- 08。 基金項目:國家自然科學基金資助項目(61472340);河北省科技計劃項目(15210913)。

劉院英(1977—),女,河北石家莊人,講師,博士研究生,CCF會員,主要研究方向:在線社會網(wǎng)絡; 郭景峰(1962—),男,河北秦皇島人,教授,博士,CCF會員,主要研究方向:數(shù)據(jù)挖掘、在線社會網(wǎng)絡; 魏立東(1962—),男,河北石家莊人,副教授,碩士,主要研究方向:數(shù)據(jù)挖掘; 胡心專(1978—),女,河北石家莊人,副教授,博士研究生,主要研究方向:在線社會網(wǎng)絡。

1001- 9081(2017)02- 0367- 06

10.11772/j.issn.1001- 9081.2017.02.0367

TP312

A