基于抽樣的影響力傳播成本最小化算法

盛 俊,李 斌,陳 崚

(1.揚州大學(xué) 信息工程學(xué)院，江蘇 揚州 225000； 2.揚州市職業(yè)大學(xué) 信息工程學(xué)院，江蘇 揚州 225000)

0 引 言

近年來，隨著Twitter、Facebook、谷歌、微博等社交網(wǎng)絡(luò)的蓬勃發(fā)展，網(wǎng)絡(luò)分析成為社區(qū)檢測[1]、關(guān)系挖掘[2]、度量學(xué)習[3]、網(wǎng)絡(luò)結(jié)構(gòu)分析[4]、鏈接預(yù)測[5]等領(lǐng)域的研究熱點。社交網(wǎng)絡(luò)[6]是由各種實體構(gòu)成的交流平臺，它形成了一個圖的結(jié)構(gòu)，圖中的頂點為各種實體，連接它們的邊反映了它們的相互關(guān)系。隨著互聯(lián)網(wǎng)的不斷發(fā)展，人們使用社交網(wǎng)絡(luò)也越來越頻繁。社交網(wǎng)絡(luò)中，用戶的觀點、行為和情感都會受到某些用戶影響力的傳播作用的影響。而社交網(wǎng)絡(luò)的流行，也帶來了影響力傳播的一些新的應(yīng)用，例如輿情控制[7]、病毒式營銷[8]等。因此，如何衡量和預(yù)測一個或多個用戶對其社交范圍內(nèi)其他用戶的影響力是一個關(guān)鍵的問題。影響力最大化[9]就是要在一個社交網(wǎng)絡(luò)中找出一個影響力的發(fā)散源節(jié)點，即“種子”集合，使得這些集合中的節(jié)點在社交網(wǎng)絡(luò)中擴散的影響力最大化。影響力最大化在生物信息學(xué)[10]、政治選舉、病毒營銷[11,12]、經(jīng)濟學(xué)[13]、推薦[14]、輿情監(jiān)測[15]等領(lǐng)域得到了廣泛的應(yīng)用。

影響力最大化的問題本質(zhì)上是一個離散優(yōu)化問題，常用的傳播模型有獨立級聯(lián)模型和線性閾值模型。影響力最大化的問題可以用貪心法來求解。然而，貪心算法的時間復(fù)雜度很高，大部分的計算時間用來估計種子集合的影響力范圍。因此，隨后的很多人對其效率進行了改進。Sun等[16]提出了一種基于有影響力種子接班人的可擴展的影響力最大化方法，算法借助種子頂點接班人的概念，減少了影響力傳播的評估次數(shù)。

近年來，出現(xiàn)了一些不同的傳播模型下的影響力最大化的新的應(yīng)用問題。SharanVaswani等[17]研究了自適應(yīng)的影響力最大化問題，提出了自適應(yīng)的種子選擇策略。該方法根據(jù)已有種子的傳播情況的反饋來選擇新的種子。為了有效地利用反饋信息，Yuan等[18]提出了一個部分反饋模型，該模型可以在性能和延遲之間取得平衡。他們驗證了部分反饋模型中的影響力擴散函數(shù)是非次模的。為此,他們提出了一種(α,β)貪婪的方法可以使得在部分反饋模型中達到常數(shù)近似比例的結(jié)果。

在病毒營銷中，由于顧客對產(chǎn)品的影響力傳播能力不同，商家可能會向不同的顧客提供不同的優(yōu)惠折扣。該問題可以建模為連續(xù)影響最大化問題。Yu Yang等[19]研究了這個問題,并提出了一個獲得最優(yōu)種子集的算法。Tang等[20]研究了如何確定病毒營銷中各個客戶的優(yōu)惠折扣的問題：給定一個預(yù)算值,企業(yè)需要決定給予哪些客戶優(yōu)惠折扣，應(yīng)該給每一個客戶提供多少折扣,才能使得產(chǎn)品銷售到盡可能多的客戶。他們在不同的擴散模型下研究了這一問題，并提出了一種貪心方法，使得影響擴散的期望值充分地逼近最優(yōu)值。

在上面提到的問題中，種子集的大小或成本是預(yù)先定義好的。但在一些實際應(yīng)用中，影響力的散布者希望通過最少的種子或最低的成本來將影響力傳播到一定范圍內(nèi)。已有的研究結(jié)果表明該問題不具有次模性，可以使用逼近最優(yōu)解的近似算法來求解。Zhang等[21]研究了在多個網(wǎng)絡(luò)中將影響傳播到指定范圍的最小數(shù)目的種子挖掘問題。他們提出了一種將多個網(wǎng)絡(luò)映射成單個網(wǎng)絡(luò)的有損耦合方法，并采用改進的貪婪算法檢測種子節(jié)點。

