鄧曉衡 曹德娟 潘 琰 沈海瀾 陳志剛

1(中南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410083)2 (中南大學(xué)軟件學(xué)院 長沙 410075) (dxh@csu.edu.cn)

一種基于時(shí)延約束的社會(huì)網(wǎng)絡(luò)信用分布優(yōu)化模型

鄧曉衡1曹德娟1潘 琰1沈海瀾1陳志剛2

1(中南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410083)2(中南大學(xué)軟件學(xué)院 長沙 410075) (dxh@csu.edu.cn)

基于時(shí)延約束的影響力最大化問題(influence maximization with time-delay constraint, IMTC)定義為在時(shí)延約束條件下，選取網(wǎng)絡(luò)中一部分初始用戶，使得影響力傳播過程結(jié)束后網(wǎng)絡(luò)中被成功影響的用戶數(shù)量最多.現(xiàn)有研究工作主要依據(jù)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化影響力傳播模型，或改進(jìn)啟發(fā)式算法提高初始節(jié)點(diǎn)的選取質(zhì)量，影響力傳播過程中的時(shí)間延遲特性及時(shí)延約束條件往往被忽略.針對這點(diǎn)不足，基于時(shí)延約束的信用分布模型(credit distribution with time-delay constraint model, CDTC)綜合考慮見面概率和條件激活概率對信用分配進(jìn)行優(yōu)化定義，同時(shí)將相鄰節(jié)點(diǎn)之間不斷見面并激活對信用分配的阻礙作用映射到傳播增量路徑中，最后根據(jù)信用分布函數(shù)，使用基于時(shí)延約束的貪心算法GA-TC，遞歸選取邊際收益最大的節(jié)點(diǎn)組成初始節(jié)點(diǎn)集合.實(shí)驗(yàn)結(jié)果表明：在CDTC模型上使用GA-TC算法不僅能夠保證初始節(jié)點(diǎn)的選取質(zhì)量，而且具有更高的執(zhí)行效率及更好的行為執(zhí)行預(yù)測能力.

社會(huì)網(wǎng)絡(luò)；影響力最大化；時(shí)延約束；信用分布；貪心算法

互聯(lián)網(wǎng)的發(fā)展不僅為我們帶來了生活上的便捷，而且使我們交流與溝通方式產(chǎn)生了巨大的變化.隨著越來越多的人使用諸如移動(dòng)終端等更加便捷的數(shù)據(jù)交換設(shè)備，我們交友與分享智慧的途徑變得更加豐富多樣，社會(huì)結(jié)構(gòu)變得更加復(fù)雜，人與人之間的聯(lián)系也變得更加緊密.一般情況下，通過在線社會(huì)網(wǎng)絡(luò)中用戶之間的聯(lián)系，信息可以以極快的速度和極小的代價(jià)進(jìn)行傳播.正因?yàn)槿绱耍绊懥υ谏鐣?huì)網(wǎng)絡(luò)中的擴(kuò)散和傳播為病毒式營銷帶來了前所未有的機(jī)遇和挑戰(zhàn)，如何找到初始用戶群體使得信息最終的影響傳播范圍最大已成為熱點(diǎn)研究領(lǐng)域之一.

總體看來，在社會(huì)網(wǎng)絡(luò)中對影響力傳播進(jìn)行有效評估面臨3個(gè)主要問題[1-3]:1)如何評估節(jié)點(diǎn)影響力，或者通過何種方式表現(xiàn)影響力的大小;2)如何描述和建模影響力傳播過程，使得它能夠真實(shí)有效地反映影響力傳播情況;3)結(jié)合給定的影響力傳播模型，怎樣設(shè)計(jì)算法對初始節(jié)點(diǎn)進(jìn)行高效且準(zhǔn)確的選取.

在社會(huì)網(wǎng)絡(luò)中，用戶之間的影響力通過口碑效應(yīng)進(jìn)行傳播，商家首先找尋初始用戶，并利用病毒式營銷策略對網(wǎng)絡(luò)中的群體用戶進(jìn)行產(chǎn)品推廣以達(dá)到最優(yōu)化宣傳的目的，如何有效準(zhǔn)確地鑒別出初始用戶是影響力最大化問題(influence maximization, IM)的核心.Domingos 和 Richardson[4-5]首先提出使用優(yōu)化算法解決影響力最大化問題.Kempe等人[6]將問題公式化表示，并且將它作為離散優(yōu)化問題進(jìn)行解決.此外，他們還提出2個(gè)影響力傳播模型，即獨(dú)立級聯(lián)模型(independent cascade model, IC)和線性閾值模型(linear threshold model, LT)，并證明影響力最大化問題是NP難問題.更重要的是，在這2個(gè)模型上使用貪心算法能夠得到相比于最優(yōu)解(1-1e)更高的運(yùn)算結(jié)果準(zhǔn)確率.然而，IC和LT等模型也存在缺陷，它們需要使用大量的Monto-Carlo模擬來保證對傳播結(jié)果評估的精確性.該過程需要花費(fèi)大量的時(shí)間，從而使得模型并不普遍適用于解決大型網(wǎng)絡(luò)的影響力最大化問題.因此，如何尋找具有高效、普適和可擴(kuò)展性的算法成為亟待解決的問題[7].當(dāng)前例如LDAG[8]和PMIA[9-10]等啟發(fā)式算法雖然克服了運(yùn)算效率低下的問題，但相比于傳統(tǒng)貪心算法，啟發(fā)式算法往往以犧牲計(jì)算結(jié)果的精確性和穩(wěn)定性來獲取運(yùn)算效率的提高.除此之外，在現(xiàn)實(shí)場景中，經(jīng)營者會(huì)對影響力在網(wǎng)絡(luò)中傳播的過程設(shè)置一定的前提，或者對影響力的傳播結(jié)果限制一定的約束條件[11]，例如，社會(huì)網(wǎng)絡(luò)中的話題的關(guān)注與談?wù)摕岫葧?huì)隨著時(shí)間的推移呈現(xiàn)衰減的特性，在影響力傳播的同時(shí)，商家往往追求的是在一段時(shí)期或者一定傳播代價(jià)范圍內(nèi)影響力傳播覆蓋范圍的最大化.本文針對時(shí)延約束的影響力最大化問題進(jìn)行研究，已知節(jié)點(diǎn)之間的見面事件是它們發(fā)生影響作用的前提必要條件，并且1個(gè)節(jié)點(diǎn)在同一時(shí)刻只能和一個(gè)出鄰居節(jié)點(diǎn)發(fā)生碰面并嘗試激活.我們將見面概率與條件激活概率兩者綜合考慮，并將其優(yōu)化應(yīng)用在影響力的評估和傳播過程之中.

