劉 勇，謝勝男，張 巍，朱敬華，王 楠

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

社會(huì)網(wǎng)中時(shí)間最優(yōu)的利潤(rùn)最大化算法研究*

劉 勇+，謝勝男，張 巍，朱敬華，王 楠

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

影響最大化問(wèn)題是在社會(huì)網(wǎng)上尋找最具影響力的種集。目前的研究工作忽略了影響傳播最大化和利潤(rùn)最大化的區(qū)別，以及影響范圍會(huì)隨著時(shí)間的推移趨于平穩(wěn)?？紤]用戶動(dòng)作日志，提出了基于時(shí)間長(zhǎng)度的影響力分配模型IVA-T（influence value allocation-T），在此基礎(chǔ)上首次提出了時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題（time optimal profit maximization，OTPM），并證明了該問(wèn)題為NP-hard問(wèn)題。為求解OTPM問(wèn)題，提出了一個(gè)有效的近似算法Profit-Max，并證明了Profit-Max算法的近似比。多個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法可以有效并高效地解決OTPM問(wèn)題。

社會(huì)網(wǎng)；利潤(rùn)最大化；動(dòng)作日志；時(shí)間長(zhǎng)度

1 引言

最近幾年，一些規(guī)模較大的社會(huì)網(wǎng)流行起來(lái)，如微信、Instagram、微博等。這些網(wǎng)絡(luò)將人們以各種方式聯(lián)系起來(lái)，進(jìn)行信息交互和資源共享。進(jìn)一步，使得社會(huì)網(wǎng)的研究具有較大意義，可以通過(guò)對(duì)社會(huì)網(wǎng)中用戶之間的聯(lián)系，估計(jì)影響傳播概率，進(jìn)行一些新思想或是新商品的傳播。

基于上述思想，Domingos等人[1]在2001年首次提出了病毒性市場(chǎng)營(yíng)銷這一概念。在社會(huì)網(wǎng)中選取k個(gè)有影響力的用戶，免費(fèi)給他們使用待推廣產(chǎn)品，通過(guò)社會(huì)網(wǎng)中的口碑效應(yīng)，使最多的用戶接受并購(gòu)買該產(chǎn)品。2003年，Kempe等人[2]將上述問(wèn)題形式化為影響最大化問(wèn)題：給定有向圖G(V,E)，正整數(shù)k，選擇一組節(jié)點(diǎn)數(shù)為k的集合，即為種集，在給定的影響傳播模型下，最終達(dá)到最大的影響范圍。文獻(xiàn)[3-7]針對(duì)影響最大化問(wèn)題進(jìn)行了進(jìn)一步的研究，對(duì)不同應(yīng)用背景下的影響最大化提出了相應(yīng)的解決方案。然而，上述文獻(xiàn)的解決方法并沒(méi)有考慮以下兩個(gè)問(wèn)題：（1）在求種集的影響范圍時(shí)，沒(méi)有考慮成本問(wèn)題；（2）忽略了營(yíng)銷時(shí)間對(duì)影響范圍的影響。

在現(xiàn)實(shí)應(yīng)用中，促銷成本一定會(huì)隨著時(shí)間推移而增加，而種集的影響范圍會(huì)變得平穩(wěn)，以下的實(shí)驗(yàn)證實(shí)了這一觀點(diǎn)。在真實(shí)數(shù)據(jù)集Digg上做了如下實(shí)驗(yàn)：利用文獻(xiàn)[8]中的算法選擇具有最大影響力的10個(gè)節(jié)點(diǎn)組成種集，選擇了長(zhǎng)度遞增的7個(gè)時(shí)間段，用以觀察種集的影響范圍隨時(shí)間的變化，實(shí)驗(yàn)結(jié)果如表1所示。其中，T表示不同的時(shí)間長(zhǎng)度，Spread為影響范圍，表示被影響的節(jié)點(diǎn)數(shù)量。

Table 1 Spread vs different timespan T in Digg dataset表1 在Digg數(shù)據(jù)集上影響范圍vs不同的時(shí)間長(zhǎng)度

從表1可以得出結(jié)論，影響范圍會(huì)隨著時(shí)間的推移而逐漸趨于平穩(wěn)。從中可以得出另一重要結(jié)論，對(duì)于不同的時(shí)間長(zhǎng)度，最終選擇的種集也是不一樣，具體實(shí)驗(yàn)結(jié)果見5.4節(jié)。因此，在市場(chǎng)營(yíng)銷應(yīng)用中，選擇最佳的促銷時(shí)長(zhǎng)及對(duì)應(yīng)的種集可以幫助商家以最小的成本獲得最大的利潤(rùn)。