在影響力最大化的商業(yè)應(yīng)用中，廣告的成本往往受到預(yù)算的限制。例如，一家通訊設(shè)備公司需要在某個地區(qū)銷售一款新手機，他們可以通過向一些選定的用戶提供優(yōu)惠折扣，以最大限度地擴大其新手機的影響力。公司的目的是鼓勵有影響力的客戶說服盡可能多的朋友和親戚購買這款新手機，而該公司在優(yōu)惠折扣上的成本要降到最低。由于公司對不同的用戶所給的折扣可能不一樣，該問題的關(guān)鍵是如何選擇有影響力的用戶，將產(chǎn)品的影響力傳播到某個地區(qū)范圍，而總費用要最小。這就是研究影響力傳播的成本最小化問題。近年來，有很多工作研究了這一個問題。

已有的大部分影響力最大化算法需要通過抽樣方法來估計影響力傳播的范圍，這使得算法的復(fù)雜度很高。因此，研究影響力最大化以及成本最小化的效率更高的算法很有必要。為此，文中提出基于LT模型的影響力傳播的成本最小化算法，該算法利用VC(Vapnik-Chervonenkis)維對網(wǎng)絡(luò)的路徑進行抽樣，從而計算它們的激活概率。我們在實際數(shù)據(jù)集上的實驗結(jié)果表明，該算法比其它方法具有更高的性能。

1 問題的定義及其性能分析

定義1 影響力傳播的成本最小化問題

一個社交網(wǎng)絡(luò)可用有向圖G=(V,E,P) 表示，其中V為節(jié)點的集合，E為有向邊的集合，P=[pij] 為概率矩陣，設(shè)有向邊(vi,vj)∈E,P的元素pij表示vi對vj產(chǎn)生影響的概率。在網(wǎng)絡(luò)的頂點集合V上定義成本函數(shù)C(v)， 為選用頂點v為種子的成本。給出激活范圍U?V， 以及一個覆蓋閾值η≤|μ|， 我們要找一個使得成本

最小的種子集合S，且其在U中的影響力InfU(S) 滿足

|InfU(S)|≥η

即要在集合V中選擇一個種子集合S*滿足

(1)

我們稱該問題為影響力傳播的成本最小化問題。

頂點v的激活成本C(v) 在實際應(yīng)用中通常為給種子客戶v的折扣優(yōu)惠，或網(wǎng)站v推銷產(chǎn)品的廣告費用。這可以根據(jù)用戶的信譽度、網(wǎng)站的影響力來確定。所有種子的成本之和，構(gòu)成了種子集合S的成本，此為該產(chǎn)品營銷的總成本，我們的目的是要將產(chǎn)品的影響力傳播到指定的范圍，而總費用要最小。

我們考慮在線性閾值模型下的影響力傳播的成本最小化問題。線性閾值模型(LT)將用戶分為激活和非激活兩種狀態(tài)，該模型為每個節(jié)點v賦予一個閾值θv， 一旦v的相鄰節(jié)點對它激活值的累計大于θv， 節(jié)點v就會變?yōu)榧せ顮顟B(tài)。圖1表示了在線性閾值模型下影響力的傳播方式，其具體過程如下：

圖1 線性閾值傳播模型

初始時刻t=0,網(wǎng)絡(luò)中只有種子節(jié)點為激活狀態(tài)。一個節(jié)點被激活以后，它會試圖激活它的未激活的鄰居。一旦節(jié)點v所受到的影響力的累計超過閾值θv, 它就轉(zhuǎn)變?yōu)榧せ顮顟B(tài)，否則它繼續(xù)在未激活狀態(tài)。重復(fù)這樣的激活過程，直到?jīng)]有更多的節(jié)點可以被激活為止。種子傳播的影響力大小即為被激活的節(jié)點的個數(shù)。

定理1 影響力傳播的成本最小化問題是NP-難的。

證明：證明影響力傳播的成本最小化問題可以規(guī)約為帶權(quán)集合覆蓋(WSC)問題，而WSC問題是NP-難的。