針對IM問題，其他一些學(xué)者也已經(jīng)提出了許多有意義的工作.文獻(xiàn)[12]提出一種基于用戶推薦的方式構(gòu)建用戶之間連接的算法，社交服務(wù)運(yùn)營商通過分時(shí)分步向申請者提供推薦名單，使目標(biāo)用戶接受申請者發(fā)起邀請的概率最大.文獻(xiàn)[13]提出了一種并行計(jì)算的方法，將網(wǎng)絡(luò)劃分為不重合的子圖，并從節(jié)點(diǎn)的影響力和認(rèn)知度2方面對節(jié)點(diǎn)的影響概率進(jìn)行評價(jià).文獻(xiàn)[14]使用矩陣變換，針對節(jié)點(diǎn)之間影響力提出一種線性有界的計(jì)算方式，同時(shí)對影響力的傳播進(jìn)行建模和描述，并提出2種算法對初始節(jié)點(diǎn)進(jìn)行選取.

我們對信用分布模型(credit distribution, CD)進(jìn)行優(yōu)化[15]，提出一種基于時(shí)延約束的信用分布模型(credit distribution with time-delay constraint, CDTC)，基于真實(shí)用戶行為記錄，結(jié)合見面事件、激活事件以及時(shí)延約束條件，追蹤并得到不同行為在網(wǎng)絡(luò)中的傳播路徑，然后對路徑中的用戶節(jié)點(diǎn)逆向分配代表影響力大小的信用值，除此之外，我們根據(jù)見面概率和條件激活概率以及影響力隨時(shí)間衰減的特性對行為傳播路徑中相鄰用戶節(jié)點(diǎn)之間分配的直接信用進(jìn)行優(yōu)化定義.例如，在網(wǎng)絡(luò)中，節(jié)點(diǎn)u和節(jié)點(diǎn)v是相鄰的2個(gè)用戶節(jié)點(diǎn)，通過分析行為a的傳播路徑，已知節(jié)點(diǎn)v首先執(zhí)行了該行為，節(jié)點(diǎn)u在之后的某時(shí)刻也同樣執(zhí)行了行為a，說明在節(jié)點(diǎn)u執(zhí)行行為a的時(shí)刻，節(jié)點(diǎn)v嘗試與節(jié)點(diǎn)u碰面并激活成功，這時(shí)對節(jié)點(diǎn)v分配一個(gè)信用值，代表節(jié)點(diǎn)v影響節(jié)點(diǎn)u的影響力的大小.明顯地，如果節(jié)點(diǎn)v對節(jié)點(diǎn)u的影響力越大，則相應(yīng)分配給節(jié)點(diǎn)v的信用值也就越高，代表節(jié)點(diǎn)u對節(jié)點(diǎn)v的信任程度越大.在模型中，采用級聯(lián)的方式對信用度進(jìn)行分配，即如果節(jié)點(diǎn)v并不是行為a的初始執(zhí)行者，那么我們也會(huì)對行為a先于節(jié)點(diǎn)v的前一步執(zhí)行者分配一定的信用讓其影響節(jié)點(diǎn)u.這里還需要注意的是，對信用的分配需要限定在時(shí)延約束條件指定的范圍之內(nèi).最后，我們在CDTC模型上提出基于時(shí)延約束的貪心算法(greedy algorithm based on time-delay constraint, GA-TC)進(jìn)行近似求解，通過k次迭代，每次選取邊際收益最大的節(jié)點(diǎn)作為當(dāng)前輪次最具影響力的初始節(jié)點(diǎn)，算法運(yùn)行結(jié)束后得到初始節(jié)點(diǎn)集合S.我們工作的主要貢獻(xiàn)如下：

1) 對傳統(tǒng)信用分布模型CD進(jìn)行優(yōu)化并提出時(shí)延約束的信用分布模型CDTC，通過結(jié)合見面事件和激活事件對影響力在現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)中傳播的時(shí)間延遲特性進(jìn)行模擬，并結(jié)合影響力隨時(shí)間衰減的特性對相鄰節(jié)點(diǎn)之間的信用分配進(jìn)行優(yōu)化定義；

2) 提出一個(gè)基于時(shí)延約束的貪心算法GA-TC，并提出傳播增量路徑PIP，結(jié)合時(shí)延約束條件限定信用在網(wǎng)絡(luò)中的分配范圍；除此之外，我們證明了相比于最優(yōu)解，在CDTC模型中使用GA-TC算法對初始節(jié)點(diǎn)選取結(jié)果的準(zhǔn)確率下限為(1-1e)；

3) 使用真實(shí)的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集對模型和算法進(jìn)行模擬和測試，實(shí)驗(yàn)結(jié)果表明我們提出的方法能夠更加真實(shí)可靠地反映影響力的傳播，并且執(zhí)行效率明顯優(yōu)于傳統(tǒng)算法；在行為影響力的預(yù)測方面，CDTC模型上的預(yù)測準(zhǔn)確度相比于傳統(tǒng)信用分布模型有一定的優(yōu)化和提升.

1 時(shí)延約束的影響力最大化

在社會(huì)網(wǎng)絡(luò)中，用戶節(jié)點(diǎn)之間的信息交換受到時(shí)延約束條件的制約，而這種制約表現(xiàn)在時(shí)間和空間2方面.對于在線社會(huì)網(wǎng)絡(luò)，用戶之間信息交換的空間限制條件被極大地削弱，也正是由于信息交換平臺(tái)的這種廣泛而便捷的特性，使得用戶在在線社會(huì)網(wǎng)絡(luò)中交友和信息共享的范圍被極大地?cái)U(kuò)充，與此同時(shí)帶來的是用戶之間關(guān)系的脆弱性和易失性.雖然在線社會(huì)網(wǎng)絡(luò)極大地降低了信息在用戶之間傳遞的限制，擴(kuò)充了信息傳播的范圍，并提高了信息傳遞的時(shí)效性，但用戶對行為的執(zhí)行仍然存在時(shí)間延遲效應(yīng)，正如用戶行為日志中記錄的相同行為被不同執(zhí)行者執(zhí)行的時(shí)間間隔并不確定且存在差異一樣，行為在網(wǎng)絡(luò)中傳播同樣受到時(shí)間延遲的影響.例如社交網(wǎng)絡(luò)服務(wù)用戶只有看到消息提醒并在打開終端后才會(huì)看到好友發(fā)來的消息，也只有這個(gè)會(huì)面過程之后其他用戶對他的影響才會(huì)生效，這里我們引入1個(gè)隨機(jī)變量，定義為見面事件，并將后續(xù)的影響激活事件發(fā)生的概率看作是見面事件發(fā)生前提下的條件概率.對于影響力最大化問題IM，傳統(tǒng)的定義方式被描述為在網(wǎng)絡(luò)中找尋k個(gè)初始用戶節(jié)點(diǎn)，使得在影響力傳播過程結(jié)束后，網(wǎng)絡(luò)中被初始節(jié)點(diǎn)集合S激活的節(jié)點(diǎn)的個(gè)數(shù)最大(如算法1所示).