現(xiàn)有如下場(chǎng)景：京東商城的一家商店要推廣一個(gè)新的商品，現(xiàn)要在整個(gè)社會(huì)網(wǎng)中進(jìn)行促銷。這個(gè)商家每天都有一定的促銷成本，每件商品都有一定的利潤(rùn)。由于受影響而購(gòu)買該商品的用戶總量會(huì)隨著時(shí)間的推移而不再呈上升趨勢(shì)，所以這家商店期望可以選擇具有較大影響力的用戶和最佳的促銷時(shí)間段來(lái)獲得更大的利潤(rùn)。上文的場(chǎng)景可以形式化地表示為時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題：給定每個(gè)時(shí)間單位的促銷成本cost，每件商品利潤(rùn)price，用戶的歷史動(dòng)作記錄L，要選擇時(shí)間長(zhǎng)度T和種集S，使得S在時(shí)間T內(nèi)的影響可以使商家獲取最大的利潤(rùn)。顯然，選擇最佳的促銷時(shí)間長(zhǎng)度有重要的應(yīng)用價(jià)值。本文主要貢獻(xiàn)如下：

（1）利用用戶的歷史動(dòng)作記錄，設(shè)計(jì)了基于時(shí)間長(zhǎng)度的影響力分配模型IVA-T（influence value allocation-T），在該模型基礎(chǔ)上第一次提出了時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題（time optimal profitmaximization，OTPM），并證明了該問(wèn)題是NP-hard問(wèn)題。

（2）提出了一個(gè)近似算法Profit-Max來(lái)解決OTPM問(wèn)題，同時(shí)證明了Profit-Max算法的近似比為1-1/e-β/e，其中β表示最優(yōu)解的成本與最優(yōu)解的純利潤(rùn)的比值，是一個(gè)極小的數(shù)。

（3）通過(guò)在多個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，得出以下結(jié)論：Profit-Max算法可以有效并高效地求解OTPM問(wèn)題。另外，發(fā)現(xiàn)給定不同的時(shí)間長(zhǎng)度，最終得到的種集是不一樣的。

本文組織結(jié)構(gòu)如下：第2章介紹了相關(guān)工作；第3章給出了影響力分配模型及OTPM問(wèn)題定義；第4章提出了基于動(dòng)作日志的時(shí)間最優(yōu)利潤(rùn)最大化算法Profit-Max；第5章給出了實(shí)驗(yàn)結(jié)果及分析；第6章對(duì)本文工作進(jìn)行了總結(jié)。

2 相關(guān)工作

2003年，Kempe等人[2]第一次提出了社會(huì)網(wǎng)中的影響最大化問(wèn)題，并利用貪心算法來(lái)解決該問(wèn)題。每次迭代過(guò)程中選擇一個(gè)影響范圍增益最大的節(jié)點(diǎn)加入到種集，迭代循環(huán)到種集中節(jié)點(diǎn)數(shù)目為k。算法在選擇種子節(jié)點(diǎn)時(shí)，每次迭代都需要進(jìn)行大量次數(shù)的蒙特卡羅模擬使得求解的影響范圍更為精確，然而效率會(huì)變低。2007年，Leskovec等人[7]提出了CELF（cost-effective lazy forward）優(yōu)化算法改進(jìn)貪心算法的效率，比原始貪心算法快700倍。Zhou等人[9]為影響范圍函數(shù)設(shè)計(jì)了一個(gè)上界，該上界可以減少在貪心算法中調(diào)用蒙特卡羅模擬的次數(shù)，尤其是在初始化的第一次迭代中，基于該上界，并結(jié)合CELF優(yōu)化，設(shè)計(jì)了UBLF（upper bound based lazy forward）算法。Liu等人[10]也提出了一個(gè)線性的上界方法來(lái)計(jì)算影響力及影響最大化，設(shè)計(jì)了一個(gè)定量指標(biāo)Group-Page-Rank，以便快速地在線性方法上估計(jì)影響力的上界，進(jìn)一步提高影響最大化算法的效率。很多研究也將競(jìng)爭(zhēng)因素結(jié)合到影響最大化研究中。Chen等人[11]擴(kuò)展了IC傳播模型，提出了帶有時(shí)間限制的影響最大化問(wèn)題。2012年，Lu等人[12]提出了LT-V模型，并在該模型上定義了利潤(rùn)最大化問(wèn)題。此后，Bhagat等人[13]提出LT-C傳播模型，并在該模型上研究并解決了最大化產(chǎn)品購(gòu)買問(wèn)題。Lin等人[14]考慮了現(xiàn)在社會(huì)網(wǎng)中很多相似商品之間的競(jìng)爭(zhēng)關(guān)系，提出了基于學(xué)習(xí)的框架去解決多輪的競(jìng)爭(zhēng)影響最大化，每個(gè)競(jìng)爭(zhēng)者在選擇種集的時(shí)候不僅考慮了網(wǎng)絡(luò)信息，也考慮了對(duì)手的選擇，分別提出了已知對(duì)手策略和未知對(duì)手策略的解決辦法。