對于帶權(quán)集合覆蓋問題，記U={u1,u2,…,un} 為全集，而B1,B2,…,Bm為U的m個子集。每個子集Bi?U(i=1,2,…,m) 具有一個權(quán)重w(Bi)。 WSC問題就是要找出具有最小權(quán)重的一組子集，使它們的并集覆蓋U的至少η個元素。

假設(shè)S={v1,v2,…,vk} 為影響力傳播的成本最小問題的解。如果S∩Y=φ, 我們知道WSC問題中的子集B1,B2,…,Bk至少可以覆蓋在u中的η個元素，它們可以形成WSC的問題的一個解。如果Y∩S≠φ， 我們可以將Y∩S中的每一個頂點u用其成本最少的鄰居節(jié)點v∈N(u) 來代替，從而形成新的子集S′?S。 易知C(S′)=C(S)， 則S′也是WSC問題的一個解。

可以用類似的方法證明，WSC實例的解也是影響力傳播的成本最小問題實例的解。

證畢。

由于影響力傳播的成本最小化問題是NP-難的，需要設(shè)計一種有效的算法來尋找種子集S，使其近似于最優(yōu)解S*。我們利用影響力傳播的成本最小化問題的傳播函數(shù)的單調(diào)性和次模性，使用貪心方法取得該問題的近似最優(yōu)解。

定義2 單調(diào)性

設(shè)f(S) 為集合S的函數(shù)，對于兩個集合S和Q,若S?Q， 有f(S)≤f(Q)， 則稱f(S) 對于集合S是單調(diào)的。

定義3 次模性

設(shè)f(S) 為集合S的函數(shù)，對于兩個集合S和Q以及元素V,若S?Q， 有

f(S∪{v})-f(S)≥f(Q∪{v})-f(Q)

則稱f(S) 是次模的。

在影響力傳播的成本最小化問題中，我們用InfU(S) 表示種子集合S所影響的U中的節(jié)點的集合，用傳播擴散函數(shù)f(S)=|InfU(S)| 表示所影響的U中的節(jié)點的數(shù)目。

定理2 在影響力擴散傳播的成本最小化問題中，傳播函數(shù)f(S)=|InfU(S)| 是單調(diào)和次模的。

證明：

(1)單調(diào)性

設(shè)X為U中的一個被種子集合S影響的節(jié)點， InfU(S,x) 為S中種子的影響力傳播到X的路徑中U中的被影響的節(jié)點的集合， fx(S)=|InfU(S,x)| 為InfU(S,x) 中節(jié)點的個數(shù)，則有

在這里, Pr(x) 是X被影響的概率。

由于f(S) 是fx(S) 的線性組合， f(S) 也是單調(diào)的。

(2)次模性

設(shè)v∈V為網(wǎng)絡(luò)中的一個頂點，易知

fx(S∪{v})-fx(S)=|InfU(v,x)InfU(S,x)|fx(Q∪{v})-fx(Q)=|InfU(v,x)InfU(Q,x)|

(2)

由于S?Q， 且fx(S) 是單調(diào)的,則有fx(S)≤fx(Q)。

那么有

|InfU(S,x)|≤|InfU(Q,x)|

(3)

由式(2)和式(3)可知

fx(S∪{v})-fx(S)≥fx(Q∪{v})-fx(Q)

(4)

這說明了fx(S) 是次模的。由于f(S) 是fx(S) 的線性組合，故f(S) 也是次模的。

證畢。

研究結(jié)果表明，若影響力最大化問題的傳播擴散函數(shù)具有單調(diào)性和次模性，則使用貪心算法依次選擇影響擴散增量最大的節(jié)點，其結(jié)果是最優(yōu)解的 (1-1/e) 近似。因此，基于傳播擴散函數(shù)f(S) 的次模性，我們可以用貪心法來選取種子集合。

2 路徑的激活概率

研究結(jié)果表明，LT模型可化為多個“Live-Edge”圖(LE圖，活邊圖)來表示。在一個活邊圖中，每一個頂點v按照連接它的入邊的概率隨機選取一條入邊加入活邊圖。因此，我們可以將網(wǎng)絡(luò)看成是一個不確定圖，LE模型中的每一種選擇可以看成不確定圖的一個可能世界。

定義4 不確定圖

不確定圖是一個三元組G=(V,E,P)， 其中p∶E→(0,1) 為邊上的存在函數(shù)，V和E分別表示為頂點和邊的集合。邊上的概率P∈(0,1) 表示該邊存在的可能性，若圖中所有邊上的概率皆為P=1， 即該圖為確定圖。

