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

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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1 傳播模型

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

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

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

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

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

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

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

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

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

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

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

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

1)證明在樣本點(diǎn)x上的單調(diào)性。

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

2)證明在樣本點(diǎn)x上的子模性。

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

2 問題定義

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

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

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

定義4 當(dāng)以Cost(u)表示節(jié)點(diǎn)的費(fèi)用，Degree(u)表示u的鄰居數(shù)時，u進(jìn)行信息傳播的次數(shù)Num(u)定義為：

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

(1)

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

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

inf(a)=

(2)

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

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

圖1給出的是節(jié)點(diǎn)A以及它的鄰居節(jié)點(diǎn)，當(dāng)計算A的影響力時，節(jié)點(diǎn)B和C屬于T1(a)，節(jié)點(diǎn)D、E、F屬于T2(a)。基于后面提到的近距離影響法，忽略邊(B,C)和(D,E)的影響。

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

定義5 對于圖G=(V,E)，假設(shè)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é)點(diǎn)u和v之間的距離不大于2。

3 影響最大化算法

3.1 貪心算法

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

算法1Greedy_MII。

輸入G=(V,E)，成本B，節(jié)點(diǎn)費(fèi)用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é)點(diǎn)費(fèi)用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

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

3.2 BCIM算法

3.2.1 減少搜索范圍

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

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

3.2.2 減少計算工作量

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

3.2.3BCIM算法實(shí)現(xiàn)

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

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

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

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

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

(3)

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

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

BCIM算法如算法3所示。

算法3BCIM。

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

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

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

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

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

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

4.2 實(shí)驗(yàn)設(shè)置

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

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

所有的程序代碼都采用Python語言編寫，運(yùn)行計算機(jī)的配置為：PentiumDual-coreCPUE6500 2.93GHz，2GB內(nèi)存。

4.3 實(shí)驗(yàn)結(jié)果

4.3.1 信息傳播范圍和種子質(zhì)量

圖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算法的增加值小于上述兩個算法，而隨機(jī)算法Random的增加值依然非常低。

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

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

4.3.2 運(yùn)行時間

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

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

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

5 結(jié)語

針對成本控制環(huán)境下影響最大化問題，首先提出初始節(jié)點(diǎn)進(jìn)行多次傳播的信息傳播模型，然后通過縮減種子搜索范圍以及減少計算節(jié)點(diǎn)影響范圍的工作量，提出了基于動態(tài)規(guī)劃思路的最大化算法BCIM。仿真實(shí)驗(yàn)表明BCIM算法比貪心算法更適合解決成本控制下的影響最大化問題。下一步的研究方向可以考慮如何實(shí)現(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。 基金項目:國家自然科學(xué)基金資助項目(61472340);河北省科技計劃項目(15210913)。

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

1001- 9081(2017)02- 0367- 06

10.11772/j.issn.1001- 9081.2017.02.0367

TP312

A