然而，上述模型都有如下弊端：邊上的概率值為預(yù)先設(shè)定，不能準(zhǔn)確地模擬真實(shí)傳播。為解決該問(wèn)題，Goyal等人[8]提出了基于動(dòng)作日志來(lái)求解影響最大化問(wèn)題。他們定義了基于數(shù)據(jù)傳播的CD模型，利用用戶的歷史行動(dòng)日志來(lái)學(xué)習(xí)用戶之間的影響概率。在真實(shí)數(shù)據(jù)的傳播過(guò)程中有一個(gè)新的發(fā)現(xiàn)：給定不同的傳播時(shí)間，最終計(jì)算出的種集是不同的。而且，在現(xiàn)實(shí)營(yíng)銷環(huán)境中，成本會(huì)隨著時(shí)間的推移而增加。因此，在利用動(dòng)作日志精確選擇種集的基礎(chǔ)上，考慮不同的時(shí)間長(zhǎng)度可以使最終選擇的種集具有更大的影響范圍。

3 傳播模型及問(wèn)題定義

本章提出了一個(gè)考慮時(shí)間長(zhǎng)度的影響力分配模型IVA-T，并給出了時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題（OTPM）的定義。

3.1 IVA-T傳播模型

給定有向圖G=(V,E)，時(shí)間長(zhǎng)度T，動(dòng)作日志L。動(dòng)作日志L中記錄格式為(user,action,time)，表示用戶user在時(shí)間time執(zhí)行了動(dòng)作action。令V表示user的全集，A表示action的全集。對(duì)于任意u∈V,a∈A，令t(u,a)代表用戶u執(zhí)行動(dòng)作a的時(shí)間?，F(xiàn)假設(shè)每一個(gè)用戶最多只執(zhí)行某個(gè)動(dòng)作一次。t(u,a)＜t(v,a)代表用戶u在用戶v之前執(zhí)行過(guò)動(dòng)作a；t(u,a)=+∞代表用戶u未執(zhí)行過(guò)動(dòng)作a。如果對(duì)于節(jié)點(diǎn)v，滿足0≤t(v,a)-t(u,a)≤T并且(u,v)∈E，則表示在時(shí)間T內(nèi)，動(dòng)作a從節(jié)點(diǎn)u傳播到節(jié)點(diǎn)v。

對(duì)于動(dòng)作a，定義在T時(shí)間內(nèi)，直接影響v的節(jié)點(diǎn)集合為Nin(v,a,T)={u|{u,v)∈E,0≤t(v,a)-t(u,a)≤T}。節(jié)點(diǎn)v在執(zhí)行動(dòng)作a時(shí)，v要對(duì)?u∈Nin(v,a,T)分配直接影響力，記作αv,u(a,T)，且滿足。對(duì)于直接影響力αv,u(a,T)，有多種分配方式。為便于理解，先定義αv,u(a,T)=1/Nin(v,a,T)。節(jié)點(diǎn)v迭代地為節(jié)點(diǎn)u的父節(jié)點(diǎn)w分配影響力，進(jìn)一步判斷v與w的執(zhí)行時(shí)間間隔是否滿足0≤t(v,a)-t(w,a)≤T，若滿足該條件，則需要給w分配影響力，否則不需要。給定動(dòng)作a，節(jié)點(diǎn)v在時(shí)間T內(nèi)給它的父節(jié)點(diǎn)w分配的影響力形式化地表示為，并 且Γu,u(a,T)=1。給定集合S?V，對(duì)于動(dòng)作a，可以類似定義節(jié)點(diǎn)v在時(shí)間T內(nèi)對(duì)S分配的影響力，如果u∈S，那么Γu,S(a,T)=1。最后，對(duì)動(dòng)作日志中的每個(gè)動(dòng)作聚集，得出最終影響力。節(jié)點(diǎn)v在時(shí)間T內(nèi)給它的父節(jié)點(diǎn)w分配的影響力定義為，其中|Pv|表示節(jié)點(diǎn)v執(zhí)行的動(dòng)作個(gè)數(shù)。在時(shí)間T內(nèi)，對(duì)于任意集合S?V，節(jié)點(diǎn)v對(duì)S分配的影響力表示為。以上描述的具有時(shí)間限制的傳播模型定義為IVA-T。在時(shí)間T內(nèi)，給定IVA-T模型，種集S的影響范圍。