一個不確定圖G=(V,E,P) 含有2|E|個可能世界，可能世界的定義請參見文獻[22]。記G的可能世界集合為W(G)。

設(shè)G′=(V,E′) 為G的一個可能世界，G′存在的概率為

(5)

G的所有可能世界的存在概率之和為1，即

將網(wǎng)絡(luò)中的每一條邊上的傳播概率看成邊的存在概率，則可以構(gòu)成一個不確定圖，LE模型中的每一種活邊圖可以看成一個可能世界。這樣，S的激活范圍σ(S) 就為可能世界中從S的頂點能夠連接的U中的范圍的期望值。即

(6)

其中， σG′(S) 可以使用下式進行計算

(7)

在式(7)中

結(jié)合式(6)和式(7)可以得到

(8)

(9)

則

(10)

由式(10)可見，要計算σ(S) 的值，首先要對S中所有頂點u估計Pr(u) 的值。

3 路徑抽樣方法

由于Pr(u,v)是從u到v有路徑的概率，可用下式計算

(11)

我們首先估計所需樣本的個數(shù)。

為了估計合適的樣本個數(shù)r，我們借助于Vapnik-Chervonenkis 維的方法。

定義5 VC維(Vapnik-Chervonenkis dimension)[23]H的VC維記為VC(H)。 VC(H) 是S被H打散的最大的基數(shù)。

打散的定義請參見文獻[23]。

在這個路徑抽樣的問題中，實例集S為PL(x)， 空間集H即為集合Hx

Hx={px,v|v∈V,|px,v|≤L}

(12)

即長度小于L的以x開頭的路徑的集合。

設(shè)S={x1,…,xm}為數(shù)據(jù)集D上根據(jù)分布φ而得到的樣本集，對于子數(shù)據(jù)集A?D， 設(shè)φ(A)為按照分布φ而得到的樣本屬于的A概率，則在S中對φ(A) 的估計值φS(A) 為

(13)

這里指示函數(shù)IA(xi) 定義為

定義6ε近似：設(shè)H為D上的一個空間集合，φ為D上的概率分布，設(shè)ε∈(0,1)，D上滿足下列條件的集合S為 (H,φ) 中的一個ε近似

(14)

式中：sup為上確界。根據(jù)Vapnik-Chervonenkis 的學(xué)習理論可知，我們可以由φ的分布以及H的VC維的值來估計出構(gòu)造 (H,φ) 的ε近似所需樣本的個數(shù)。

定理3[24]記H為D上的空間集， VC(H)≤d,φ為D上的一個分布，設(shè)ε,δ∈(0,1)， 且

(15)

那么，S將以1-δ的概率為 (H,φ) 的ε近似。這里， |S| 是集合S中樣本集的大小，常數(shù)C>0。

上述定理告訴我們，如果我們估計出VC(H) 的大小，就可以用式(15)計算出QL(x) 中的樣本數(shù)r，使得QL(x) 以1-δ的概率成為PL(x) 的ε近似。

為此，針對路徑抽樣問題有如下的定理：

定理4 設(shè)H為PL(x) 上的空間集，x為G的某一頂點，H={px,v|v∈V,|px,v|≤L}, 則Hx的VC維滿足

Vc(H)≤log2(L+1)

(16)

定理4的證明請參見文獻[25]。

由定理4可知，使用H={px,v|v∈V,|px,v|≤L} 的VC維最多為log2(L+1)。 將此值帶入式(15)中的d,得到所需樣本個數(shù)r的取值范圍為

(17)

只要取大小滿足式(17)的r，就可以保證QL(x) 以1-δ的概率成為PL(x) 的ε近似。

4 算法框架與復(fù)雜度分析

綜上所述，文中提出算法Sampling_MINSC解決影響力成本最小化問題，Sampling_MINSC算法首先抽樣若干個可能世界，然后在此基礎(chǔ)上對各個節(jié)點估計Pr(u)。 算法取Pr(u)/C(u)最大的若干個節(jié)點構(gòu)成種子集合S，使得在U中的影響力傳播超過η， 且成本最小。給定誤差閾值ε、 概率值δ、 路徑的數(shù)學(xué)期望的閾值ρ， 算法Sampling_MINSC的總體框架描述如下：

算法1： Sampling_MINSC

輸入：G=(V,E,P): 已知網(wǎng)絡(luò)；

η： 擴散規(guī)模；

C： 成本閾值；

輸出：S： 達到傳播閾值的最小成本種子集合；

(1)由式(17)計算抽樣的大小r；

