不同營銷模式中基于時間的影響傳播方法研究*

劉　勇，曲思桐，王　楠，郭龍江

黑龍江大學(xué)計算機科學(xué)技術(shù)學(xué)院，哈爾濱150080

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0338-12

?

不同營銷模式中基于時間的影響傳播方法研究*

劉勇+，曲思桐，王楠，郭龍江

黑龍江大學(xué)計算機科學(xué)技術(shù)學(xué)院，哈爾濱150080

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0338-12

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 81273649 (國家自然科學(xué)基金); the Natural Science Foundation of Heilongjiang Province under Grant No. F201430 (黑龍江省自然科學(xué)基金); the Scientific Research Fund of Heilongjiang Provincial Education Department under Grant No.12531476 (黑龍江省教育廳科學(xué)技術(shù)研究項目).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-09-15, http://www.cnki.net/kcms/detail/11.5602.TP.20150915.1618.008.html

摘要：影響最大化問題是在社交網(wǎng)絡(luò)上找到一組有影響力的用戶，使得期望的影響范圍最大化。然而，已有book=339,ebook=43的研究工作沒有考慮用戶之間有效的傳播時間區(qū)間，而且忽略了營銷時間對于選取初始用戶的影響。基于真實用戶動作日志，確定了用戶之間有效的傳播時間區(qū)間，并提出了一個基于時間的影響力分配模型（influence power allocating model based on time，IPAT）。根據(jù)該模型，提出了基于真實時間的影響力最大化問題（influence maximization problem based on time，IMPT）和饑餓營銷模式中種集最小化問題（seed set minimization problem in hungry marketing，SMPHM），并證明了這兩個問題都是NP-hard問題。為求解IMPT問題和SMPHM問題，分別提出了有效的近似算法A-IMPT（algorithm for IMPT）和A-SMPHM（algorithm for SMPHM），并證明了算法A-IMPT和A-SMPHM的近似比。多個真實社交網(wǎng)絡(luò)數(shù)據(jù)集上的實驗驗證了算法AIMPT和A-SMPHM的有效性和高效率。

關(guān)鍵詞：社會網(wǎng)；影響傳播；傳播時間區(qū)間；營銷時間；饑餓營銷

1　引言

隨著社會的不斷發(fā)展，近年來各類社交網(wǎng)站不斷涌現(xiàn)出來，人們開始廣泛使用諸如微博、facebook等社交網(wǎng)站。這些社交網(wǎng)之所以變得如此受歡迎，是因為它們使人與人之間的關(guān)系變得更加緊密。此外，大量社會網(wǎng)站的普及以及在其平臺上提出的大量營銷需求都徹底顛覆了傳統(tǒng)的信息傳播模式。商家通過社會網(wǎng)能將商品或創(chuàng)意在極短的時間內(nèi)傳播給盡可能多的用戶。

社會網(wǎng)中一個引人關(guān)注的問題就是影響力最大化問題，這個問題會引起很多想要銷售他們的產(chǎn)品、服務(wù)、創(chuàng)新想法的公司或個人的興趣。它通過一個“word-of-mouth（口碑效應(yīng)）”的方式來進行商品或創(chuàng)意的傳播，而在線社會網(wǎng)絡(luò)恰恰提供了很好的平臺來處理這類問題。2001年，Domingos等人[1]將影響力最大化問題作為概率問題研究。2003年，Kempe等人[2]首次把這個問題形式化為一個離散優(yōu)化問題：給定有向圖G=(V，E)，正整數(shù)k，選擇大小為k的初始種集S，在給定傳播模型下，通過選取的種集S使盡可能多的節(jié)點受到影響。

影響力最大化問題已經(jīng)被廣泛研究[1-4]，但已有的研究往往忽略以下幾點：（1）不考慮用戶之間的有效傳播時間區(qū)間；（2）忽略了真實的營銷時間對選取初始用戶的影響；（3）傳統(tǒng)的影響力最大化問題并不適用于現(xiàn)實中的某些營銷模式，更沒有考慮營銷時間在這些營銷方式中的重要作用。

對于問題（1），通過對真實動作日志中大量的用戶和動作的分析，發(fā)現(xiàn)用戶和用戶之間存在有效的傳播時間區(qū)間。一個例子能幫助理解這一點。u和v是好朋友，由于工作較忙，u和v 3天以上才通一次電話，但每個周末u和v都一起吃飯，那么很明顯，由于信息傳播渠道的關(guān)系，u和v的傳播時間一定大于3天，且一般來說會小于7天。真實的數(shù)據(jù)也證實了這一點。表1是在Last.fm數(shù)據(jù)集上提取的幾個用戶動作信息。其中A到B有邊，C到D有邊，表中時間均為以0時刻為基準的相對時間，如(A,a)=2表示在0時刻后2個時間間隔的2時刻，用戶A執(zhí)行了動作a。

經(jīng)過分析，容易發(fā)現(xiàn)A傳播到B的動作時間都在[5,12]這個區(qū)間內(nèi)，也就是說營銷時間小于5，傳播發(fā)生的概率很小，可忽略不計；若在[5,12]的區(qū)間內(nèi)，則根據(jù)營銷時間動態(tài)調(diào)整傳播概率；若給定營銷時間超過12，則保持原有傳播概率不變。本文通過真實動作日志確定了每條邊上有效的傳播時間區(qū)間，再根據(jù)具體營銷時間動態(tài)進行影響力分配。

對于問題（2），同樣在真實的數(shù)據(jù)集Last.fm上進行了實驗，證實了本文的觀點。表2是運用本文提出的基于時間的影響力最大化算法在不同營銷時間限制下選擇的種集。設(shè)種集個數(shù)k=3，表中T代表營銷時間限制，例如10代表10個單位時間，S代表選擇的初始種集（用節(jié)點ID號表示）。