算法1. 傳統(tǒng)貪心算法.

輸入：用戶關(guān)系圖G=(V,E)，初始集合大小k，影響力傳播模型M；

輸出：初始節(jié)點(diǎn)集合S.

①S←?;

② fori=1→kdo

④S←S∪{x};

⑤ end for

⑥ returnS.

2 時(shí)延約束的信用分布模型

2.1 事件概率與模型性質(zhì)

一般情況下，社會(huì)網(wǎng)絡(luò)可以構(gòu)造為一個(gè)無向圖G=(V,E)，其中V表示網(wǎng)絡(luò)中的用戶集合，E代表不同個(gè)體之間的關(guān)系，S代表初始節(jié)點(diǎn)集合.在獨(dú)立級聯(lián)模型(IC)中，隨著影響力的傳播，網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)之間會(huì)產(chǎn)生一次性的激活嘗試，并且隨機(jī)選取范圍(0,1)之間的值作為節(jié)點(diǎn)之間的激活概率(在計(jì)算時(shí)一般根據(jù)節(jié)點(diǎn)的度值定義)，每個(gè)被激活的節(jié)點(diǎn)在當(dāng)前時(shí)刻變?yōu)榧せ顮顟B(tài)，同時(shí)會(huì)對其他所有處于未激活狀態(tài)的出鄰居節(jié)點(diǎn)產(chǎn)生一次性的激活嘗試，且次序隨機(jī)，嘗試成功的節(jié)點(diǎn)會(huì)在下一時(shí)刻執(zhí)行和父節(jié)點(diǎn)相同的行為步驟[16].其中影響者的影響力施加行為和被影響者的被激活行為我們認(rèn)定為是瞬時(shí)且不可逆的，除了行為的初始執(zhí)行者，被激活者總可以找到1個(gè)且唯一的影響成功施加者.在線性閾值模型(LT)中，鄰居節(jié)點(diǎn)施加的影響力可以累積，并通過網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的閾值來體現(xiàn)節(jié)點(diǎn)對于當(dāng)前信息的偏好程度.具體過程如下，假設(shè)當(dāng)前時(shí)刻為t，t>0，對于網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)u(u?St，St為時(shí)刻t網(wǎng)絡(luò)中已經(jīng)被激活的節(jié)點(diǎn)集合)，當(dāng)其所有處于激活狀態(tài)的入鄰居節(jié)點(diǎn)對其影響力之和大于自身閾值時(shí)，節(jié)點(diǎn)u在時(shí)刻t+1被激活且保持激活狀態(tài)，同時(shí)對所有未激活的出鄰居節(jié)點(diǎn)產(chǎn)生影響.此外，IC和LT模型都需要對節(jié)點(diǎn)影響力的影響范圍進(jìn)行定義，我們用參數(shù)X來表示影響力傳播路徑形成的影響力傳播范圍可行域.對于一個(gè)帶權(quán)有向圖G=(V,E,p)，給定的影響力傳播模型M，影響力傳播函數(shù)σM(S)可以寫為：

(1)

(2)

根據(jù)期望的定義重寫式(2)，得：

(3)

式(3)表明影響力傳播函數(shù)σM(S)等于每個(gè)節(jié)點(diǎn)u∈V被初始節(jié)點(diǎn)集合S激活的概率之和.在時(shí)延約束的信用分布模型CDTC中，我們用信用分布過程結(jié)束后積累在節(jié)點(diǎn)上的信用值來表示節(jié)點(diǎn)的影響力.同時(shí)，我們使用用戶行為日志中記錄的真實(shí)行為傳播路徑對Pr(path(S,u)=1)進(jìn)行直接評估，也就是說，我們針對不同的行為，統(tǒng)計(jì)并追蹤用戶在不同時(shí)刻執(zhí)行的情況，生成行為傳播路徑(action propagation path, APP).因?yàn)閭鞑サ臅r(shí)間延遲效應(yīng)，相鄰節(jié)點(diǎn)只有在見面的前提下才會(huì)產(chǎn)生影響作用，加入時(shí)延約束條件τ，信用的分布被限定在一定的范圍之內(nèi)，最終提高計(jì)算的效率.需要注意的是，因?yàn)樾袨閳?zhí)行的時(shí)序性，我們假定同一個(gè)用戶對相同的行為最多只能執(zhí)行1次，而且并不是在一個(gè)節(jié)點(diǎn)受到影響并被成功激活后就立即對相鄰的節(jié)點(diǎn)產(chǎn)生影響，而是在雙方發(fā)生見面并嘗試激活后，被影響的用戶節(jié)點(diǎn)才會(huì)執(zhí)行相同的行為，因此，對于同一個(gè)行為的傳播路徑構(gòu)成的圖是一個(gè)有向無環(huán)圖DAG.在影響力傳播范圍評估方面，我們在模型中使用信用分布函數(shù)σCDTC(S)代替影響力傳播函數(shù)σM(S)，即給定集合S，讓其影響網(wǎng)絡(luò)中其他節(jié)點(diǎn)的總信用.

假設(shè)圖中存在一條行為傳播路徑P={v1,v2,v3,…,vn}，其中相鄰節(jié)點(diǎn)之間的邊(vi,vj)∈P，則這條鏈路的激活概率為：

(4)

加入見面概率m后，相鄰節(jié)點(diǎn)vi和vj之間的激活概率為bvi,vj.設(shè)網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)vi和vj發(fā)生見面的事件用A表示，事件B表示節(jié)點(diǎn)vi已處于激活狀態(tài)且vi將vj成功激活，則有如下定理：

定理1. 網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)vi和vj之間發(fā)生見面的概率為m，見面條件下vi將vj成功激活的條件概率為α，則用戶節(jié)點(diǎn)vj被節(jié)點(diǎn)vi激活成功的概率bvi,vj=mα.

證畢.

證明. 由貝葉斯定理可得

因?yàn)闂l件概率Pr(A|B)=1，所以可以得到

綜合考慮這2種情況，假設(shè)見面概率m為未知參數(shù)，則似然函數(shù)可以表示為：

(5)

取對數(shù)似然函數(shù)，將其轉(zhuǎn)化為：

L(m;α)=lg(1-m)+lg(1-α)+
lgm-2lg(1-mα).

(6)

對式(6)取關(guān)于參數(shù)m的梯度，可以得到：

(7)

證畢.