/*構(gòu)造r個可能世界*/

(2)fori=1 to r do

Sample-generating(G)

end fori;

/*計算每個節(jié)點在可能世界中可以到達的范圍*/

(3)對圖G中所有節(jié)點對 (u,v) 置

Pr(u,v)=0

(4)fori=1 to r do

Prob-computing(Gi);

end fori;

(5)forevery nodeu∈Vdo

endforu;

(6) InfU(S)=0;

repeat

取Pr(u)/C(u) 最大的節(jié)點u;

S=S∪{u}；

InfU(S)=InfU(S)+Pr(u);

UntilInfU(S)≥η;

(7)returnS

算法Sampling_MINSC的步驟1由式(17)計算抽樣個數(shù)r；第(2)步調(diào)用算法3產(chǎn)生r個抽樣；第(3)步和第(4)步調(diào)用算法2估計各個頂點能夠到達的范圍。第(5)步對各個頂點計算Pr(u)。 第(6)步和第(7)步取Pr(u)/C(u) 最大的若干個節(jié)點構(gòu)成集合S并輸出。

算法第1步計算抽樣個數(shù)r，所需時間為O(1)； 第(2)步調(diào)用算法2，復(fù)雜度為O(r*m)， 其中m=|E|。 第(3)步復(fù)雜度為O(n2)， 其中n=|V|。 第(4)步調(diào)用算法Prob-computing，所需時間為O(r*n2)。 第(5)步累加所有頂點Pr(u) 值，需要O(n2) 時間。第(6)步構(gòu)成集合S，設(shè)最終S中有P個種子，p≤n， 則復(fù)雜度為O(np)。 第(7)步輸出S,復(fù)雜度為O(p)。 綜上所述，算法的復(fù)雜度為O(n2)。

算法Prob-computing計算G所有頂點對u、V計算Pr(u,v) 的值。其內(nèi)容如下：

算法2： Prob-computing

輸入：Gi: 已知的抽樣圖；

L: 路徑長度閾值；

輸出： Pr: 節(jié)點之間的Pr(u,v) 的值；

(1)foreachv∈Vdo

(2)u=v;l=0;Q=φ;

(3)whileQ≠φandl≤Ldo

(4)foreach unvisited neighborwofudo

(5) put (w,l+1) into the tail ofQ；

(6) Pr(u,v)=Pr(u,v)+Pr(Gi);

(7)endforu；

(8) get the head ofQ→(u,l)；

(9)endwhile

(10)endforv

算法Sample-generating 對圖G的邊進行抽樣，從而產(chǎn)生一個可能世界，具體步驟如下：

算法3： Sample-generating

輸入：G=(V,E,P): 已知網(wǎng)絡(luò)；

輸出：G′=(V,Ek): 所產(chǎn)生的一個可能世界；

(1)Ek=φ

(2)forevery edgee=(u,v) inEdo

(3) 產(chǎn)生隨機數(shù)r∈(0,1);

(4)ifr

(5)Ek=Ek∪{e}

(6)endif;

(7)endfore;

(8)G′=(V,Ek);

(9) returnG′

5 實驗結(jié)果及其分析

5.1 實驗數(shù)據(jù)集和相關(guān)設(shè)置

我們在4個數(shù)據(jù)集上對上述算法的性能進行測試。實驗數(shù)據(jù)集見表1。

表1 實驗數(shù)據(jù)集

數(shù)據(jù)集DBLP來自一個論文作者的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的頂點為作者，頂點間的連邊說明他們共同發(fā)表過論文。和DBLP類似，數(shù)據(jù)集NetHPET來自一個高能物理論文作者的網(wǎng)絡(luò)。Epinions是一個對商品進行評價的網(wǎng)站，用戶可以對商品發(fā)表評論，或?qū)ζ渌脩舻脑u論發(fā)表意見。從用戶之間的不同意見可以決定他們之間的關(guān)系。數(shù)據(jù)集LiveJournal來自一個在線社區(qū)，其中節(jié)點表示會員，會員通過個人日志和組日志來標志和其他成員的朋友關(guān)系。

我們對算法用Matlab編程，在Windows7環(huán)境下運行，處理器為Core i5 2410 M 2.3 GHz，16 GB內(nèi)存。

對上述數(shù)據(jù)集，頂點間的傳播概率設(shè)置為

節(jié)點的激活閾值θv設(shè)置為 [0,1] 中的一個隨機值。對每個節(jié)點v產(chǎn)生一個 [0,1] 間的隨機數(shù)作為它的成本值C(v)。