Table 2　 Marketing time T and seed set inLast.fm dataset (k=3)表2　在Last.fm數(shù)據(jù)集上不同的營銷時間與種集(k=3)

從表2中可以看出，在不同的營銷時間限制下，相應(yīng)選取的種集也不同。因此，根據(jù)不同的營銷時間來確定影響力的分配并選取相應(yīng)的種集是合理的。

針對問題（3），考慮一個真實生活中的營銷場景:小米手機自從上市以來一直受到人們的追捧和關(guān)注。原因在于小米手機選擇了一種不同的營銷方式——饑餓營銷。饑餓營銷是近幾年很有代表性的營銷方式，即供應(yīng)商在固定時間內(nèi)有意調(diào)低供應(yīng)量，以期制造供不應(yīng)求“假象”來長期維持商品較高利潤率的一種營銷策略。而在饑餓營銷的短期銷售過程內(nèi)，在商家規(guī)定了固定的銷售時間和期望的影響范圍（商品供應(yīng)量）這個條件下，人們可以找出銷售目標客戶中的最少初始用戶(最小的種集)來進行產(chǎn)品的初始傳播。不僅滿足了商家對短期銷售時間的要求，又達到了長期節(jié)省成本的目的。針對以上情景，本文提出了一種傳統(tǒng)影響力最大化問題的變體，即在饑餓營銷中基于時間的種集最小化問題。

本文主要貢獻如下:

（1）基于用戶的動作日志，確定用戶之間傳播的有效時間區(qū)間，并提出了一個基于時間的影響力分配模型（influence power allocating model based on time，IPAT）。根據(jù)該模型提出了基于時間的影響最大化問題（influence maximization problem based on time，IMPT），證明了該問題是NP-hard問題，并提出了求解IMPT問題的高效近似算法A-IMPT（algorithm for IMPT）。

（2）首次提出饑餓營銷中基于時間的種集最小化問題（seed set minimization problem in hungry marketing，SMPHM），證明了該問題為NP-hard問題，并提出了求解SMPHM問題的高效近似算法A-SMPHM （algorithm for SMPHM），同時證明了A-SMPHM的聯(lián)機近似比。

（3）多個真實的社會網(wǎng)數(shù)據(jù)集上的實驗結(jié)果表明，本文算法能有效并高效求解IMPT問題和SMPHM問題。

本文組織結(jié)構(gòu)如下:第2章介紹了相關(guān)工作；第3章給出了影響力分配模型及問題定義；第4章詳細闡述了A-IMPT和A-SMPHM算法；第5章給出了實驗及分析；第6章總結(jié)全文。

2　相關(guān)工作

2001年，Domingos等人[1]首次提出了在社會網(wǎng)上尋找具有重要影響力的用戶進行產(chǎn)品營銷的問題。Kempe等人[2]在2003年第一次將影響力最大化的問題定義為離散優(yōu)化問題。Kempe等人[3-4]證明了影響力最大化問題是NP-hard問題，并提出了具有1-1/e-ε近似比的貪心算法。雖然得到了較好的近似比，但由于使用了大量的蒙特卡洛模擬估計影響范圍，并不適用于大型社會網(wǎng)絡(luò)。2007年，Leskovec等人[5]提出CELF（cost-effective lazy forward）優(yōu)化對貪心算法進行了改進，大大提高了貪心算法的效率。Chen等人[6]在2009年提出了一個Degreediscount啟發(fā)式算法，運行速度非?？?，獲得了很高的擴展性。Chen等人[7]在2010年提出了基于IC模型的啟發(fā)式算法PMIA（prevalent marketing influence allocation），利用路徑估計影響傳播。Goyal等人[8]在2010年提出了獲取邊上影響概率的方法。Jiang等人[9]在2011年提出了一個基于模擬退火（simulated annealing）的方法解決影響最大化問題。2013年Li等人[10]提出具有遵從感知的影響力最大化問題，考慮了個人接受別人對自己影響的能力。2014年Li等人[11]提出關(guān)于地理感知的影響力問題，加入了地理信息因素。Feng等人[12]在2014年提出具有時間衰減的影響力最大化問題，但是他單純用一個衰減因子更新影響力，并沒有考慮到真實數(shù)據(jù)。2014年Barbieri等人[13]提出基于主題的影響力最大化問題，將問題細化到不同的主題分布上。

然而，上述所有模型都是人為設(shè)置用戶之間的傳播概率，這顯然是不合理的，在生活中用戶之間的相互影響是受到很多因素限制的。2012年Goyal等人[14]提出基于數(shù)據(jù)的方法進行影響力最大化問題的計算，通過分析真實動作日志直接計算節(jié)點的影響力。但卻沒有考慮影響傳播過程中時間因素對結(jié)果的影響。即用戶之間的影響具有有效傳播時間區(qū)間，營銷時間不同，最終選取的種集也不一樣。

而且，已有的研究一般只考慮解決傳統(tǒng)的影響力最大化問題，并不針對其他的營銷方式考慮相應(yīng)的解決方案，近年來越來越多的營銷方式的出現(xiàn)也證實了影響傳播在這些真實情境中的具體應(yīng)用價值，因此本文也首次提出了饑餓營銷中基于時間的種集最小化問題。

3　傳播模型及問題定義

本文給出兩種獲取有效傳播時間區(qū)間的度量，提出了基于時間的影響力分配模型，并給出了基于時間的影響最大化問題和饑餓營銷中基于時間的種集最小化問題的形式化定義。