舉例來(lái)解釋提出的模型。給定一個(gè)有向圖G=(V,E)，其中V={1,2,3,4,5,6,7}，E={(1,2),(2,3),(2,4),(5,6),(5,7)}。動(dòng)作日志L={(1,a,0),(5,a,0),(2,a,1),(6,a,1),(7,a,1),(3,a,3),(4,a,3)}。首先，對(duì)動(dòng)作日志(u,a,t)做預(yù)處理：先按action排序，再按照time排序。利用IVA-T模型，先計(jì)算T=1時(shí)，圖G中節(jié)點(diǎn)的影響力分配，找到影響力最大的節(jié)點(diǎn)。當(dāng)T=1時(shí)，對(duì)于動(dòng)作日志記錄(1,a,0)，節(jié)點(diǎn)1先于其他節(jié)點(diǎn)執(zhí)行動(dòng)作a，因此節(jié)點(diǎn)1不給其他節(jié)點(diǎn)分配影響力；對(duì)于日志記錄(2,a,1)，掃描指向節(jié)點(diǎn)2的鄰接鏈表，因?yàn)?≤t(2,a)-t(1,a)≤1,(1,2)∈E，所以節(jié)點(diǎn)2給節(jié)點(diǎn)1分配的影響力為1/Nin(2,a,1)=1；同理，對(duì)于動(dòng)作日志記錄(6,a,1)和(7,a,1)，得出節(jié)點(diǎn)6給節(jié)點(diǎn)5分配的影響力為1/Nin(6,a,1)=1，節(jié)點(diǎn)7給節(jié)點(diǎn)5分配的影響力也為1/Nin(7,a,1)=1；對(duì)于動(dòng)作日志記錄(3,a,3)，掃描指向節(jié)點(diǎn)3的鄰接鏈表，因?yàn)閠(3,a)-t(2,a)＞1，所以節(jié)點(diǎn)3不對(duì)節(jié)點(diǎn)2分配影響力。同理節(jié)點(diǎn)4也不對(duì)節(jié)點(diǎn)2分配影響力。當(dāng)T=2時(shí)，采用上述方法進(jìn)行影響力分配。當(dāng)T=1，T=2時(shí)影響力分配的結(jié)果如表2所示。

Table 2 Influence value of different timespan表2 在不同時(shí)間長(zhǎng)度條件下分配的影響力

通過(guò)上述例子，發(fā)現(xiàn)在不同時(shí)間長(zhǎng)度條件下，影響力最大的節(jié)點(diǎn)是不同的。例如，T=1時(shí)，節(jié)點(diǎn)5影響力最大；T=2時(shí)，節(jié)點(diǎn)1影響力最大。因此，在不同的時(shí)間長(zhǎng)度條件下，應(yīng)當(dāng)選擇不同的種集。

3.2 問(wèn)題定義

時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題（OTPM）：給定有向圖G=(V,E)，動(dòng)作日志L(user,action,time)，每件商品的利潤(rùn)price，單位時(shí)間的成本cost，正整數(shù)k，最佳促銷時(shí)間長(zhǎng)度T，種集S，其中|S|=k，使得在IVA-T模型下，商品的純利潤(rùn)price×δIVA-T(S,T)-cost×T達(dá)到最大，其中price×δIVA-T(S,T)表示在時(shí)間T內(nèi)促銷商品獲得的利潤(rùn)，cost×T表示在時(shí)間T內(nèi)促銷的成本。

定理1最優(yōu)的利潤(rùn)最大化問(wèn)題OTPM是NP-hard問(wèn)題。

證明 如果把時(shí)間長(zhǎng)度T設(shè)置為社會(huì)網(wǎng)中用戶執(zhí)行動(dòng)作的最大時(shí)間T=max{t(u,a)|u∈V}，那么IVA-T傳播模型等價(jià)于CD傳播模型[8]，使price=1，cost=0，則時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題OTPM可以轉(zhuǎn)化為影響最大化問(wèn)題。Goyal已經(jīng)證明影響最大化問(wèn)題在CD傳播模型下是NP-hard問(wèn)題。由于時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題的特殊情況是NP-hard，那么該問(wèn)題也是NP-hard。 □

4 基于動(dòng)作日志的利潤(rùn)最大化算法

首先將時(shí)間均勻分為M個(gè)單位長(zhǎng)度，對(duì)于每個(gè)遞增的時(shí)間長(zhǎng)度，首先利用算法Initialization影響力分配鏈表inf_link進(jìn)行初始化，再利用算法Greedy-CELF選擇種集S_temp，并計(jì)算當(dāng)前時(shí)間長(zhǎng)度所選擇的種集得到的利潤(rùn)。如果當(dāng)前利潤(rùn)大于最大利潤(rùn)，則依次替換當(dāng)前最大利潤(rùn)、種集S和最佳時(shí)間長(zhǎng)度T。Profit-Max算法的偽代碼如算法1所示。

算法1 Profit-Max算法

4.1 掃描動(dòng)作日志，初始化影響力分配鏈表

算法Initialization按序掃描動(dòng)作日志，針對(duì)動(dòng)作a∈A，對(duì)每個(gè)節(jié)點(diǎn)u∈V的影響力分配鏈表inf_link[a][u]進(jìn)行初始化。inf_link[a][u]中存儲(chǔ)節(jié)點(diǎn)u在動(dòng)作a上為其他節(jié)點(diǎn)分配的影響力值。