5.2 算法對比

在實驗中，我們將所提出的算法的性能和Greedy、PageRank[26]、DegreeDiscountIC[15]和Random等算法進行比較。Greedy是一種貪心算法，它逐次選擇影響力增量最大的頂點加入種子集合。PageRank采用迭代的方法計算節(jié)點的影響力，并挑選影響力最大的若干個頂點為種子頂點。算法DegreeDiscountIC采用貪心法根據(jù)頂點的度來選擇種子集合。和Greedy算法不同的是，當頂點v的相鄰頂點被選作種子后，算法要對節(jié)點v的度數(shù)適當降低。Random算法在頂點集合中隨機挑選k個頂點作為種子頂點。

5.3 實驗結(jié)果

(1)DBLP數(shù)據(jù)集上的結(jié)果

在DBLP上抽出1 737 893個可能世界進行實驗，實驗結(jié)果如圖2所示。

圖2 DBLP上的運行結(jié)果

由圖2可以看出，達到相同的影響力覆蓋范圍時，提出的算法Sampling_MINSC所用的成本最少，PageRank和Sampling_MINSC的成本總體上相近，略小于Sampling_MINSC。DegreeDiscountIC次之, Random最差。

(2)Epinions數(shù)據(jù)集上的結(jié)果

我們在Epinions數(shù)據(jù)集上進行1 737 893次抽樣，所得到的傳播成本如圖3所示。

圖3 Epinions上的運行結(jié)果

由圖3可以看出，Sampling_MINSC算法依然是最優(yōu)的，PageRank次之，DegreeDiscountIC和Random的效果較差。

(3)NetHPET數(shù)據(jù)集上的結(jié)果

我們在NetHPET數(shù)據(jù)集上進行1 737 893次抽樣，所得到的傳播成本如圖4所示。

圖4 NetHPET上的運行結(jié)果

實驗結(jié)果顯示，提出的算法Sampling_MINSC所用的成本最少，PageRank和Sampling_MINSC的成本總體上相近，略小于Sampling_MINSC。DegreeDiscountIC次之, Random最差。

從上述實驗結(jié)果可以看出，相較于PageRank、DegreeDiscountIC和Random，Sampling_MINSC算法的效果是最好的。Sampling_MINSC算法之所以影響傳播代價最小，是因為它采用了貪心算法使得種子的影響力盡可能覆蓋較多的目標范圍。另外，它采用基于抽樣的方法從抽樣的子圖中得到種子集，能較準確地逼近原網(wǎng)絡(luò)。

對算法Sampling_MINSC在Epinions數(shù)據(jù)集上對于不同的概率p下的成本進行比較。設(shè)誤差界為ε=0.01η， 圖5顯示了在各種傳播范圍閾值η下，對于不同的概率p的成本。由圖5可以看出，對于較大的概率p，由于所要覆蓋的范圍較大，所需的成本較高。

圖5 Epinions數(shù)據(jù)集上不同的概率p下的成本

對算法Sampling_MINSC在Epinions數(shù)據(jù)集上對于不同的誤差界ε下的成本進行比較。設(shè)概率值p為0.9，圖6顯示了在各種傳播范圍閾值η下，誤差界為ε=0.01η、0.02η、0.05η、0.1η時的成本。由圖6可以看出，對于較大的ε值，由于覆蓋的精確度要求較高，所需的成本較高。

圖6 Epinions數(shù)據(jù)集上不同的誤差界ε下的成本

6 結(jié)束語

針對影響力傳播的成本最小化問題，提出Sampling_MINSC算法。算法基于不確定圖的可能世界的概念進行路徑的抽樣，使用VC維去估計可能世界的抽樣數(shù)量，這樣可以避免使用Monte Carlo模擬來計算度量影響力擴散。使用貪婪算法在固定影響范圍下篩選出具有最小成本的種子集合。我們通過實驗來驗證文中所提算法的準確性，并和其它類似算法進行比較。此外，還對算法在不同的概率p下的成本、在不同誤差界ε下的成本進行比較。實驗結(jié)果表明，Sampling_MINSC算法的傳播代價比其它算法小。Sampling_MINSC算法之所以影響傳播代價最小，是因為它采用了貪心算法使得種子的影響力盡可能覆蓋較多的目標范圍。另外，它采用基于抽樣的方法從抽樣的子圖中得到種子集，能較準確地逼近原網(wǎng)絡(luò)。