在CD模型中，相鄰節(jié)點(diǎn)之間的影響力使用的是節(jié)點(diǎn)度值定義方式，即γvi,vj=1|Nout(vi)|.在本文中，根據(jù)推論1中見面概率和見面條件下的激活概率之間的優(yōu)化關(guān)系，并結(jié)合定理1，當(dāng)給定節(jié)點(diǎn)之間見面條件下的激活概率α?xí)r，可以得到網(wǎng)絡(luò)中任意節(jié)點(diǎn)vj被其鄰居節(jié)點(diǎn)vi激活成功的概率為bvi,vj=.一般情況下，相鄰節(jié)點(diǎn)之間條件激活概率α的值參照節(jié)點(diǎn)度值的倒數(shù)定義，即對于節(jié)點(diǎn)u，在見面條件下被鄰居節(jié)點(diǎn)激活的概率為，其中Nin(u)代表節(jié)點(diǎn)u的入鄰居節(jié)點(diǎn)集合.然而，當(dāng)節(jié)點(diǎn)的入度為0時(shí)，概率公式的分母為0，計(jì)算失效.因此，我們采用Laplace平滑方法對上述概率計(jì)算公式進(jìn)行改進(jìn)，在分母中加入平滑因子c，同時(shí)分子加1，則計(jì)算公式變形為.

類似于網(wǎng)絡(luò)中熱點(diǎn)話題的傳播會(huì)隨著人們關(guān)注度的降低而逐漸減弱，節(jié)點(diǎn)之間的影響力也會(huì)隨著時(shí)間的推移而遞減.我們使用函數(shù)sigmoid對影響力進(jìn)行平滑衰減變換，模擬影響力的衰減特性，并以此作為相鄰節(jié)點(diǎn)之間分配直接影響力的依據(jù)，即分配給vi對其影響出鄰居vj的直接信用定義為

(8)

其中tvi(a)和tvj(a)分別代表vi和vj執(zhí)行行為a的時(shí)刻.二者之間的時(shí)間跨度越大，表明分配給的信用越小，vi對vj的影響力也就越弱.

定理2. 社會(huì)網(wǎng)絡(luò)中相鄰用戶節(jié)點(diǎn)之間加入見面概率后，使用時(shí)延約束的信用分布模型CDTC，信用分布函數(shù)仍然具有單調(diào)性和子模特性.

證明. 在模型中，當(dāng)相鄰節(jié)點(diǎn)之間的見面概率m=1時(shí)，見面事件變?yōu)楸厝皇录藭r(shí)時(shí)延約束的信用分布模型CDTC等價(jià)于傳統(tǒng)信用分布模型CD.由于嘗試見面和激活而使行為傳播路徑增長為傳播增量路徑，設(shè)2個(gè)節(jié)點(diǎn)集合S和T，S?T，雖然時(shí)延約束條件τ將信用分布限制在一定范圍之內(nèi)，但是明顯有σCDTC(S)<σCDTC(T)，即信用分布函數(shù)σCDTC(S)為單調(diào)遞增函數(shù).

根據(jù)CDTC模型的定義可知，模型通過對信用的分配和積累來表現(xiàn)不同節(jié)點(diǎn)的影響力大小，所以對于信用分布函數(shù)子模特性的證明可以轉(zhuǎn)化為證明給予集合S讓其影響節(jié)點(diǎn)w的總信用TS,w是否具有相同的性質(zhì).以下使用數(shù)學(xué)歸納法證明，假設(shè)在CDTC模型中，TS,w具有子模特性，當(dāng)前信用分配的路徑長度表示為η，時(shí)延約束條件為τ.首先考慮當(dāng)η<τ并且η+1≤τ時(shí)，對于任意節(jié)點(diǎn)x，x?T，根據(jù)函數(shù)的子模特性可得TS+x,w(a;η)-TS,w(a;η)≥TT+x,w(a;η)-TT,w(a;η).當(dāng)路徑長度為η+1時(shí)，對于?u∈V,根據(jù)本文2.2節(jié)式(12)計(jì)算函數(shù)的差值

(9)

對式(9)化簡并根據(jù)題設(shè)中的子模特性可得

TS+x,w(a;η+1)-TS,w(a;η+1)≥

將不等式右邊展開,即可得到

TS+x,w(a;η+1)-TS,w(a;η+1)≥

TT+x,w(a;η+1)-TT,w(a;η+1)，

所以當(dāng)信用分配的路徑長度為η+1時(shí)定理2成立.當(dāng)η≥τ時(shí)，因?yàn)樾庞玫姆峙涫艿綍r(shí)延約束條件τ的限制，距離過長的節(jié)點(diǎn)不再被分配信用，即TS,w(a;η+1)=0，所以上式的左右兩邊相等.

證畢.

2.2 時(shí)延約束條件下的信用分布

社會(huì)網(wǎng)絡(luò)中，用戶對于行為的執(zhí)行記錄被保存在用戶行為日志中，而對于單個(gè)行為的整個(gè)執(zhí)行過程，則是按照時(shí)間順序形成連續(xù)的過程記錄，用戶行為日志中的每條記錄可以表示為(u,t,a)，即用戶u在時(shí)間t執(zhí)行了行為a.通過對用戶行為日志的遍歷，并結(jié)合用戶關(guān)系網(wǎng)絡(luò)，我們可以針對行為得到其被執(zhí)行的整個(gè)過程.同理，假設(shè)用戶u是用戶v的直接出鄰居，u∈Nout(v)，用戶v在時(shí)刻t1執(zhí)行了行為a，并且用戶v與用戶u成功見面并嘗試激活(在線社會(huì)網(wǎng)絡(luò)中可以理解為用戶u看到用戶v的消息)，如果用戶u在時(shí)刻t2(t2>t1)也執(zhí)行了相同的行為a，則認(rèn)定在網(wǎng)絡(luò)中節(jié)點(diǎn)v成功見面并激活了節(jié)點(diǎn)u.

(10)

