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

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

ISSN 1673-9418 CODEN JKYTA8

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

?

不同營(yíng)銷模式中基于時(shí)間的影響傳播方法研究*

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

黑龍江大學(xué)計(jì)算機(jī)科學(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ù)研究項(xiàng)目).

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的研究工作沒有考慮用戶之間有效的傳播時(shí)間區(qū)間，而且忽略了營(yíng)銷時(shí)間對(duì)于選取初始用戶的影響?；谡鎸?shí)用戶動(dòng)作日志，確定了用戶之間有效的傳播時(shí)間區(qū)間，并提出了一個(gè)基于時(shí)間的影響力分配模型（influence power allocating model based on time，IPAT）。根據(jù)該模型，提出了基于真實(shí)時(shí)間的影響力最大化問題（influence maximization problem based on time，IMPT）和饑餓營(yíng)銷模式中種集最小化問題（seed set minimization problem in hungry marketing，SMPHM），并證明了這兩個(gè)問題都是NP-hard問題。為求解IMPT問題和SMPHM問題，分別提出了有效的近似算法A-IMPT（algorithm for IMPT）和A-SMPHM（algorithm for SMPHM），并證明了算法A-IMPT和A-SMPHM的近似比。多個(gè)真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了算法AIMPT和A-SMPHM的有效性和高效率。

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

1　引言

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

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

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

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

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

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

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

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

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

本文主要貢獻(xiàn)如下:

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

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

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

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

2　相關(guān)工作

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

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

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

3　傳播模型及問題定義

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

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

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

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

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

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

（2）平均值+標(biāo)準(zhǔn)差（average value standard value，AVSV）

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

其中，μu,v和δu,v分別表示u到v傳播時(shí)間間隔的均值和標(biāo)準(zhǔn)差，定義如下：最終

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

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

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

3.2影響力分配模型

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

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

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

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

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

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

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

3.3問題定義

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

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

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

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

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

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

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

4　基于真實(shí)時(shí)間的A-IMPT和A-SMPHM算法

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

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

算法1 A-IMPT算法

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

輸出:T時(shí)間內(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給出了饑餓營(yíng)銷中基于時(shí)間的種集最小化問題的算法A-SMPHM，大體思想與算法1相似。為了簡(jiǎn)便，算法2略去了得到圖G′的過程，只給出核心思想。算法第3~4行比較當(dāng)前種集的影響范圍S.mg與輸入的期望影響范圍Q。如果S.mg

算法2 A-SMPHM算法

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

輸出：T時(shí)間內(nèi)，能夠達(dá)到期望范圍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é)點(diǎn)初始影響增益

算法parentslink掃描圖G′=(V,E′)，對(duì)每個(gè)節(jié)點(diǎn)建立入度鏈表Inde_list，掃描動(dòng)作日志，為每個(gè)節(jié)點(diǎn)分配影響力。同時(shí)計(jì)算節(jié)點(diǎn)的初始影響增益。

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

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

算法3 parentslink算法

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

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

1. For each v∈V

2.建立節(jié)點(diǎn)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é)點(diǎn)

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

算法4CELF算法

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

輸出：當(dāng)前具有最大增益的種子節(jié)點(diǎn)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計(jì)算節(jié)點(diǎn)v針對(duì)當(dāng)前種集S的影響增益

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

算法5 Co-influence算法

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

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

1. margin = 0;

2. For each u∈V

3. If (v∈Inde_list[u])

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

6. Return v.mg;

4.4更新影響力

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

算法6 Update算法

輸入：節(jié)點(diǎn)v，影響力分配鏈表Inde_list，當(dāng)前種集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時(shí)間復(fù)雜性和近似比計(jì)算

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

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

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

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

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

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

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

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

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

5.2比較算法

實(shí)驗(yàn)選擇了6種已有的算法和本文A-IMPT算法進(jìn)行比較，比較算法介紹如下。

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

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

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

（4）DegreeDiscount[6]：?jiǎn)l(fā)式度折扣方法求種集。

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

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

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

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

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

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

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

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

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

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

5.4時(shí)間及種集大小對(duì)運(yùn)行時(shí)間的影響(AIMPT算法)

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

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

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

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

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

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

5.5營(yíng)銷時(shí)間對(duì)種集大小和運(yùn)行時(shí)間的影響(A-SMPHM算法)

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

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

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

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

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

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

5.6比較MMV和AVSV度量方法和準(zhǔn)確性

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

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

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

6　結(jié)束語

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

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é)計(jì)算機(jī)科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院副教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)閿?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é)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?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)域?yàn)閭鞲衅骶W(wǎng)絡(luò)，社會(huì)網(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é)計(jì)算機(jī)科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，并行與分布式計(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

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP311