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

盛 俊,李 斌,陳 崚

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

0 引 言

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

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

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

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

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

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

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

1 問(wèn)題的定義及其性能分析

定義1 影響力傳播的成本最小化問(wèn)題

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

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

|InfU(S)|≥η

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

(1)

我們稱該問(wèn)題為影響力傳播的成本最小化問(wèn)題。

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

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

圖1 線性閾值傳播模型

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

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

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

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

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

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

證畢。

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

定義2 單調(diào)性

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

定義3 次模性

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

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

則稱f(S) 是次模的。

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

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

證明：

(1)單調(diào)性

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

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

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

(2)次模性

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

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)

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

證畢。

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

2 路徑的激活概率

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

定義4 不確定圖

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

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

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

(5)

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

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

(6)

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

(7)

在式(7)中

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

(8)

(9)

則

(10)

由式(10)可見(jiàn)，要計(jì)算σ(S) 的值，首先要對(duì)S中所有頂點(diǎn)u估計(jì)Pr(u) 的值。

3 路徑抽樣方法

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

(11)

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

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

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

打散的定義請(qǐng)參見(jiàn)文獻(xiàn)[23]。

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

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

(12)

即長(zhǎng)度小于L的以x開(kāi)頭的路徑的集合。

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

(13)

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

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

(14)

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

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

(15)

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

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

為此，針對(duì)路徑抽樣問(wèn)題有如下的定理：

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

Vc(H)≤log2(L+1)

(16)

定理4的證明請(qǐng)參見(jiàn)文獻(xiàn)[25]。

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

(17)

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

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

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

算法1： Sampling_MINSC

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

η： 擴(kuò)散規(guī)模；

C： 成本閾值；

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

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

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

(2)fori=1 to r do

Sample-generating(G)

end fori;

/*計(jì)算每個(gè)節(jié)點(diǎn)在可能世界中可以到達(dá)的范圍*/

(3)對(duì)圖G中所有節(jié)點(diǎn)對(duì) (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é)點(diǎn)u;

S=S∪{u}；

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

UntilInfU(S)≥η;

(7)returnS

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

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

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

算法2： Prob-computing

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

L: 路徑長(zhǎng)度閾值；

輸出： Pr: 節(jié)點(diǎn)之間的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 對(duì)圖G的邊進(jìn)行抽樣，從而產(chǎn)生一個(gè)可能世界，具體步驟如下：

算法3： Sample-generating

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

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

(1)Ek=φ

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

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

(4)ifr

(5)Ek=Ek∪{e}

(6)endif;

(7)endfore;

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

(9) returnG′

5 實(shí)驗(yàn)結(jié)果及其分析

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

我們?cè)?個(gè)數(shù)據(jù)集上對(duì)上述算法的性能進(jìn)行測(cè)試。實(shí)驗(yàn)數(shù)據(jù)集見(jiàn)表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

5.2 算法對(duì)比

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

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

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

在DBLP上抽出1 737 893個(gè)可能世界進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示。

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

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

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

我們?cè)贓pinions數(shù)據(jù)集上進(jìn)行1 737 893次抽樣，所得到的傳播成本如圖3所示。

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

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

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

我們?cè)贜etHPET數(shù)據(jù)集上進(jìn)行1 737 893次抽樣，所得到的傳播成本如圖4所示。

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

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

從上述實(shí)驗(yàn)結(jié)果可以看出，相較于PageRank、DegreeDiscountIC和Random，Sampling_MINSC算法的效果是最好的。Sampling_MINSC算法之所以影響傳播代價(jià)最小，是因?yàn)樗捎昧素澬乃惴ㄊ沟梅N子的影響力盡可能覆蓋較多的目標(biāo)范圍。另外，它采用基于抽樣的方法從抽樣的子圖中得到種子集，能較準(zhǔn)確地逼近原網(wǎng)絡(luò)。

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

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

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

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

6 結(jié)束語(yǔ)

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