結(jié)合用戶行為日志和用戶之間的關(guān)系網(wǎng)絡(luò)，針對行為得到傳播增量路徑PIP，之后我們在時(shí)延約束條件τ限制的范圍內(nèi)對路徑中的節(jié)點(diǎn)逆向分配信用，這樣節(jié)點(diǎn)之間的影響力就可以通過信用分布結(jié)束后網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)積累的信用值來表示，如果信用值較大，我們認(rèn)定網(wǎng)絡(luò)中其他節(jié)點(diǎn)對其的信任程度也較高，其反向?qū)λ麄兊挠绊懥σ簿洼^大.信用分布的具體過程描述如下：當(dāng)節(jié)點(diǎn)u執(zhí)行行為a，節(jié)點(diǎn)u或者是該行為的初始執(zhí)行者，或者是被動(dòng)轉(zhuǎn)發(fā)者.執(zhí)行的同時(shí)，節(jié)點(diǎn)u會(huì)對其他所有沒有執(zhí)行過該行為的鄰接節(jié)點(diǎn)產(chǎn)生影響.相似地，我們定義如果節(jié)點(diǎn)v執(zhí)行行為a之后，節(jié)點(diǎn)v的鄰接節(jié)點(diǎn)u也執(zhí)行了行為a，那么給節(jié)點(diǎn)v分配信用讓節(jié)點(diǎn)v影響節(jié)點(diǎn)u.對于PIP中任何相鄰的2個(gè)節(jié)點(diǎn)u和v，分配給節(jié)點(diǎn)v的信用的大小根據(jù)式(8)計(jì)算.另外，由于節(jié)點(diǎn)之間的信用分配采用類似于影響力級聯(lián)傳播過程的分配方式，所以不僅節(jié)點(diǎn)v會(huì)被分配信用，節(jié)點(diǎn)v之前對于行為a的前任執(zhí)行者也會(huì)被分配信用讓其影響節(jié)點(diǎn)u，信用的分配范圍被限定在τ的范圍之內(nèi).對于任意的2個(gè)節(jié)點(diǎn)v和u，給予節(jié)點(diǎn)v讓其影響節(jié)點(diǎn)u的總信用定義為

(11)

其中，w為節(jié)點(diǎn)u的入鄰居，γw,u(a)為給予w讓其影響節(jié)點(diǎn)u的信用大小.相似地，給予節(jié)點(diǎn)集合S讓其影響節(jié)點(diǎn)u的總信用可以定義為

(12)

值得注意的是CDTC模型并不像IC或者LT模型，它是通過學(xué)習(xí)歷史性的行為傳播記錄來追蹤行為傳播路徑，并依據(jù)行為傳播路徑逆向分配信用值.另外，我們在CDTC模型上選取初始節(jié)點(diǎn)并形成初始節(jié)點(diǎn)集合S.因?yàn)椴恍枰獔?zhí)行任何的Monte-Carlo模擬就可以得到影響力傳播結(jié)果的準(zhǔn)確評估，所以保證了在模型上對最大影響力初始節(jié)點(diǎn)選取工作的高效性和可靠性.

3 基于時(shí)延約束的貪心算法

3.1 節(jié)點(diǎn)邊際收益

σCDTC(S+v)-σCDTC(S)=

3.2 基于時(shí)延約束的貪心算法

現(xiàn)已證明在IC和LT模型中計(jì)算初始節(jié)點(diǎn)集合影響力傳播大小的期望值是NP難問題[6].當(dāng)前許多啟發(fā)式算法的提出正是為了近似有效地求解影響力最大化問題，然而在快速得出運(yùn)算結(jié)果的同時(shí)它們并不能保證結(jié)果的精確性和可靠性.相比之下，因?yàn)樵贑DTC模型中信用分布函數(shù)仍然具有單調(diào)性和子模特性，所以使用貪心算法計(jì)算初始節(jié)點(diǎn)可以保證得到精確率相比于最優(yōu)解下限為(1-1e)的選取結(jié)果.算法2給出了基于時(shí)延約束的貪心算法GA-TC的具體步驟.

算法2. 基于時(shí)延約束的貪心算法.

如算法2所示，我們首先對初始節(jié)點(diǎn)集合S和記錄節(jié)點(diǎn)邊際收益的隊(duì)列Q進(jìn)行初始化(行①).對網(wǎng)絡(luò)中的任意節(jié)點(diǎn)u，計(jì)算節(jié)點(diǎn)u與相鄰節(jié)點(diǎn)w在見面條件下的激活概率α，并根據(jù)見面概率m和α之間的優(yōu)化關(guān)系計(jì)算節(jié)點(diǎn)u成功激活w的概率bu,w(行②～⑤).然后通過遍歷訓(xùn)練集用戶行為日志，并根據(jù)用戶關(guān)系網(wǎng)絡(luò)、時(shí)延約束條件τ以及行④計(jì)算得到節(jié)點(diǎn)間的激活概率來構(gòu)建傳播增量路徑PIP.同時(shí)，依據(jù)路徑中用戶節(jié)點(diǎn)之間的激活概率對路徑中的相鄰節(jié)點(diǎn)分配直接信用(行⑥).之后根據(jù)信用分布函數(shù)的定義σCDTC(S)計(jì)算節(jié)點(diǎn)的邊際收益，排序后插入存儲(chǔ)隊(duì)列Q中(行⑦～⑨).在隨后選取初始節(jié)點(diǎn)的階段中，我們需要進(jìn)行k輪迭代，每輪選出Q中記錄的邊際收益最大的節(jié)點(diǎn)作為當(dāng)前輪次的候選節(jié)點(diǎn)，記為節(jié)點(diǎn)x，利用信用分布函數(shù)的子模特性，判斷當(dāng)前候選節(jié)點(diǎn)x的信用值更新輪次it是否符合當(dāng)前輪次|S|，若x.it=|S|，則將節(jié)點(diǎn)x插入到初始節(jié)點(diǎn)集合S中.這里需要注意的是，因?yàn)榧蟂加入了初始節(jié)點(diǎn)x，所以我們需要對V-S中節(jié)點(diǎn)的信用分布進(jìn)行更新.若x.it<|S|，則重新計(jì)算節(jié)點(diǎn)x的邊際收益，按更新后值的大小將節(jié)點(diǎn)x插入到Q中相應(yīng)位置，并返回判斷循環(huán)條件(行⑩～)，算法運(yùn)行結(jié)束時(shí)輸出初始節(jié)點(diǎn)集合S(行).

4 實(shí) 驗(yàn)

本節(jié)主要對CDTC模型和GA-TC算法的性能與計(jì)算結(jié)果進(jìn)行驗(yàn)證.針對不同方法選取的初始節(jié)點(diǎn)集合，通過設(shè)計(jì)對比實(shí)驗(yàn)比較影響力傳播范圍的大小，驗(yàn)證模型和算法對于影響力最大化初始節(jié)點(diǎn)選取的有效性和可靠性.同時(shí)設(shè)計(jì)實(shí)驗(yàn)對比不同方法在運(yùn)行時(shí)間方面的差異性表現(xiàn).最后通過設(shè)計(jì)實(shí)驗(yàn)?zāi)M并計(jì)算行為日志中測試集行為的真實(shí)傳播結(jié)果，對比于傳統(tǒng)信用分布模型比較并判斷我們的方法在影響力傳播預(yù)測方面是否具有更高的準(zhǔn)確度.