首先，對(duì)動(dòng)作日志L(user,action,time)進(jìn)行預(yù)處理：先按動(dòng)作action進(jìn)行排序，然后按時(shí)間time排序。令active為存儲(chǔ)被目前動(dòng)作激活的節(jié)點(diǎn)集合，P[u]代表節(jié)點(diǎn)u執(zhí)行動(dòng)作的個(gè)數(shù)，father[u]為節(jié)點(diǎn)u在目前動(dòng)作上可激活的父節(jié)點(diǎn)集合，time[u]為節(jié)點(diǎn)u執(zhí)行目前動(dòng)作的時(shí)間。由給定有向圖G=(V,E)可構(gòu)造指向每個(gè)節(jié)點(diǎn)u∈V的鄰接表in_edge[u]。順序掃描動(dòng)作日志(u,a,t)，鄰接表in_edge[u]中的每個(gè)節(jié)點(diǎn)w，若w在active集合中，并且u執(zhí)行目前動(dòng)作的時(shí)間與w執(zhí)行目前動(dòng)作的時(shí)間間隔小于等于時(shí)間長(zhǎng)度T，則把w加入節(jié)點(diǎn)u的影響力分配鏈表中，再對(duì)w進(jìn)行影響力分配。然后迭代地對(duì)節(jié)點(diǎn)w的父節(jié)點(diǎn)進(jìn)行影響力分配。算法2為Initialization算法的偽代碼。

算法2 Initialization算法

4.2 利用CELF優(yōu)化選取節(jié)點(diǎn)

在選擇種集時(shí)使用了CELF算法。CELF算法利用函數(shù)的子模性。如果對(duì)?S?T，有φ(S∪{u})-φ(S)≥φ(T?{u})-φ(T)，則稱函數(shù)φ(?)具有子模性。易證，本文提出的影響傳播函數(shù)δIVA-T(S,T)在時(shí)間T固定時(shí)具有子模性，因此本文采用CELF算法進(jìn)行種集選擇。

首先，Greedy-CELF算法利用Margin-compute計(jì)算節(jié)點(diǎn)u∈V的影響增益u.margin，更新當(dāng)前迭代次數(shù)，再將u存儲(chǔ)到優(yōu)先隊(duì)列queue。優(yōu)先隊(duì)列queue將所有節(jié)點(diǎn)按margin的值從大到小排序。Greedy-CELF算法的偽代碼如算法3所示。

算法3 Greedy-CELF算法

4.3 對(duì)所有動(dòng)作聚集，計(jì)算節(jié)點(diǎn)影響范圍增益

Margin-compute計(jì)算節(jié)點(diǎn)x加入種集S后影響范圍增益margin。gain[a]中存儲(chǔ)節(jié)點(diǎn)x每個(gè)動(dòng)作上的影響力聚集值。SA[a][x]表示節(jié)點(diǎn)x針對(duì)動(dòng)作a對(duì)當(dāng)前種集S的影響力。那么針對(duì)動(dòng)作a將x加入種集S，增益為gain[a]×(1-SA[a][x])。則基于所有動(dòng)作，margin為增益gain[a]×(1-SA[a][x])的累加和。Margin-compute的偽代碼如算法4所示。

算法4 Margin-compute算法

4.4 更新影響力分配鏈表

將節(jié)點(diǎn)x加入到種集S后，算法Value-update更新了inf_link以及其他節(jié)點(diǎn)給當(dāng)前種集S分配的影響力SA。算法Value-update的偽代碼如算法5所示。

算法5 Value-update算法

4.5 算法的時(shí)間復(fù)雜性分析

Profit-Max算法的時(shí)間復(fù)雜度為O(kηM|V||L|)。其中k為S的大?。沪鞘撬泄?jié)點(diǎn)的父節(jié)點(diǎn)數(shù)的最大值，即η=max{|inf_link[a][u]|,a∈A,u∈V}；|inf_link[a][u]|表示鏈表inf_link[a][u]的長(zhǎng)度；M是時(shí)間段數(shù)；|V|是圖中節(jié)點(diǎn)數(shù)目；|L|為動(dòng)作日志記錄數(shù)。

定理2 Profit-Max算法的近似比為1-1/e-β/e，其中β表示最優(yōu)解的成本比上最優(yōu)解的純利潤(rùn)，即β=(cost×T0)/(price×δIVA-T(S0,T0)-cost×T0)。其中(S0,T0)是問(wèn)題OTPM的最優(yōu)解。

證明 本文提出在選擇最終種集S時(shí)，固定了時(shí)間長(zhǎng)度T。當(dāng)T為常數(shù)時(shí)，利用文獻(xiàn)[8]的定理2易證δIVA-T(S,T)具有子模性、單調(diào)性。因此當(dāng)T為常數(shù)時(shí)，利用貪心算法可以找到一個(gè)與最優(yōu)解的比值至少為1-1/e的近似解。為了便于閱讀，令α=1-1/e。設(shè)T=T0，S=S0是OTPM問(wèn)題的最優(yōu)解，Profit-Max算法在T=T0時(shí)找到的種集為S′，Profit-Max算法在求解OTPM問(wèn)題時(shí)返回的解為T=T1，S=S1。那么有α×δIVA-T(S0,T0)≤δIVA-T(S′,T0)。因此price×δIVA-T(S0,T0)-cost×T0≤1/α×price×δIVA-T(S′,T0)-cost×T0=1/α×(price×δIVA-T(S′,T0)-cost×T0)+(1/α-1)× cost×T0≤ 1/α×(price×δIVA-T(S1,T1)-cost×T1)+(1/α-1)×cost×T0，從 而 1≤1/α×(price×δIVA-T(S1,T1)-cost×T1)/(price×δIVA-T(S0,T0)-cost×T0)+(1/α-1)×β。整理后，(price×δIVA-T(S1,T1)-cost×T1)/(price×δIVA-T(S0,T0)-cost×T0)≥(1-(1/α-1)×β)×α=α-(1-α)×β=1-1/e-β/e。 □

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