3.1獲取有效傳播時間區(qū)間

給定有向圖G=(V,E)，動作日志A，A中每條記錄格式為(user,action,time)，例如(a,3,4)表示用戶a在4時刻執(zhí)行了動作3。本文利用動作日志和用戶的關(guān)系計算用戶之間的有效傳播時間區(qū)間，提出兩種獲取有效傳播時間區(qū)間的度量。

（1）最大最小值（maximumminimumvalue，MMV）

直觀地獲取兩個用戶歷史傳播時間間隔的最大和最小值作為有效傳播時間區(qū)間，定義如下：

其中，eu,v∈E表示從節(jié)點u到節(jié)點v有邊；區(qū)間作為u到v的有效傳播時間區(qū)間。

（2）平均值+標準差（average value standard value，AVSV）

最大最小值法可能會受到特殊傳播事件的干擾，因此提出平均值+標準差方法來更準確地表示有效傳播時間區(qū)間，定義如下：

其中，μu,v和δu,v分別表示u到v傳播時間間隔的均值和標準差，定義如下：最終

為u →v的有效傳播時間區(qū)間。圖1給出了一個具有有效傳播時間的例子。

Fig.1　 Social network with effective propagationtime interval圖1　帶有有效傳播時間區(qū)間的社會網(wǎng)

其中，tv1,v5=[5,10 ]表示節(jié)點v1到節(jié)點v5的有效傳播時間區(qū)間是5時刻之后10時刻之前。也就是說，v1做出某個動作后，v5通常會在5時刻之后10時刻之前采取該動作。若給定營銷時間少于5個單位時間，則傳播幾率很小，可忽略不計；若給定營銷時間在[5,10]區(qū)間內(nèi)，則應(yīng)根據(jù)營銷時間調(diào)整原有傳播概率（見式（7））；若給定營銷時間超過10單位時間，則應(yīng)保持原有傳播概率不變。

3.2影響力分配模型

在給出了用戶之間的有效傳播時間區(qū)間后，本文提出了一個基于時間的影響力分配模型IPAT。

給定有向圖G=(V,E)，一個營銷時間T，動作日志A。若營銷時間T小于用戶u→v之間的有效傳播時間，那么u→v的傳播幾率很小，設(shè)定為u→v不傳播。因此先將>T的所有邊從圖G中刪掉，得到新的圖G′=(V,E′)，圖G′中都是在給定時間T內(nèi)可能傳播的邊，接下來的操作在圖G′上進行。

在T時間內(nèi)如果圖G′中存在邊u→v，動作日志A中的某些動作將從節(jié)點u傳播到節(jié)點v，此時v反過來為節(jié)點u分配影響力，同時v也對u的祖先節(jié)點迭代地分配影響力。在固定時間T內(nèi)，定義直接影響v的節(jié)點集合為Nv={u|e′u,v∈E′}，那么節(jié)點v要對Nv中的∑每一個節(jié)點u分配影響力，定義為Ind，并且滿足u∈NvInd≤1。對于Ind的值有很多種分配方法，本文根據(jù)營銷時間T動態(tài)分配影響概率值，定義如下：

其中，Au是u執(zhí)行的動作數(shù)；分子表示在T時間內(nèi)u傳播到v的動作個數(shù)。為保證，還需要對進行規(guī)范化，定義如下：

分配直接影響力后，開始由節(jié)點v迭代地向u的祖先w分配間接影響力，從而更新節(jié)點的影響力。v對祖先w分配的間接影響力Ind定義如下：其中，Indu,u=1。最后，對于每個節(jié)點u，把T時間內(nèi)其他節(jié)點為u分配的影響力進行聚集，記為Inf，即為u在T時間∑內(nèi)的影響力。

類似的，對于種集S?V，也可以根據(jù)營銷時間T定義節(jié)點v對∑種集S分配的影響力，定義如下：

接下來利用圖1的例子來說明IPAT模型。已知有向圖G=(V,E)如圖1所示，動作日志A={(v2,a,0),(v1, a,1),(v3,a,2),(v4,a,2),(v5,a,6),(v2,b,2),(v1,b,3)}。設(shè)T=4，根據(jù)IPAT模型，由于=5>T，刪除v1→v5的邊。接下來按照IPAT模型舉例計算v4的影響力分配過程。首先，找到v4的直接鄰居集合{v1,v2}，即Nv4 ={v1,v2}。根據(jù)動作日志發(fā)現(xiàn)節(jié)點v1共執(zhí)行過a和b兩個動作，而由v1傳播到v4的動作只有a一個。根據(jù)式（7）可得Ind=1/2，Ind=1/2。分配直接影響力后，v4接著向自己的祖先節(jié)點分配間接影響力。因為v4向v2分配了直接影響力，v2向v1直接分配了影響力，所以v1是v4的祖先節(jié)點，v4應(yīng)向v1分配一次間接影響力。根據(jù)式（9）來更新v4對v1的影響力，即Ind=1/2+1/2×1/2=3/4，其他節(jié)點同理。

3.3問題定義

基于時間的影響最大化問題(IMPT)：給定有向圖G=(V,E)，動作日志A(user,action,time)，正整數(shù)k，固定的營銷時間T，在IPAT傳播模型下，計算影響范圍最大的種集S(|S | =k)。

饑餓營銷中基于時間的種集最小化問題(SMPHM)：給定有向圖G=(V,E)，動作日志A(user, action,time)，固定的營銷時間T，期望的影響范圍Q，在IPAT傳播模型下，計算能達到期望影響范圍Q的最小種集S。

定理1基于真實時間的影響最大化問題是NP-hard問題。