IC模型相鄰節(jié)點(diǎn)之間的激活概率通過EM算法學(xué)習(xí)而來[17]，而LT模型中鄰接節(jié)點(diǎn)v，u之間的激活概率使用ppv,u=1|Nin(u)|進(jìn)行計(jì)算[14-15]，其中|Nin(u)|表示節(jié)點(diǎn)u的入鄰居節(jié)點(diǎn)個(gè)數(shù).對于這2個(gè)模型，我們將Monte-Carlo模擬的次數(shù)均設(shè)定為10 000次.相比之下，在CDTC模型中對于任意節(jié)點(diǎn)u，設(shè)定u與相鄰節(jié)點(diǎn)之間見面條件下的激活概率α=c(c+|Nin(u)|)，其中平滑參數(shù)c的作用是當(dāng)c>0時(shí)，防止節(jié)點(diǎn)入度為0從而分式無意義的情況出現(xiàn).c值的設(shè)定也是有限定性要求的，當(dāng)c值過大，傳播增量路徑變小，時(shí)延約束條件τ對路徑長度的限定作用也會(huì)隨之減弱.通過實(shí)驗(yàn)比較，我們設(shè)定c=7，τ=15.相比之下，CD模型仍然使用原始的定義和設(shè)計(jì)模式[15].

實(shí)驗(yàn)環(huán)境為2.13 GHz Quad-Core Intel Xeon CPU E5506 8 GB RAM服務(wù)器.

Fig. 1 Influence spread consequence based on different models圖1 不同的模型對于初始集合的影響力傳播

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

本文中的實(shí)驗(yàn)數(shù)據(jù)集共2個(gè)，均來自SNAP公共數(shù)據(jù)集.第1個(gè)數(shù)據(jù)集源自圖片媒體分享網(wǎng)站Flickr[18]，總數(shù)據(jù)集包含105938張照片.根據(jù)照片的來源共分為4個(gè)部分，我們選擇其中之一作為實(shí)驗(yàn)對象，包含2 602個(gè)節(jié)點(diǎn)、222 292條邊和24 648張照片.處理之后得到2個(gè)文件，其中圖文件記錄網(wǎng)絡(luò)中用戶之間的關(guān)聯(lián)關(guān)系，用戶行為日志文件包含以時(shí)間順序記錄的用戶行為.值得注意的是，用戶行為日志文件中包含75 269條記錄，我們將用戶行為記錄分成2部分，即包含2 724種行為的訓(xùn)練集用戶行為記錄和包含1 816種行為的測試集用戶行為記錄.第2個(gè)數(shù)據(jù)集為High-energy physics citation network[19]，其中包含34 546個(gè)節(jié)點(diǎn)和421 578條邊.我們依據(jù)時(shí)間排列將不同文章中相同的引用看作是其作者對相同行為的執(zhí)行過程，以此構(gòu)建的用戶行為日志中包含412 674條記錄.

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

4.2.1 影響力傳播

首先在Flickr數(shù)據(jù)集上使用CDTC模型對問題進(jìn)行建模，并使用GA-TC算法求解初始節(jié)點(diǎn)集合.同理，依次在CD、IC和LT模型上對相同的數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn)，對于給定不同的k值，這4種方法得到的影響力傳播結(jié)果如圖1(a)所示.當(dāng)k=10時(shí)，4種方法的初始節(jié)點(diǎn)影響力傳播結(jié)果依次為24.74，29.78，20.87,17.79；當(dāng)k=50時(shí)，4種方法得到的結(jié)果依次變?yōu)?1.63，93.36，84.39，78.69.圖1(b)表示初始節(jié)點(diǎn)在CDTC模型和CD模型中初始用戶的影響力傳播結(jié)果(信用分布結(jié)果)與用戶真實(shí)影響力之間的差異對比關(guān)系.

綜合圖1可以看出，CDTC模型雖然在影響傳播方面略低于CD模型，但是其影響力計(jì)算值與真實(shí)影響力傳播結(jié)果之間的誤差要明顯小于CD模型，并且隨著初始節(jié)點(diǎn)個(gè)數(shù)的增加，這種優(yōu)勢呈現(xiàn)增長的趨勢.這主要是因?yàn)槲覀冊贑DTC模型中加入時(shí)延約束和時(shí)間延遲等現(xiàn)實(shí)因素，降低了對于影響力傳播結(jié)果過于樂觀的估計(jì)，并使得影響力計(jì)算更加真實(shí)可靠，保證初始節(jié)點(diǎn)選取的質(zhì)量.而相比于IC和LT模型，CDTC模型的另一個(gè)優(yōu)勢在于它是對用戶真實(shí)的行為記錄進(jìn)行學(xué)習(xí)，并結(jié)合用戶特征以及時(shí)間特性，而不是僅僅依據(jù)網(wǎng)絡(luò)結(jié)構(gòu)對用戶影響力和影響力的傳播進(jìn)行評價(jià)，所以我們的方法具有更加真實(shí)地反映用戶行為和影響力傳播的能力.

4.2.2 運(yùn)行時(shí)間

我們首先對Flickr數(shù)據(jù)集進(jìn)行測試.如圖2(a)所示，當(dāng)k=50時(shí)，在CDTC模型上和在CD模型上對初始節(jié)點(diǎn)的選取的運(yùn)行時(shí)間分別記錄為 1.96 min，2.19 min，相比之下，在IC和LT模型上的運(yùn)行時(shí)間分別記錄為30.98 min，145.82 min.為了便于觀察，我們擴(kuò)大CDTC模型和CD模型選取相同數(shù)量初始節(jié)點(diǎn)的運(yùn)行時(shí)間的縱坐標(biāo)范圍，運(yùn)行時(shí)間對比結(jié)果如圖2(b)所示.很明顯可以看出，在CDTC模型上選取初始節(jié)點(diǎn)在時(shí)間消耗方面呈現(xiàn)線性增長趨勢，且運(yùn)行時(shí)間少于在CD模型上選取相同數(shù)量節(jié)點(diǎn)所消耗的時(shí)間，隨著k值的增加，這種優(yōu)勢更加明顯.除了對用戶真實(shí)行為記錄的學(xué)習(xí)從而避免執(zhí)行大量且繁重的Monto-Carlo模擬，我們方法的優(yōu)勢還來源于時(shí)延約束條件對影響力傳播以及等價(jià)的信用分配范圍的限制作用.相比于CD模型，采用CDTC模型以及GA-TC算法對初始節(jié)點(diǎn)的選取工作具有高效性.值得說明的是，IC模型采用了CELF優(yōu)化策略，所以在時(shí)間消耗呈現(xiàn)階梯式分布；而LT模型則在時(shí)間消耗方面呈指數(shù)增長的趨勢.

Fig. 2 In Flickr dataset, the running time comparison under different models圖2 在Flickr數(shù)據(jù)集中，不同的模型對于初始節(jié)點(diǎn)選取所消耗的運(yùn)行時(shí)間