在兩個(gè)真實(shí)數(shù)據(jù)集上測(cè)試和評(píng)估了本文提出的算法，并從多個(gè)角度驗(yàn)證本文算法的有效性和高效性。

5.1 實(shí)驗(yàn)環(huán)境描述

本文使用的兩個(gè)數(shù)據(jù)集都包含一個(gè)社會(huì)網(wǎng)G=(V,E)和一組動(dòng)作日志L(user,action,time)。數(shù)據(jù)集分別是Last.fm[15]和Digg[15]。其中，Last.fm是社交音樂(lè)平臺(tái)，用戶可以評(píng)論音樂(lè)。動(dòng)作日志中的信息代表用戶u在時(shí)間t評(píng)論音樂(lè)a。從中提取了2 100個(gè)節(jié)點(diǎn)，25 435條邊及相應(yīng)的動(dòng)作日志。該動(dòng)作日志包含1 000個(gè)動(dòng)作，21 646條記錄。Digg是社交新聞網(wǎng)站，用戶可以評(píng)論網(wǎng)站上的文章。動(dòng)作日志中的信息代表用戶u在時(shí)間t評(píng)論文章a。從中提取了5 000個(gè)節(jié)點(diǎn)，395 513條邊及相應(yīng)的動(dòng)作日志。該動(dòng)作日志包含500個(gè)動(dòng)作，77 461條記錄。

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

5.2 種集大小和時(shí)間長(zhǎng)度對(duì)利潤(rùn)的影響

本組實(shí)驗(yàn)考察種集大小k和時(shí)間長(zhǎng)度T對(duì)影響范圍Spread和利潤(rùn)Profit的影響。從圖1和圖2可以看出，當(dāng)時(shí)間長(zhǎng)度T固定時(shí)，隨著種集大小k的增加，影響范圍Spread也在不斷增加。當(dāng)k固定時(shí)，隨著時(shí)間長(zhǎng)度T的增加，影響范圍Spread也在增加。

從圖3和圖4可以看出，固定k時(shí)，隨著時(shí)間長(zhǎng)度T的增加，利潤(rùn)不斷增加，但當(dāng)時(shí)間達(dá)到某個(gè)點(diǎn)時(shí)，利潤(rùn)不再增加。在Last數(shù)據(jù)集上T=6時(shí)，利潤(rùn)Profit達(dá)到最大。而在Digg數(shù)據(jù)集上，利潤(rùn)Profit在T=3時(shí)達(dá)到最大。由此可見選擇最佳促銷時(shí)間在營(yíng)銷過(guò)程中的重要性。

Fig.1 Spread vs timespan T in Last dataset圖1 在Last數(shù)據(jù)集上影響范圍vs時(shí)間長(zhǎng)度T

Fig.3 Profit vs timespan T in Last dataset(price=20,cost=100)圖3 在Last數(shù)據(jù)集上price=20,cost=100時(shí)產(chǎn)品利潤(rùn)vs時(shí)間長(zhǎng)度T

5.3 產(chǎn)品價(jià)格和成本對(duì)利潤(rùn)的影響

本組實(shí)驗(yàn)考察產(chǎn)品價(jià)格price和成本cost對(duì)利潤(rùn)和最佳促銷時(shí)間的影響。由圖5可以看出，最佳促銷時(shí)間隨著price的增加也在不斷增加。當(dāng)price=10時(shí)，T=3為最佳促銷時(shí)間。而當(dāng)price=40時(shí)，T=6為最佳。由圖6可以看出，最佳促銷時(shí)間不斷減小。當(dāng)cost=100時(shí)，T=6為最佳促銷時(shí)間。而當(dāng)cost=400時(shí)，T=4為最佳。由此可見，在不同的產(chǎn)品價(jià)格price和成本cost條件下，選擇不同的促銷時(shí)間長(zhǎng)度是重要的。

在Digg數(shù)據(jù)集上也做了相同的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果得出的規(guī)律與在Last上的結(jié)果相似。

Fig.2 Spread vs timespan T in Digg dataset圖2 在Digg數(shù)據(jù)集上影響范圍vs時(shí)間長(zhǎng)度T

Fig.4 Profit vs timespan T in Digg dataset(price=20,cost=400)圖4 在Digg數(shù)據(jù)集上price=20,cost=400時(shí)產(chǎn)品利潤(rùn)vs時(shí)間長(zhǎng)度T

5.4 比較不同算法選擇的種集

