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

盛 俊,李 斌,陳 崚

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

|InfU(S)|≥η

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

(1)

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

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

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

圖1 線性閾值傳播模型

初始時刻t=0,網絡中只有種子節點為激活狀態。一個節點被激活以后，它會試圖激活它的未激活的鄰居。一旦節點v所受到的影響力的累計超過閾值θv, 它就轉變為激活狀態，否則它繼續在未激活狀態。重復這樣的激活過程，直到沒有更多的節點可以被激活為止。種子傳播的影響力大小即為被激活的節點的個數。

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

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

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

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

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

證畢。

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

定義2 單調性

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

定義3 次模性

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

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

則稱f(S) 是次模的。

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

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

證明：

(1)單調性

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

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

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

(2)次模性

設v∈V為網絡中的一個頂點，易知

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) 是單調的,則有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) 也是次模的。

證畢。

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

2 路徑的激活概率

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

定義4 不確定圖

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

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

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

(5)

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

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

(6)

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

(7)

在式(7)中

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

(8)

(9)

則

(10)

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

3 路徑抽樣方法

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

(11)

我們首先估計所需樣本的個數。

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

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

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

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

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

(12)

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

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

(13)

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

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

(14)

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

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

(15)

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

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

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

定理4 設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,得到所需樣本個數r的取值范圍為

(17)

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

4 算法框架與復雜度分析

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

算法1： Sampling_MINSC

輸入：G=(V,E,P): 已知網絡；

η： 擴散規模；

C： 成本閾值；

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

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

/*構造r個可能世界*/

(2)fori=1 to r do

Sample-generating(G)

end fori;

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

(3)對圖G中所有節點對 (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) 最大的節點u;

S=S∪{u}；

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

UntilInfU(S)≥η;

(7)returnS

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

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

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

算法2： Prob-computing

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

L: 路徑長度閾值；

輸出： Pr: 節點之間的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的邊進行抽樣，從而產生一個可能世界，具體步驟如下：

算法3： Sample-generating

輸入：G=(V,E,P): 已知網絡；

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

(1)Ek=φ

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

(3) 產生隨機數r∈(0,1);

(4)ifr

(5)Ek=Ek∪{e}

(6)endif;

(7)endfore;

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

(9) returnG′

5 實驗結果及其分析

5.1 實驗數據集和相關設置

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

表1 實驗數據集

數據集DBLP來自一個論文作者的網絡，網絡中的頂點為作者，頂點間的連邊說明他們共同發表過論文。和DBLP類似，數據集NetHPET來自一個高能物理論文作者的網絡。Epinions是一個對商品進行評價的網站，用戶可以對商品發表評論，或對其他用戶的評論發表意見。從用戶之間的不同意見可以決定他們之間的關系。數據集LiveJournal來自一個在線社區，其中節點表示會員，會員通過個人日志和組日志來標志和其他成員的朋友關系。

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

對上述數據集，頂點間的傳播概率設置為

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

5.2 算法對比

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

5.3 實驗結果

(1)DBLP數據集上的結果

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

圖2 DBLP上的運行結果

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

(2)Epinions數據集上的結果

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

圖3 Epinions上的運行結果

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

(3)NetHPET數據集上的結果

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

圖4 NetHPET上的運行結果

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

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

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

圖5 Epinions數據集上不同的概率p下的成本

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

圖6 Epinions數據集上不同的誤差界ε下的成本

6 結束語

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