Fig. 3 In HEPC dataset, the running time comparison under different models圖3 在HEPC中，不同模型對于初始節(jié)點(diǎn)選取所消耗的運(yùn)行時(shí)間

我們同樣對HEPC(high-energy physics citation network)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).如圖3(a)所示，當(dāng)k=50時(shí)，4種方法對于初始節(jié)點(diǎn)選取的時(shí)間消耗分別為5.23 min，7.62 min，69.91 min,65.95 min.為了便于觀察，圖3(b)為縮小縱坐標(biāo)范圍之后2種方法的的對比結(jié)果.結(jié)合圖3可以看出，隨著初始節(jié)點(diǎn)個(gè)數(shù)的增加，排除實(shí)驗(yàn)結(jié)果誤差的影響，CDTC模型和CD模型對于初始節(jié)點(diǎn)的選取所消耗的時(shí)間呈現(xiàn)線性增長的趨勢，而LT模型上的時(shí)間消耗則呈現(xiàn)指數(shù)增長的趨勢.不僅如此，在IC模型和LT模型上對初始節(jié)點(diǎn)選取所消耗的時(shí)間遠(yuǎn)遠(yuǎn)大于在CDTC模型上對同等數(shù)量節(jié)點(diǎn)選取所花費(fèi)的時(shí)間.

綜上所述，CDTC模型和GA-TC算法在影響力最大化初始節(jié)點(diǎn)選取方面具有高效性.

4.2.3 影響力傳播預(yù)測

隨著商業(yè)營銷對用戶行為分析需求的不斷增加，針對特定信息或行為的分析和預(yù)測變得越來越有價(jià)值.在實(shí)驗(yàn)中，我們在Flickr數(shù)據(jù)集中使用CDTC和CD兩種模型對其測試集中記錄的行為進(jìn)行影響力傳播預(yù)測，測試集包含全部1 816種行為，實(shí)驗(yàn)結(jié)束后我們按照真實(shí)的影響力傳播結(jié)果對不同的行為進(jìn)行排序，并將實(shí)驗(yàn)預(yù)測結(jié)果與其真實(shí)值進(jìn)行對比.圖4(a)為在CDTC和CD模型上對編號1～1 816行為的影響力傳播預(yù)測對比結(jié)果，以測試集中經(jīng)過排序后行為編號為602的行為為例，真實(shí)的影響力傳播大小為8，使用CDTC模型和CD模型對該行為影響力傳播的預(yù)測值分別為6.76和6.03，同樣，以測試集中行為編號為1 727的行為為例，真實(shí)的影響力傳播大小為60，而使用CDTC模型和CD模型對該行為影響力傳播的預(yù)測值分別為37.87和35.64.值得注意的是，我們并不是根據(jù)某一單一行為進(jìn)行的影響力傳播預(yù)測，而是對測試集中1 816種不同的行為分別使用2種模型進(jìn)行測試，并將預(yù)測結(jié)果和真實(shí)值相比較.根據(jù)均平方根誤差的計(jì)算公式，2種方法得到預(yù)測結(jié)果的RMSE值分別為17.520 9和18.783 2.由此可見，除去個(gè)別噪點(diǎn)樣本，CDTC和CD模型對測試集行為樣本的影響力傳播預(yù)測結(jié)果均低于真實(shí)值；但從統(tǒng)計(jì)結(jié)果可以看出，相比于CD模型，在CDTC模型上對于用戶行為的預(yù)測效果有一定程度的優(yōu)化和提升.圖4(b)為對數(shù)坐標(biāo)系中的影響力傳播預(yù)測對比結(jié)果，圖中實(shí)心圓點(diǎn)近似將空心圈點(diǎn)覆蓋，并且趨近于星號點(diǎn)表示的真實(shí)值.除此之外，實(shí)驗(yàn)結(jié)果也表現(xiàn)出在CDTC模型上的影響力傳播結(jié)果具有無尺度網(wǎng)絡(luò)節(jié)點(diǎn)度分布的冪律分布特性，這也從側(cè)面印證了信用分布過程中用戶行為日志和用戶關(guān)系網(wǎng)絡(luò)兩者結(jié)合所發(fā)揮的關(guān)鍵性作用.綜上所述，實(shí)驗(yàn)結(jié)果表明我們提出的方法相比于傳統(tǒng)信用分布預(yù)測方法具有更高的精確度.

Fig. 4 Influence prediction for user actions圖4 用戶行為影響力預(yù)測

5 結(jié)論與展望

本文結(jié)合影響力傳播過程中存在的時(shí)間延遲特性，提出一種基于時(shí)延約束的信用分布模型CDTC，并基于該模型提出了基于時(shí)延約束的貪心算法GA-TC，近似求解影響力最大化問題.我們綜合考慮見面事件和激活事件，將見面概率和見面條件下相鄰節(jié)點(diǎn)的激活概率進(jìn)行優(yōu)化，得出相鄰節(jié)點(diǎn)之間激活成功的概率，結(jié)合影響力隨時(shí)間衰減的特性，對鄰接節(jié)點(diǎn)之間信用分配的進(jìn)行優(yōu)化定義.除此之外，在行為執(zhí)行結(jié)束后，通過對用戶行為日志和用戶關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)，將用戶之間反復(fù)見面并嘗試激活對行為傳播的阻礙作用投射到傳播路徑長度的增長方面，提出傳播增量路徑PIP，同時(shí)結(jié)合時(shí)延約束條件，對路徑中的節(jié)點(diǎn)逆向分配信用值，這樣不僅可以限制信用分布的范圍，還可以簡化信用分配的計(jì)算，提高執(zhí)行效率.不僅如此，通過學(xué)習(xí)真實(shí)的行為傳播記錄，我們不需要執(zhí)行Monte-Carlo模擬就可以實(shí)現(xiàn)對影響力傳播結(jié)果的精確評估，從而大幅度降低了算法的時(shí)間復(fù)雜度.在影響力傳播方面，也正是基于對真實(shí)行為傳播日志的學(xué)習(xí)，并加入見面概率、激活概率、衰減特性以及時(shí)延約束條件，我們的模型能夠更加真實(shí)合理地反映用戶的行為，保證初始節(jié)點(diǎn)選取的質(zhì)量.實(shí)驗(yàn)結(jié)果表明在CDTC模型中使用GA-TC算法對初始節(jié)點(diǎn)集合的選取工作具有高效性和可靠性.