本組實(shí)驗(yàn)考察本文算法與其他算法在選擇的種集的真實(shí)影響范圍以及運(yùn)行時(shí)間上的差異。主要與下面方法進(jìn)行比較。（1）Degree-Max：選擇節(jié)點(diǎn)度數(shù)最大的k個(gè)節(jié)點(diǎn)作為種集；（2）Greedy-Max：使用貪心算法選取種集；（3）CD-Max：在CD模型上使用貪心算法選取種集；（4）LAIC-Max：在LAIC模型上根據(jù)時(shí)間長(zhǎng)度選取種集；（5）IC-M-Max：在IC-M模型上根據(jù)時(shí)間長(zhǎng)度選取種集。

Fig.5 Profit vs timespan T in Last dataset(cost=300,k=10)圖5 在Last數(shù)據(jù)集上cost=300,k=10時(shí)產(chǎn)品利潤(rùn)vs時(shí)間長(zhǎng)度T

Fig.6 Profit vs timespan T in Last dataset(price=20,k=10)圖6 在Last數(shù)據(jù)集上price=20,k=10時(shí)產(chǎn)品利潤(rùn)vs時(shí)間長(zhǎng)度T

在這組實(shí)驗(yàn)中，分別利用上述6種算法選擇k=10的種集，并計(jì)算選定種集在不同時(shí)間長(zhǎng)度下影響范圍Spread。從圖7和圖8中可以看出，Degree-Max的結(jié)果最差，因?yàn)镈egree-Max只是選擇全局具有最大度數(shù)的節(jié)點(diǎn)。Greedy-Max在計(jì)算影響范圍時(shí)采用了蒙特卡羅模擬估計(jì)，使得該算法結(jié)果略優(yōu)于Degree-Max。LAIC-Max與IC-M-Max既考慮了圖的拓?fù)浣Y(jié)構(gòu)，也考慮了時(shí)間因素，但是在求解影響范圍時(shí)沒(méi)有利用真實(shí)數(shù)據(jù)，因此計(jì)算出的影響范圍不準(zhǔn)確。CD-Max雖然利用了真實(shí)數(shù)據(jù)，但該算法在每個(gè)時(shí)間長(zhǎng)度所選擇的種集S都是相同的。Profit-Max則在真實(shí)數(shù)據(jù)上計(jì)算影響范圍，根據(jù)不同的時(shí)間長(zhǎng)度T，選擇最優(yōu)種集S，因此得到的影響范圍優(yōu)于其他算法。

從圖9中可以看出以上6種算法的運(yùn)行時(shí)間。Degree-Max運(yùn)行時(shí)間較快的原因是該算法只是簡(jiǎn)單地選擇全局度數(shù)最大的k個(gè)節(jié)點(diǎn)作為種集。LAICMax與IC-M-Max的運(yùn)行時(shí)間隨著時(shí)間長(zhǎng)度的增加呈線性增加的趨勢(shì)。Profit-Max運(yùn)行時(shí)間最快，是因?yàn)镻rofit-Max直接利用真實(shí)數(shù)據(jù)計(jì)算影響范圍。由于Greedy-Max方法需要大量次數(shù)蒙特卡羅模擬，使得運(yùn)行時(shí)間太長(zhǎng)，圖中沒(méi)有顯示。

Fig.7 Spread vs timespan T in Last dataset(k=10)圖7 在Last數(shù)據(jù)集上k=10時(shí)影響范圍vs時(shí)間長(zhǎng)度T

Fig.8 Spread vs timespan T in Digg1000 dataset(k=10)圖8 在Digg1000數(shù)據(jù)集上k=10時(shí)影響范圍vs時(shí)間長(zhǎng)度T

選擇了7個(gè)不同的時(shí)間長(zhǎng)度，分別計(jì)算出在這些不同時(shí)間長(zhǎng)度下的種集。從表3中可以得出結(jié)論，在不同的促銷時(shí)間長(zhǎng)度下，應(yīng)選擇不同的種集。

Fig.9 Running time vs timespan T in Digg1000 dataset(k=10)圖9 在Digg1000數(shù)據(jù)集上k=10時(shí)運(yùn)行時(shí)間vs時(shí)間長(zhǎng)度T

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

Table 3 Different time vs seed set length in Last dataset with k=10表3 在Last數(shù)據(jù)集上k=10時(shí)時(shí)間長(zhǎng)度vs種集

本文提出了基于時(shí)間長(zhǎng)度的影響力分配模型IVA-T，在其基礎(chǔ)上提出了時(shí)間最優(yōu)的利潤(rùn)最大化問(wèn)題（OTPM），并證明了該問(wèn)題是NP-hard問(wèn)題。為解決該問(wèn)題，提出了一個(gè)高效的近似算法Profit-Max，并證明了Profit-Max的近似比。多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了Profit-Max算法的有效性和高效率。