證明設(shè)時間T為社會網(wǎng)中所有用戶之間邊上有效傳播時間區(qū)間中的最大時間，即T=max{t|eu,v∈E}，那么IPAT模型也就等價于Goyal提出的CD （credite distribution）影響力傳播模型[11]。因此，CD傳播模型下的影響力最大化問題是基于時間的影響最大化問題的特殊情況。CD傳播模型下的影響力最大化問題已經(jīng)被證明是NP-hard問題，因此IMPT問題也是NP-hard問題。

定理2饑餓營銷中基于時間的種集最小化問題是NP-hard問題。

證明如果SMPHM不是NP- hard問題，則SMPHM存在多項式時間算法A，使用算法A容易構(gòu)造求解IMPT問題的多項式時間算法。過程如下：給定IMPT問題的一個實例(G(V,E) ,A,k,T)。設(shè)期望影響范圍Q的取值從最大變化到最小(即Q∈{|V | ,|V | -1, |V| -2,…,1})，則可構(gòu)造一系列SMPHM的實例(G(V,E) ,A,T,Q)。對SMPHM每個實例(G(V,E) ,A,Q)運行算法A，如果SMPHM的某個實例輸出種集S大小為k，則顯然S為IMPT問題實例(G(V,E) ,A,k,T)的最優(yōu)解。上述過程最多調(diào)用|V|次算法A，顯然整個求解過程仍是多項式時間。

根據(jù)定理1，IMPT問題是NP-hard問題，不存在多項時間算法。因此，SMPHM不存在多項式時間算法A，SMPHM問題是NP-hard問題。

4　基于真實時間的A-IMPT和A-SMPHM算法

本文給出求解基于時間的影響最大化問題的算法A-IMPT以及饑餓營銷中基于時間的種集最小化問題的算法A-SMPHM。

首先輸入真實的營銷時間T，單位時間可以是小時、天、周等，可以依據(jù)具體的應(yīng)用來確定。A-IMPT算法主要分3個階段。第一階段（第1~5行）對圖G進行預(yù)處理，根據(jù)T來對圖G=(V,E)進行刪減得到圖G′=(V,E′)。第二階段（第6行）建立入度鏈表Inde_list，根據(jù)IPAT模型和營銷時間T為節(jié)點分配影響力。同時計算節(jié)點的初始影響增益存入優(yōu)先級隊列queue。第三階段（第7~10行）采用CELF優(yōu)化方法貪心選取種集。每當選取一個種子節(jié)點后，迭代更新其他節(jié)點的影響增益。A-IMPT算法的偽代碼如下所示。

算法1 A-IMPT算法

輸入:社會網(wǎng)G=(V,E)，歷史動作日志A，營銷時間T，正整數(shù)k。

輸出:T時間內(nèi)具有最大影響范圍的種集S(|S | =k)。

1. For each (u,v)∈E

4.刪除邊(u,v);

5.最后得到的圖記為G′=(V,E′) ;

6. (Inde_list ,queue)= parentslink(G′,A);

7. S←?;

8. While (|S|< k )

9. S=S?CELF(G′,Inde_list, queue, S);

10. Return S;

算法2給出了饑餓營銷中基于時間的種集最小化問題的算法A-SMPHM，大體思想與算法1相似。為了簡便，算法2略去了得到圖G′的過程，只給出核心思想。算法第3~4行比較當前種集的影響范圍S.mg與輸入的期望影響范圍Q。如果S.mg

算法2 A-SMPHM算法

輸入：社會網(wǎng)G′=(V,E′)，動作日志A，營銷時間T，期望的影響范圍Q。

輸出：T時間內(nèi)，能夠達到期望范圍Q的最小種集S。

1. S←?;

2. (Inde_list ,queue) = parentslink(G′,A);

3. While ( S.mg < Q)

4. S=S?CELF(G’,Inde_list,queue,S);

5. Return S;

4.1建立入度鏈表,更新節(jié)點初始影響增益

算法parentslink掃描圖G′=(V,E′)，對每個節(jié)點建立入度鏈表Inde_list，掃描動作日志，為每個節(jié)點分配影響力。同時計算節(jié)點的初始影響增益。

算法（第1~6行）建立入度鏈表，掃描動作日志，分配影響力。為了方便計算，先將動作日志按照動作進行排序，再按照執(zhí)行動作的時間進行排序，根據(jù)式（7）計算節(jié)點之間的直接影響力，之后根據(jù)式（9）計算節(jié)點之間的間接影響力。因為G′已經(jīng)根據(jù)營銷時間處理過，所以可對鏈表中每個節(jié)點迭代地分配直接影響力，然后更新間接影響力。

算法（第7~10行）利用Co-influence算法計算每個節(jié)點v∈V的初始影響增益v.mg，利用優(yōu)先級隊列queue，以每個節(jié)點的影響增益v.mg為基準進行由大到小排序。并標記計算每個節(jié)點v影響增益的輪數(shù)v.round為0。具體偽代碼如算法3所示。

算法3 parentslink算法

輸入：G′=(V,E′)，動作日志A。

輸出：每個節(jié)點v∈V的影響力值分配鏈表Inde_list[v]，優(yōu)先級隊列queue。

1. For each v∈V

2.建立節(jié)點v的入度鏈表Inde_list[v];

3. For each u∈Inde_list[v] ;

5. For each w∈Inde_list[u]

7. queue←?;

8. For each v∈V

9. v.mg =Co-influence(Inde_list,v ,?);

10. v.round =0; push(queue,v);

4.2 CELF優(yōu)化選取最大影響增益節(jié)點