對于時(shí)延約束的影響力最大化問題，還有許多方面可以在未來的工作中做進(jìn)一步研究.首先，雖然加入見面概率來表現(xiàn)用戶延遲接觸行為信息影響的可能性，但是并未考慮用戶對于信息可能存在的偏好特性.其次，用戶的特異性判定也并未加入到其影響力的評估中.我們可以通過學(xué)習(xí)用戶行為日志，對用戶的行為習(xí)慣以及行為偏好進(jìn)行分析，并將結(jié)果加入到影響力的傳播以及信用分布的判定當(dāng)中.除此之外，我們還可以通過對用戶行為標(biāo)簽的學(xué)習(xí)，更加真實(shí)準(zhǔn)確地判別用戶的行為.在未來的工作中，我們將繼續(xù)對不同種類的社會(huì)網(wǎng)絡(luò)進(jìn)行基于主題的影響力挖掘，設(shè)計(jì)出更加真實(shí)有效的影響力傳播模型和影響力最大化算法.

[1]Wu Xindong, Li Yi, Li Lei. Influence analysis in online social networks [J]. Chinese Journal of Computers, 2014, 37(4): 735-752 (in Chinese)(吳信東, 李毅, 李磊. 在線社交網(wǎng)絡(luò)影響力分析[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 735-752)

[2]Xu Ge, Zhang Sai, Chen Hao, et al. Measurement and analysis in online social networks [J]. Chinese Journal of Computers, 2014, 36(1): 165-188 (in Chinese)(徐恪, 張賽, 陳昊, 等. 在線社會(huì)網(wǎng)絡(luò)的測量與分析[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 36(1): 165-188)

[3]Xiao Tao, Chen Yunfang, Zhang Wei, et al. Review of influence in social networks [J]. Journal of Computer Applications, 2014, 34(4): 980-985 (in Chinese)(夏濤, 陳云芳, 張偉, 等. 社會(huì)網(wǎng)絡(luò)中的影響力綜述[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(4): 980-985)

[4]Domingos P, Richardson M. Mining the network value of customers[C] //Proc of the 7th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2001: 57-66

[5]Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing[C] //Proc of the 8th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 61-70

[6]Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[C] //Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146

[7]Rahimkhani K, Aleahmad A, Rahgozar M, et al. A fast algorithm for finding most influential people based on the linear threshold model [J]. Expert Systems with Applications, 2015, 42(3): 1353-1361

[8]Chen W, Yuan Y, Zhang L. Scalable influence maximization in social networks under the linear threshold model[C] //Proc of 2010 IEEE Int Conf on Data Mining. Piscataway,NJ: IEEE, 2010: 88-97

[9]Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C] //Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 199-207

[10]Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C] // Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 1029-1038

[11]Chen Wei, Lu Wei, Zhang Ning. Time-critical influence maximization in social networks with time-delayed diffusion process [J]. Chinese Journal of Engineering Design, 2012, 19(5): 340-344

[12]Yang D N, Hung H J, Lee W C, et al. Maximizing acceptance probability for active friending in on-line social networks[C] //Proc of the 19th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 713-721

[13]Li H, Bhowmick S S, Sun A. CINEMA: Conformity-aware greedy algorithm for influence maximization in online social networks[C] //Proc of the 16th Int Conf on Extending Database Technology. New York: ACM, 2013: 323-334

[14]Liu Q, Xiang B, Chen E, et al. Influence maximization over large-scale social networks: A bounded linear approach[C] //Proc of the 23rd ACM Int Conf on Information and Knowledge Management. New York: ACM, 2014: 171-180

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

[16]Saito K, Nakano R, Kimura M. Prediction of information diffusion probabilities for independent cascade model[C] //Proc of the 12th Int Conf on Knowledge-Based Intelligent Information and Engineering Systems. Berlin: Springer, 2008: 67-75

[17]Goyal A, Bonchi F, Lakshmanan L V S. Learning influence probabilities in social networks[C] //Proc of the 3rd ACM Int Conf on Web Search and Data Mining. New York: ACM, 2015: 241-250

[18]Mcauley J, Leskovec J. Image labeling on a network: Using social-network metadata for image classification [J]. Computer Vision-ECCV, 2012, 7575(1): 828-841

[19]Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: Densification laws, shrinking diameters and possible explanations[C] //Proc of the 11th ACM SIGKDD Int Conf on Knowledge Discovery in Data Mining. New York: ACM, 2005: 177-187

Deng Xiaoheng, born in 1974. Professor and PhD at Central South University. Senior member of CCF. His main research interests include several areas in wireless communications and networking, especially on network transmission and routing optimization with cross-layer design method.

Cao Dejuan, born in 1992. Master candidate in the School of Information and Communication Engineering, Central South University. Her main research interests include influence maximization in social networks and big data analysis (caodejuan@csu.edu.cn).

Pan Yan, born in 1990. Master candidate in the School of Information Science and Engineering, Central South University. His main research interests include influence maximization in social networks (panyan@csu.edu.cn).

Shen Hailan, born in 1974. Received her PhD degree from Central South University in 2011. Currently associate professor at the School of Information Science and Engineering, Central South University. Her main research interests include mobile computing, big data analysis, and oppor-tunistic network (hailansh@csu.edu.cn).

Chen Zhigang, born in 1964. PhD supervisor. Fellow member of CCF. His main research interests include network computing and distributed processing (czg@csu.edu.cn).

An Optimized Credit Distribution Model in Social Networks with Time-Delay Constraint

Deng Xiaoheng1, Cao Dejuan1, Pan Yan1, Shen Hailan1, and Chen Zhigang2

1(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083)2(SchoolofSoftware,CentralSouthUniversity,Changsha410075)

The research of influence maximization in social networks is emerging as a promising opportunity for successful viral marketing. Influence maximization with time-delay constraint (IMTC) is to identify a set of initial individuals who will influence others and lead to a maximum value of influence spread consequence under time-delay constraint. Most of the existing models focus on optimizing the simulation consequence of influence spread, and time-delay factors and time-delay constraint are always ignored. The credit distribution with time-delay constraint model (CDTC) incorporates the meeting and activation probabilities to optimize the distribution of credit considering time-delay constraint, and utilizes the optimized relationships of meeting and activation probabilities to evaluate the ability to influence on adjacent individuals. Furthermore, the obstructive effect due to repeated attempts of meeting and activation is reflected by the length of increased propagation paths. After assigning the credit along with the increased propagation paths learned from users’ action-logs, the nodes which obtain maximal marginal gain are selected to form the seed set by the greedy algorithm with time-delay constraint (GA-TC). The experimental results based on real datasets show that the proposed approach is more accurate and efficient compared with other related methods.

social networks; influence maximization; time-delay constraint; credit distribution; greedy algorithm

2015-12-18；

2016-07-05

國家自然科學(xué)基金項(xiàng)目(61379058,61272149,61379057,61350011) This work was supported by the National Natural Science Foundation of China (61379058, 61272149, 61379057, 61350011).

TP39