[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.NewYork:ACM,2001:57-66.

[2]Kempe D,Kleinberg J M,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,Aug 24-27,2003.New York:ACM,2003:137-146.

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

[4]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 International Conference on Knowledge Discovery and Data Mining,Washington,Jul 25-28,2010.New York:ACM,2010:1029-1038.

[5]Li Yuchen,Zhang Dongxiang,Tan K L.Real time targeted influence maximization for online advertisements[J].Proceedings of the VLDB Endowment,2015,8(10):1070-1081.

[6]Horel T,Singer Y.Scalable methods for adaptively seeding a social network[C]//Proceedings of the 24th International Conference on World Wide Web Companion,Florence,Italy,May 18-22,2015.New York:ACM,2015:623-624.

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

[8]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.

[9]Zhou Chuan,Zhang Peng,Guo Jing,et al.An upper bound based greedy algorithm for mining top-kinfluential nodes in social networks[C]//Proceedings of the 23rd International World Wide Web Conference,Seoul,Apr 7-11,2014.New York:ACM,2014:421-422.

[10]Liu Qi,Xiang Biao,Chen Enhong,et al.Influence maximization over large-scale social networks:a bounded linear approach[C]//Proceedings of the 23rd International Conference on Information and Knowledge Management,Shanghai,Nov 3-7,2014.New York:ACM,2014:171-180.

[11]Chen Wei,Lu Wei,Zhang Ning.Time-critical influence maximization in social networks with time-delayed diffusion process[C]//Proceedings of the 26th Conference on Artificial Intelligence,Toronto,Canada,Jul 22-26,2012.Menlo Park,USA:AAAI,2012:592-598.

[12]Lu Wei,Lakshmanan L V S.Profit maximization over social networks[C]//Proceedings of the 12th International Conference on Data Mining,Brussels,Dec 10-13,2012.Washington:IEEE Computer Society,2012:479-488.

[13]Bhagat S,Goyal A,Lakshmanan L V S.Maximizing product adoption in social networks[C]//Proceedings of the 5th International Conference on Web Search and Data Mining,Seattle,USA,Feb 8-12,2012.NewYork:ACM,2012:603-612.

[14]Lin Suchen,Lin Shoude,Chen M S.A learning-based framework to handle multi-round multi-party influence maximization on social networks[C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Sydney,Australia,Aug 10-13,2015.New York:ACM,2015:695-704.

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

2016-08,Accepted 2017-02.

Research on Time Optimal Profit Maximization in Social Network*

LIU Yong+,XIE Shengnan,ZHANG Wei,ZHU Jinghua,WANG Nan
School of Computer Science and Technology,Heilongjiang University,Harbin 150080,China
+Corresponding author:E-mail:acliuyong@sina.com

Influence maximization is the problem of finding a small set of seed nodes in a social network.Existing works ignore the differences between influence spread maximization and profit maximization,and influence spread becomes stable when time passes by.This paper uses real action log and proposes a new propagation model with timespan which is called IVA-T(influence value allocation-T)propagation model,and firstly proposes time optimal profit maximization(OTPM)problem and proves that the problem is NP-hard.In order to solve the problem,this paper designs an effective approximation algorithm Profit-Max and analyzes the approximation ratio.The experimental results on several real datasets show that Profit-Max algorithm can solve OTPM problem effectively and efficiently.

social network;profit maximization;action log;timespan

10.3778/j.issn.1673-9418.1608044

*The Natural Science Foundation of Heilongjiang Province under Grant No.F201430(黑龍江省自然科學(xué)基金);the Innovation Talents Project of Science and Technology Bureau of Harbin under Grant No.2017RAQXJ094(哈爾濱科技創(chuàng)新人才研究專項(xiàng)資金項(xiàng)目);the Fundamental Research Funds of Universities in Heilongjiang Province,Special Fund of Heilongjiang University under Grant No.HDJCCX-201608(黑龍江省高?；究蒲袠I(yè)務(wù)費(fèi)黑龍江大學(xué)專項(xiàng)資金項(xiàng)目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-03-01,http://kns.cnki.net/kcms/detail/11.5602.TP.20170301.1040.002.html

LIU Yong,XIE Shengnan,ZHANG Wei,et al.Research on time optimal profit maximization in social network.Journal of Frontiers of Computer Science and Technology,2017,11(11)：1723-1732.

A

TP311

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ù)庫(kù)等。

XIE Shengnan was born in 1991.She received the M.S.degree from School of Computer Science and Technology,Heilongjiang University in 2015.Her research interest is data mining.

謝勝男（1991—），女，黑龍江黑河人，黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。

ZHANG Wei was born in 1989.She received the M.S.degree from School of Computer Science and Technology,Heilongjiang University in 2015.Her research interest is data mining.

張?。?989—），女，黑龍江人，2015年于黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院獲得碩士學(xué)位，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。

ZHU Jinghua was born in 1976.She received the Ph.D.degree in computer science from Harbin Institute of Technology in 2009.Now she is an associate professor and M.S.supervisor at Heilongjiang University.Her research interests include data mining and database,etc.

朱敬華（1976—），女，黑龍江齊齊哈爾人，2009年于哈爾濱工業(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ù)庫(kù)等。

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ò)等。