本節(jié)利用CELF優(yōu)化貪心選取節(jié)點。CELF優(yōu)化利用了InfS的子模性，每一輪不需要重新計算所有節(jié)點的影響增益，有效地提高了算法效率。CELF算法分兩個階段。第一階段（第1~3行）取隊列頭節(jié)點v，如果v的影響增益計算輪數(shù)v.round等于當前種集數(shù)，則v對當前種集S來說是增益最大的節(jié)點。返回v，并利用算法Update更新其他節(jié)點u∈VS的影響力入度鏈表Inde_list，刪除所有通過v分配的影響力，同時更新節(jié)點u對種集S的影響力分配值Ind。第二階段（第5~7行）如果v.round不等于當前種集數(shù)，說明v的增益v.mg不是針對當前種集S的影響增益。此時利用算法Co-influence重新計算v針對當前種集S的影響增益，更新節(jié)點v的影響增益計算輪數(shù)v.round，并將節(jié)點v重新插入到優(yōu)先級隊列queue，返回第1行重新求增益最大的節(jié)點。重復(fù)以上過程直到選出一個針對當前種集S具有最大影響增益的節(jié)點。具體過程如算法4所示。

算法4CELF算法

輸入：社會網(wǎng)G′=(V,E′)影響力值分配鏈表Inde_list，優(yōu)先級隊列queue，當前種集S。

輸出：當前具有最大增益的種子節(jié)點v。

1. v = pop(queue);

2. If (v.round == |S|)

3. Update(Inde_list, v, S);

4. Else

5. v.mg = Co-influence(Inde_list, v, S);

6. v.round = |S|; push(queue,v);

7. Goto 1;

8. Return v;

4.3計算節(jié)點v針對當前種集S的影響增益

本節(jié)采用Co-influence算法計算節(jié)點v針對當前種集S的影響增益。算法第5行去除節(jié)點v對種集S的影響力分配值Ind，得到節(jié)點v對種集S的影響增益v.mg。算法的具體過程如算法5所示。

算法5 Co-influence算法

輸入:節(jié)點v，影響力分配鏈表Inde_list，當前種集S。

輸出: v針對種集S的影響范圍增益v.mg。

1. margin = 0;

2. For each u∈V

3. If (v∈Inde_list[u])

4. margin +=節(jié)點u分配給v的影響力;

6. Return v.mg;

4.4更新影響力

當節(jié)點v加入種子集合后，本節(jié)利用算法Update更新其他節(jié)點u∈VS的影響力入度鏈表Inde_list。算法第2~4行先刪除節(jié)點u通過v分配的影響力，第5行更新節(jié)點u對種集S的影響力分配值Ind。Update算法的具體過程如算法6所示。

算法6 Update算法

輸入：節(jié)點v，影響力分配鏈表Inde_list，當前種集S。

輸出：影響力分配鏈表Inde_list。

1. For each u∈V

2. If(v∈Inde_list[u])

3. For each w∈Inde_list[v]

4.刪除Inde_list[u]中通過v分給w的影響力;

4.5時間復(fù)雜性和近似比計算

A-IMPT和A-SMPHM算法的時間復(fù)雜度都為O(|S ||V ||A | γ)，其中|S|為種子節(jié)點個數(shù)，|V|是圖中節(jié)點個數(shù)，|A|是動作日志記錄數(shù)，γ是所有節(jié)點中祖先節(jié)點的最大值max{|Inde_list[u]| ,u∈V}，即最大的Inde_list的長度。

定理3 IM-IMF算法的近似比為1-1/e。

證明當營銷時間T為常數(shù)時，根據(jù)文獻[10]的定理2容易證明InfS的子模性和單調(diào)性，因此可以用貪心算法找到近似解，近似解和最優(yōu)解的比值為1-1/e。

5　實驗與結(jié)果分析

本文在兩個社會網(wǎng)數(shù)據(jù)集上進行實驗，并與多種算法進行比較，驗證了算法的有效性和高效性。

5.1數(shù)據(jù)集及實驗環(huán)境

本文使用兩個真實社會網(wǎng)絡(luò)數(shù)據(jù)集進行實驗，表3給出了數(shù)據(jù)集的信息。Last.fm[12]是音樂評論網(wǎng)站，本文提取了2 100個節(jié)點，25 435條邊和動作日志記錄。若用戶u在時間t評論了歌手a，并且用戶u的朋友v在時間t后也評價了歌手a，那么就認為這個動作從u傳播到了v。Digg中文翻譯為“掘客”，是新聞評論網(wǎng)站，本文提取了35 000個用戶，3 905 513條邊，其評論傳播過程與Last.fm相似。

Table 3　 Last.fm dataset and Digg dataset表3　 Last.fm數(shù)據(jù)集和Digg數(shù)據(jù)集

實驗中所有算法用C語言編寫，在Microsoft Visual C++ 6.0環(huán)境下編譯。所有實驗都在Intel?CoreTM2 Duo CPU，4 GB主存的臺式機上運行。

5.2比較算法

實驗選擇了6種已有的算法和本文A-IMPT算法進行比較，比較算法介紹如下。

（1）IM-CD（influence maximize credit distribution）[14]：利用動作日志，為每個節(jié)點在每個動作上建立鏈表，分配影響力直接求得影響范圍，再用CELF優(yōu)化算法求種集。

（2）GeneralGreedy[3]：貪心方法求種集。

（3）GreedyCELF[5]：CELF優(yōu)化貪心方法求種集。

（4）DegreeDiscount[6]：啟發(fā)式度折扣方法求種集。

（5）SimulatedAnnealing[9]：模擬退火法求種集。

（6）Degree：直接根據(jù)節(jié)點度的大小選擇種集。

為了公平比較，以上所有比較算法中都用有效傳播時間區(qū)間中的進行刪圖，也就是所有的算法都在圖G′=(V,E′)上進行。在本文的所有實驗中，如果沒有特殊說明，均采用3.1節(jié)的AVSV方法計算有效傳播時間區(qū)間。參考文獻[3,5-6,9]中對參數(shù)的設(shè)置，設(shè)置GeneralGreedy、GreedyCELF、SimulatedAnnealing中邊上傳播概率p=0.1。GeneralGreedy算法中蒙特卡洛模擬次數(shù)為R=10 000。在SimulatedAnnealing算法中設(shè)置起始溫度t0=100，終止溫度tf=10，遞減溫度tm=2。

5.3時間及種集大小對影響范圍的影響(AIMPT)算法

本節(jié)驗證了時間和種集大小對影響范圍的影響，并與其他算法比較，驗證了A-IMPT算法的有效性。

首先，對不同營銷時間下種集的影響范圍進行比較。圖2（a）給出了A-IMPT算法和6種方法在Last. fm數(shù)據(jù)集上求得種集影響范圍的比較，圖2（b）給出在Digg數(shù)據(jù)集上的比較。其中，設(shè)置種集個數(shù)k=5。

Fig.2　 Spread and time T in Last.fm and Digg datasets (k=5)圖2　在Last.fm和Digg數(shù)據(jù)集上影響范圍與營銷時間T(k=5)

從圖2可以看出，因為所有算法都利用有效傳播時間區(qū)間對圖G進行了刪減，隨著時間增加，被刪減的圖結(jié)構(gòu)越來越少，圖G’逐漸增大，所以無論在哪個數(shù)據(jù)集上，所有算法求得的影響范圍都隨著營銷時間的增加而不斷增長，這也是符合真實情景的。其中Degree和DegreeDiscount選取種集的影響范圍都比較差，因為這兩種算法是完全基于節(jié)點的度來計算種集，只考慮節(jié)點的度而并不考慮其他因素；General-Greedy、GreedyCELF和SimulatedAnnealing影響范圍差別不大，但都遠遠小于IM-CD和A-IMPT算法，是因為這幾種算法只考慮圖的拓撲結(jié)構(gòu)，且人為設(shè)定邊上概率，并不符合真實生活中的情景；IM-CD基于數(shù)據(jù)求影響范圍，但其單純將分配的影響力設(shè)置為1/入度，由于圖結(jié)構(gòu)較大，1/入度是很小的數(shù)，導(dǎo)致了影響范圍也較小，且IM-CD算法并沒有考慮時間因素；A-IMPT算法利用真實動作日志分配影響力，經(jīng)過比較，A-IMPT算法要優(yōu)于IM-CD算法。

下面考察種集大小對影響范圍的影響。圖3顯示了在Last.fm數(shù)據(jù)集上，相同營銷時間下種子個數(shù)不同對影響范圍的影響。其中設(shè)置營銷時間T=10。通過圖3可以看出當營銷時間T相同時，由于A-IMPT算法利用了真實的動作日志分配了影響力，并迭代更新了節(jié)點的影響增益，相比于其他方法，A-IMPT更符合真實情景中對影響力的分配方式，得到了比其他算法更好影響范圍。

Fig.3　 Spread and seedsize k in Last.fm dataset (T=10)圖3　在Last.fm數(shù)據(jù)集上影響范圍與種子個數(shù)k(T=10)

5.4時間及種集大小對運行時間的影響(AIMPT算法)

本節(jié)主要比較了時間和種集大小對運行時間的影響，并驗證了A-IMPT算法的高效率。

首先固定種集個數(shù)k，觀察不同的營銷時間和運行時間之間的關(guān)系。圖4是Last.fm數(shù)據(jù)集上，營銷時間T和運行時間之間關(guān)系的比較。明顯的，General-Greedy使用蒙特卡洛模擬的方法估計影響范圍，導(dǎo)致時間非常長，當T>10，圖中的絕大部分邊都被保留，運行時間超過了1 000 s，且呈指數(shù)級上漲，因此圖中沒有給出，GreedyCELF由于部分過程需要用蒙特卡洛模擬，時間也達到100 s以上；SimulatedAnnealing由于要不斷更換種集節(jié)點，運行時間也并不理想；IM-CD算法不考慮時間因素，需要掃描每個動作并為每個節(jié)點的每個動作建立影響力分配鏈表，因此IM-CD算法建立了|V|×|A|個鏈表用來分配影響力，其中|V|是節(jié)點個數(shù)，|A|是動作日志條數(shù)，而動作日志條數(shù)往往高達幾十萬條，這也就導(dǎo)致了運行速度并不理想。而A-IMPT算法提前處理了動作日志，刪減了圖結(jié)構(gòu)，且只為每個節(jié)點分配影響力分配鏈表，即只建立最多|V|個鏈表來分配影響力，因此掃描鏈表的過程中大大提高了時間；DegreeDiscount和Degree算法雖然運行速度比A-IMPT算法快，但是卻沒有近似比的保證，影響范圍遠遠沒有A-IMPT算法好。

Fig.4　 Running time and time T in Last.fm dataset (k=5)圖4　在Last.fm數(shù)據(jù)集上運行時間與營銷時間T(k=5)

接下來討論當營銷時間相同時，種集大小與運行時間之間的關(guān)系。圖5是在Last.fm數(shù)據(jù)集上，種集大小和運行時間之間的關(guān)系比較結(jié)果。結(jié)合圖3和圖5可以看到，A-IMPT算法在真實的數(shù)據(jù)集上獲得了理想的影響范圍的同時大大減少了運行時間，提高了算法的效率。

本文在Digg數(shù)據(jù)集上也做了相同的實驗，得到了類似的實驗結(jié)果。由于篇幅有限，這里沒有列出。

Fig.5　 Running time and seedsize k in Last.fmdataset (T=10)圖5　在Last.fm數(shù)據(jù)集上運行時間與種集個數(shù)k (T=10)

5.5營銷時間對種集大小和運行時間的影響(A-SMPHM算法)

由于目前尚沒有算法提出解決饑餓營銷模式中的影響力傳播問題，因此將IM-CD、GeneralGreedy、GreedyCELF和Degree算法進行了調(diào)整，并用有效傳播時間區(qū)間中的?進行了刪圖（詳見算法1）。從而適應(yīng)本文提出的SMPHM問題，并與A-SMPHM算法進行了比較。實驗中，參考文獻[3,5-6,9]中對參數(shù)的設(shè)置，設(shè)邊上的傳播概率p=0.1。蒙特卡洛模擬次數(shù)R=10 000。

圖6（a）是在Last.fm數(shù)據(jù)集上固定期望影響范圍Q=100，比較營銷時間T和選取的最小種子節(jié)點個數(shù)之間的關(guān)系。圖6（b）是在Digg數(shù)據(jù)集上的相同實驗。其中設(shè)置Q=3 000。從圖6中可知，無論在哪個數(shù)據(jù)集上，固定相同的影響范圍和營銷時間，ASMPHM算法都比其他方法獲得了更小的種集，也就是說A-SMPHM算法有效地獲得了更小的初始用戶來達到營銷中期望達到的影響范圍。從而證明了ASMPHM算法的有效性。而從現(xiàn)實生活角度來說，更小的初始用戶意味著更低的初期成本和更高的利潤，這也是商家希望看到和實現(xiàn)的。

圖7是在Last.fm數(shù)據(jù)集上關(guān)于營銷時間和運行時間的實驗結(jié)果。

從圖7中可知，A-SMPHM算法效率比General-Greedy算法至少提高3個數(shù)量級。Degree算法基于節(jié)點的度排序選擇種集，運行速度快，但求得的影響范圍較差。但SMPHM問題需將每輪影響范圍與期望影響范圍比較，由于Degree算法不能得到較好的影響范圍，導(dǎo)致它需要向種集不斷地加入節(jié)點以滿足期望的影響范圍，運行時間并不理想。圖6和圖7證明了A-SMPHM算法有效解決了饑餓營銷中基于時間的種集最小化問題，既以更小的種集達到了期望的影響范圍，又達到了理想的效率。

Fig.6　 Time T and seedsize k in Last.fm andDigg datasets圖6　在Last.fm和Digg數(shù)據(jù)集上營銷時間T與種集個數(shù)k

Fig.7　 Running time and time T in Last.fm dataset (Q=100)圖7　在Last.fm數(shù)據(jù)集上運行時間與營銷時間T(Q=100)

5.6比較MMV和AVSV度量方法和準確性

3.1節(jié)給出兩種計算有效傳播時間區(qū)間的度量方法，本節(jié)實驗比較兩種度量方法的準確性。為了更好地進行比較，用IM-CD算法作為一個比較算法。首先將Last.fm數(shù)據(jù)集中的動作按照4:1比例分為訓(xùn)練集和測試集。在訓(xùn)練集中分別使用IM-CD算法和分別加入兩種度量的A-IMPT算法得到相應(yīng)的種集，然后在測試集中求得種集的真實影響范圍，設(shè)置營銷時間T=10。圖8給出了在測試集上兩種度量方法求得的影響范圍的大小。

Fig.8　 Real spread and seedsize k in Last.fm testing set (T=10)圖8　在Last.fm測試集上影響范圍與種子個數(shù)k(T=10)

從圖8中可知，在A-IMPT算法中無論是運用最大最小值方法還是平均值+標準差方法都獲得了更好的真實影響范圍，而IM-CD算法沒有考慮時間因素，在測試集中的真實影響范圍并不如A-IMPT算法好。比較兩種度量方式，平均值+標準差的方法獲得了更好的真實影響范圍，也就是說，平均值+標準差這種度量的準確性更好。

6　結(jié)束語

本文基于真實用戶動作日志，確定了用戶有效的傳播時間區(qū)間，并提出了基于時間的影響力分配模型IPAT。根據(jù)IPAT模型，本文提出了基于時間的影響力最大化問題（IMPT）以及饑餓營銷中基于時間的種集最小化問題（SMPHM），并證明了它們是NP-hard問題。本文提出了求解IMPT問題的有效近似算法A-IMPT，以及求解SMPHM問題的有效近似算法A-SMPHM，并嚴格證明了A-IMPT和A-SMPHM算法的近似比。多個真實社會網(wǎng)數(shù)據(jù)集上的實驗表明：本文算法能有效并高效求解IMPT問題和SMPHM問題。未來研究工作將考慮基于主題分布和營銷時間，對用戶之間影響力進行更合理的分配，從而更準確地預(yù)測最佳種集。

References:

[1] Domingos P, Richardson M. Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, San Francisco, USA, Aug 26-29, 2001. New York, USA: ACM, 2001: 57-66.

[2] Kempe D, Kleinberg J, Tardos é. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, Aug 24-27, 2003. New York, USA:ACM, 2003: 137-146.

[3] Kempe D, Kleinberg J M, Tardos E. Influential nodes in a diffusion model for social networks[C]//LNCS 3580: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lisbon, Portugal, Jul 11-15, 2005. Berlin, Heidelberg: Springer, 2005: 1127-1138.

[4] Kimura M, Saito K. Tractable models for information diffusion in social networks[C]//LNCS 4213: Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, Sep 18-22, 2006. Berlin, Heidelberg: Springer, 2006: 259-271.

[5] Leskovec J, Krause A, Guestrin C. Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, San Jose, USA, Aug 12-15, 2007. New York, USA: ACM, 2007: 420-429.

[6] Chen Wei, Wang Yang. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Paris, France, Jun 28-Jul 1, 2009. New York, USA: ACM, 2009: 199-208.

[7] Chen Wei, Wang Chi, Wang Yajun. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Wash-ington, USA, Jul 25-28, 2010. New York, USA: ACM, 2010: 1029-1038.

[8] Goyal A, Bonchi F, Lakshmanan L V S. Learning influence probabilities in social networks[C]//Proceedings of the 3th ACM International Conference on Web Search and Data Mining, New York, USA, Feb 3-6, 2010. New York, USA: ACM, 2010: 241-250.

[9] Jiang Qiang, Song Ge, Wang Yang. Simulated annealing based influence maximization in social networks[C]//Proceedings of the 25th Conference on Artificial Intelligence, San Francisco, USA, Aug 7-11, 2011. Menlo Park, USA: AAAI, 2011: 318-326.

[10] Li Hui, Bhowmick S S, Sun Aixin. CINEMA: conformityaware greedy algorithm for influence maximization in online social networks[C]//Proceedings of the 16th International Conference on Extending Database Technology, Genoa, Italy, Mar 18-22, 2013. New York, USA:ACM, 2013: 323-334

[11] Li Guoliang, Chen Shuo, Feng Jianhua, et al. Efficient locationaware influence maximization[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, Snowbird, USA, Jun 22- 27, 2014. New York, USA:ACM, 2014: 87-98.

[12] Feng Shanshan, Chen Xuefeng, Cong Gao, et al. Influence maximization with novelty decay in social networks[C]// Proceedings of the 28th Conference on Artificial Intelligence, Quebec City, Canada, Jul 27-31, 2014. Menlo Park, USA:AAAI, 2014: 37-43.

[13] Aslay C, Barbieri N, Bonchi F, et al. Online topic-aware influence maximization queries[C]//Proceedings of the 17th International Conference on Extending Database Technology, Athens, Greece, Mar 24-28, 2014: 295-306.

[14] Goyal A, Bonchi F, Lakshmanan L V S. A data-based approach to social influence maximization[J]. Proceedings of the VLDB Endowment, 2011, 5(1): 73-84.

LIU Yong was born in 1975. He received the Ph.D. degree in computer science from Harbin Institute of Technology in 2010. Now he is an associate professor and M.S. supervisor at School of Computer Science and Technology, Heilongjiang University. His research interests include data mining and database, etc.劉勇（1975—），男，河北昌黎人，2010年于哈爾濱工業(yè)大學(xué)計算機科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為黑龍江大學(xué)計算機科學(xué)技術(shù)學(xué)院副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為數(shù)據(jù)挖掘，數(shù)據(jù)庫等。

QU Sitong was born in 1992. She is an M.S. candidate at School of Computer Science and Technology, Heilongjiang University. Her research interest is data mining.曲思桐（1992—），女，黑龍江哈爾濱人，黑龍江大學(xué)計算機科學(xué)技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘。

WANG Nan was born in 1980. She is a Ph.D. candidate at School of Electronic Engineering, Heilongjiang University. Her research interests include sensor network and social network, etc.王楠（1980—），女，黑龍江哈爾濱人，黑龍江大學(xué)電子工程學(xué)院博士研究生，主要研究領(lǐng)域為傳感器網(wǎng)絡(luò)，社會網(wǎng)絡(luò)等。

GUO Longjiang was born in 1973. He received the Ph.D. degree in computer science from Harbin Institute of Technology in 2007. Now he is a professor and M.S. supervisor at School of Computer Science and Technology, Heilongjiang University. His research interests include data mining, parallel and distributed computing, etc.郭龍江（1973—），男，河北豐寧人，2007年于哈爾濱工業(yè)大學(xué)計算機科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為黑龍江大學(xué)計算機科學(xué)技術(shù)學(xué)院教授、碩士生導(dǎo)師，主要研究領(lǐng)域為數(shù)據(jù)挖掘，并行與分布式計算等。

Research on Time-Based Influence Propagation Methods in Different Marketing Mode?

LIU Yong+, QU Sitong, WANG Nan, GUO Longjiang
School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China
+ Corresponding author: E-mail: acliuyong@sina.com

LIU Yong, QU Sitong, WANG Nan, et al. Research on time-based influence propagation methods in different marketing mode. Journal of Frontiers of Computer Science and Technology, 2016, 10(3): 338-349.

Abstract:Influence maximization is the problem of finding a small set of influential users in a social network that maximizes the expected spread. However, the existing works often ignore the effective propagation time interval between uses, and also don’t take influence of the marketing time on the initial seed users into consideration. This paper uses real action log to determine the effective propagation time interval between users, and proposes an influence power allocating model based on time, called IPAT. According to the IPAT model, this paper proposes an influence maximization problem based on time (IMPT) and a seed set minimization problem in hungry marketing (SMPHM), and proves that these two problems are NP-hard. In order to solve IMPT and SMPHM, this paper proposes two effective approximation algorithms, called A-IMPT and A-SMPHM respectively, and theoretically shows that the approximation ratio of the proposed algorithms A-IMPT and A-SMPHM. The experimental results in several datasets on real social networks validate the effectiveness and efficiency of A-IMPT and A-SMPHM.

Key words:social network; influence propagation; propagation time interval; marketing time; hungry marketing

doi:10.3778/j.issn.1673-9418.1507076

文獻標志碼：A

中圖分類號：TP311