劉子圖 全紫薇 毛如柏 劉 勇 朱敬華

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

近年來(lái)隨著社交網(wǎng)絡(luò)的快速發(fā)展，越來(lái)越多的用戶使用新浪微博、Twitter、Facebook等社交網(wǎng)站分享自己的生活.據(jù)統(tǒng)計(jì)Facebook截至2018年12月31日每月的活躍用戶超過(guò)23億[1].由此可見(jiàn)社交網(wǎng)已經(jīng)成為許多人生活的一部分.與此同時(shí)各大社交平臺(tái)也在促進(jìn)著各種消息的快速傳播.例如在新浪微博上平均每天有幾億條微博產(chǎn)生，在每天產(chǎn)生的微博中會(huì)包含很多重要信息.用戶更新一條微博可能包含著用戶對(duì)某消息的態(tài)度和觀點(diǎn)[2]，也可能是分享身邊的新鮮事[3].預(yù)測(cè)消息的傳播范圍在病毒營(yíng)銷(xiāo)、輿情監(jiān)控、商品推薦等諸多領(lǐng)域都有廣泛的應(yīng)用，因此受到了數(shù)據(jù)挖掘領(lǐng)域的廣泛關(guān)注.

目前對(duì)消息傳播范圍進(jìn)行預(yù)測(cè)所使用的方法主要有2種：1)根據(jù)消息特征或者消息的特定類(lèi)型進(jìn)行傳播范圍預(yù)測(cè).例如：可以根據(jù)發(fā)布的Twitter是否帶有標(biāo)志性的圖片從而預(yù)測(cè)它在Facebook上的傳播范圍[4]；也可以通過(guò)分析發(fā)布的Twitter是否包含對(duì)消息傳播有利的內(nèi)容來(lái)預(yù)測(cè)它的傳播范圍[5].然而使用消息特征預(yù)測(cè)消息傳播范圍顯然不能推廣到不同的平臺(tái).2)使用社交網(wǎng)絡(luò)中用戶的拓?fù)浣Y(jié)構(gòu)[5-7]或消息的轉(zhuǎn)發(fā)結(jié)構(gòu)[8]來(lái)預(yù)測(cè)消息傳播范圍.然而在很多實(shí)際應(yīng)用中，我們很難獲得消息的傳播結(jié)構(gòu)以及用戶的拓?fù)浣Y(jié)構(gòu)，通常只能獲得消息的傳播序列.例如在豆瓣網(wǎng)中，對(duì)于電影的影評(píng)只顯示用戶在什么時(shí)間評(píng)價(jià)了電影，而沒(méi)有表明用戶因?yàn)槭艿侥男┯脩粲绊懖旁u(píng)價(jià)該電影.因此，只利用消息的傳播序列而不考慮用戶的拓?fù)浣Y(jié)構(gòu)來(lái)預(yù)測(cè)消息的傳播范圍具有更廣泛的應(yīng)用場(chǎng)景.

本文研究了無(wú)拓?fù)浣Y(jié)構(gòu)條件下的消息傳播范圍預(yù)測(cè)問(wèn)題，提出了一種無(wú)拓?fù)浣Y(jié)構(gòu)的消息傳播范圍預(yù)測(cè)方法NT-EP.該方法由4部分構(gòu)成：1)利用消息傳播隨時(shí)間衰減的特性為每個(gè)消息構(gòu)造一個(gè)加權(quán)的傳播圖，在傳播圖上使用隨機(jī)游走策略獲取多條傳播路徑，再使用Word2vec方法計(jì)算每個(gè)用戶的特征向量；2)把目標(biāo)消息的傳播路徑替換成用戶的特征向量序列輸入到雙向門(mén)控制循環(huán)神經(jīng)網(wǎng)絡(luò)(bidirectional gated recurrent unite, Bi-GRU)，結(jié)合注意力機(jī)制計(jì)算出目標(biāo)消息的傳播特征向量；3)考慮到不同消息傳播可能存在的相互影響，利用目標(biāo)消息發(fā)生前的其他消息，使用梯度下降方法計(jì)算出其他消息的影響向量；4)將目標(biāo)消息的傳播特征向量和其他消息的影響向量結(jié)合在一起，使用多層感知機(jī)(multilayer perceptron, MLP)擬合出目標(biāo)消息的傳播范圍.與其他方法相比，NT-EP方法具有2個(gè)明顯的創(chuàng)新：1)首次考慮了消息之間的相互影響；2)利用消息傳播隨時(shí)間衰減特性為每條消息構(gòu)造加權(quán)傳播圖，抽取傳播路徑.

NT-EP方法充分考慮了消息之間的相互影響.這是因?yàn)樵谙⒌膫鞑ミ^(guò)程中，消息與消息之間必然會(huì)產(chǎn)生影響.例如在公布個(gè)人所得稅起征點(diǎn)改革消息之后的一段時(shí)間內(nèi)，用戶會(huì)增加對(duì)包含具體稅率改革內(nèi)容的消息的關(guān)注.因此個(gè)人所得稅起征點(diǎn)改革消息對(duì)有相關(guān)內(nèi)容的消息傳播產(chǎn)生了影響.消息傳播中的相互影響來(lái)自于2方面：1)來(lái)源于消息本身的內(nèi)容，也就是消息本身是否為熱點(diǎn)消息，是否會(huì)被普遍關(guān)注；2)來(lái)源于已經(jīng)參與消息傳播的用戶對(duì)于其他消息傳播的影響.在一段時(shí)間內(nèi)，用戶使用社交網(wǎng)絡(luò)的時(shí)間上限是固定的.用戶瀏覽某些消息的時(shí)間更多意味著用戶瀏覽其他消息的時(shí)間會(huì)減少.因此本文方法NT-EP考慮了目標(biāo)消息發(fā)生前后其他消息對(duì)目標(biāo)消息可能存在的各種影響，構(gòu)造了其他消息的影響向量，結(jié)合目標(biāo)消息的傳播特征向量來(lái)預(yù)測(cè)目標(biāo)消息的傳播范圍.本文實(shí)驗(yàn)部分比較了利用消息影響與不利用消息影響NT-EP方法的2種變體，證明了消息影響對(duì)范圍預(yù)測(cè)的重要性.

NT-EP方法根據(jù)傳播序列構(gòu)造加權(quán)傳播圖，來(lái)模擬接近真實(shí)傳播軌跡的傳播路徑.在無(wú)拓?fù)浣Y(jié)構(gòu)的條件下，我們只有用戶的動(dòng)作序列.但是用戶在接受消息過(guò)程中必然會(huì)受到之前接受相同消息用戶的影響，而且影響強(qiáng)度依賴于接受消息的時(shí)間差.假設(shè)在消息a傳播過(guò)程中用戶V1接受了消息a，在用戶V1之前用戶V2和用戶V3也接受消息a，并且用戶V2接受的時(shí)間早于用戶V3,那么直覺(jué)上用戶V3對(duì)用戶V1接受消息影響更大.根據(jù)消息傳播隨消息衰減的特性，我們構(gòu)造有向邊V2→V1和V3→V1，V3→V1邊上的權(quán)值大于V2→V1，邊上的權(quán)值代表了影響強(qiáng)度，權(quán)值依賴于2個(gè)用戶接受消息的時(shí)間差.NT-EP方法按照這種方式為每個(gè)消息構(gòu)造一個(gè)隨時(shí)間衰減的傳播圖，然后使用隨機(jī)游走策略抽取多條傳播路徑，這些傳播路徑更接近于真實(shí)的傳播軌跡.本文實(shí)驗(yàn)部分構(gòu)造了NT-EP方法的2種變體，一種利用時(shí)間衰減構(gòu)造傳播圖，另一種不利用時(shí)間衰減構(gòu)造傳播圖，比較了這2種變體的性能，再次證明了消息傳播符合時(shí)間衰減特性.本文的貢獻(xiàn)有4個(gè)方面：

1) 提出了一種新的無(wú)拓?fù)浣Y(jié)構(gòu)條件下的消息傳播范圍預(yù)測(cè)方法NT-EP.

2) NT-EP利用了消息之間的相互影響，提高了消息傳播范圍預(yù)測(cè)的準(zhǔn)確性.

3) NT-EP利用了消息傳播隨時(shí)間衰減的特性為消息構(gòu)造加權(quán)傳播圖，使得抽取的隨機(jī)游走路徑更接近真實(shí)的傳播軌跡，提高了消息傳播范圍預(yù)測(cè)的準(zhǔn)確性.

4) 實(shí)驗(yàn)結(jié)果表明，NT-EP能對(duì)無(wú)拓?fù)浣Y(jié)構(gòu)條件下的消息傳播范圍進(jìn)行準(zhǔn)確預(yù)測(cè)，并且預(yù)測(cè)效果明顯優(yōu)于現(xiàn)有的方法.

本文源碼和數(shù)據(jù)可以從https://github.com/Vimotus/NT-EP下載.

1 相關(guān)工作

在社交網(wǎng)中消息的傳播范圍包括微博或Twitter在一定時(shí)間內(nèi)的轉(zhuǎn)發(fā)數(shù)[4-5,9-11]、照片的被瀏覽數(shù)[2]、視頻被點(diǎn)贊的次數(shù)[12-14]、學(xué)術(shù)論文在一定時(shí)間內(nèi)被引用的次數(shù)[15]等多種情況.相關(guān)工作大致可以分為3類(lèi)：1)利用消息本身的特征進(jìn)行預(yù)測(cè)；2)利用消息的傳播序列和用戶的社交關(guān)系進(jìn)行預(yù)測(cè)；3)只利用消息的傳播序列進(jìn)行預(yù)測(cè).

消息特征或者消息的特定類(lèi)型可以幫助預(yù)測(cè)消息的傳播范圍.例如文獻(xiàn)[4]根據(jù)發(fā)布的Twitter是否帶有標(biāo)志性的圖片來(lái)預(yù)測(cè)它在Facebook上的轉(zhuǎn)發(fā)次數(shù)；文獻(xiàn)[12]分析視頻在規(guī)定的時(shí)間段內(nèi)觀看人數(shù)的增長(zhǎng)量來(lái)預(yù)測(cè)消息被觀看的次數(shù).然而消息的傳播范圍除了消息本身的特征，更多依賴發(fā)布消息或者轉(zhuǎn)發(fā)消息用戶的影響力，因此此類(lèi)方法預(yù)測(cè)效果一般，而且不易推廣到其他平臺(tái).

目前的絕大多數(shù)研究都是利用消息的傳播序列和用戶的社交關(guān)系進(jìn)行預(yù)測(cè).該類(lèi)方法又可分為2種：1)將消息傳播預(yù)測(cè)視為分類(lèi)問(wèn)題，通過(guò)預(yù)測(cè)傳播范圍是否會(huì)超過(guò)某個(gè)閾值來(lái)預(yù)測(cè)某個(gè)消息是否會(huì)變成流行消息[7,12,14];2)將消息傳播范圍預(yù)測(cè)看作回歸問(wèn)題，預(yù)測(cè)消息的最終傳播范圍或者截止到某一時(shí)刻的傳播范圍.此類(lèi)研究通常使用確定的時(shí)間屬性[12]、早期消息傳播的拓?fù)浣Y(jié)構(gòu)[6,15-16]以及用戶的拓?fù)浣Y(jié)構(gòu)[17]，來(lái)進(jìn)行傳播范圍預(yù)測(cè).文獻(xiàn)[18]學(xué)習(xí)多數(shù)消息傳播過(guò)程中的普遍拓?fù)浣Y(jié)構(gòu)預(yù)測(cè)消息傳播范圍.此類(lèi)方法需要消息的傳播結(jié)構(gòu)或者用戶的拓?fù)浣Y(jié)構(gòu)，但實(shí)際應(yīng)用中這些信息不易獲得.

目前在無(wú)拓?fù)浣Y(jié)構(gòu)(用戶社交關(guān)系)條件下，對(duì)消息傳播范圍預(yù)測(cè)的研究相對(duì)較少.2010年Gomez-Rodriguez等人[19]利用用戶被影響的時(shí)間特征推斷消息傳播的路徑，然后累加路徑上的用戶數(shù)計(jì)算傳播范圍.2012年Simma等人[20]提出了基于連續(xù)時(shí)間和霍克斯進(jìn)程的隨機(jī)過(guò)程范圍預(yù)測(cè)模型.2014年Bourigault等人[21]提出了基于學(xué)習(xí)映射觀察動(dòng)態(tài)時(shí)間對(duì)連續(xù)空間的影響，將參與擴(kuò)散的節(jié)點(diǎn)投射到潛在的表達(dá)空間,然后計(jì)算用戶向量的相似性判斷用戶是否會(huì)被另一個(gè)用戶影響.2016年Bourigault等人[22]使用用戶表達(dá)空間，將用戶的影響能力映射到一個(gè)多維空間中，通過(guò)計(jì)算多維空間中2個(gè)向量的距離來(lái)計(jì)算是否會(huì)被影響.

現(xiàn)有方法并沒(méi)有考慮消息在傳播過(guò)程中會(huì)存在相互影響的情況.本文利用了消息之間的相互影響，提出了一種無(wú)拓?fù)浣Y(jié)構(gòu)的傳播范圍預(yù)測(cè)方法NT-EP,該方法具有5個(gè)優(yōu)勢(shì)：1)是一種端對(duì)端的學(xué)習(xí)框架；2)適用于無(wú)拓?fù)浣Y(jié)構(gòu)；3)考慮了消息傳播過(guò)程中的相互作用；4)抽取的隨機(jī)游走路徑更接近真實(shí)的傳播路徑；5)結(jié)合目標(biāo)消息的傳播向量和其他消息的影響向量，同時(shí)利用注意力機(jī)制預(yù)測(cè)傳播范圍，使預(yù)測(cè)結(jié)果更準(zhǔn)確.

2 問(wèn)題定義

3 NT-EP傳播范圍預(yù)測(cè)框架

對(duì)于無(wú)拓?fù)浣Y(jié)構(gòu)下社交消息傳播預(yù)測(cè)問(wèn)題，本文提出了一種新的社交消息傳播范圍預(yù)測(cè)方法NT-EP，其框架如圖1所示.方法NT-EP首先根據(jù)消息動(dòng)作日志中的傳播時(shí)間差為每個(gè)消息構(gòu)造一個(gè)加權(quán)的傳播圖，如圖1的①②所示.傳播圖邊上的數(shù)字代表用戶之間的影響概率.在傳播圖構(gòu)造完成之后，使用隨機(jī)游走方式從傳播圖中提取若干條該消息可能的傳播路徑，如圖1的③所示，然后使用Word2vec方法計(jì)算出每個(gè)用戶的初始的特征向量.傳播路徑上的每個(gè)用戶獲得初始的特征向量后，再將消息的傳播路徑送入Bi-GRU中得到用戶的最終向量表示，如圖1的④所示.傳播路徑上的每個(gè)用戶獲得最終的特征向量后，再結(jié)合注意力機(jī)制計(jì)算出每個(gè)消息的傳播特征向量，如圖1的⑩所示.

在消息傳播過(guò)程中，不同消息之間會(huì)存在相互影響.因此我們也必須計(jì)算目標(biāo)消息發(fā)生前其他消息的可能影響.如圖1的⑤～⑧所示，使用和目標(biāo)消息類(lèi)似的方式，構(gòu)造加權(quán)傳播圖、隨機(jī)游走、Word2vec等方法計(jì)算其他消息參與用戶的特征向量，然后構(gòu)造其他消息的傳播向量.

此后，使用梯度下降方法計(jì)算出其他消息的影響向量，如圖1的⑨所示.最后NT-EP方法將目標(biāo)消息的傳播特征向量和其他消息的影響向量結(jié)合在一起，使用MLP擬合出目標(biāo)消息的增量傳播范圍，如圖1的所示.

Fig.1 NT-EP method framework圖1 NT-EP方法的框架

3.1 傳播路徑選取

給定的動(dòng)作日志通常對(duì)每個(gè)消息的動(dòng)作按照傳播時(shí)間排序，如圖2的①所示.用戶V1在時(shí)間1接受了消息A1，用戶V2在時(shí)間2接受了消息A1,….從給定的動(dòng)作日志中我們無(wú)法獲得消息真實(shí)的傳播軌跡.因?yàn)檎鎸?shí)的情況可能是：用戶V3在時(shí)間3接受了消息A1可能是因?yàn)橛脩鬡3和用戶V1是朋友，并且用戶V3看到了用戶V1接受了消息A1，從而影響用戶V3也接受了消息A1.用戶V3不認(rèn)識(shí)用戶V2，V3接受了消息A1從來(lái)沒(méi)有受到用戶V2的影響.這樣的真實(shí)傳播軌跡在沒(méi)有用戶社交關(guān)系的條件下是無(wú)法獲得的.

根據(jù)社交網(wǎng)上消息傳播呈指數(shù)衰減特性[13]，我們有理由認(rèn)為當(dāng)用戶V3接受消息A1的時(shí)候，用戶V2影響的概率大于用戶V1影響的概率，因?yàn)閂2接受消息A1的時(shí)間離V3接受消息A1的時(shí)間更近.因此，我們根據(jù)2個(gè)用戶接受消息的時(shí)間差來(lái)刻畫(huà)2個(gè)用戶的影響.假設(shè)用戶Vi和Vj接受消息的時(shí)間分別為ti和tj，并且ti

w(ti,tj)=e-μ(tj-ti)，

(1)

其中，μ為調(diào)整時(shí)間差影響的超參數(shù)，實(shí)驗(yàn)中給出了該參數(shù)的選擇過(guò)程.計(jì)算出每個(gè)消息中用戶之間的影響概率后，我們可以根據(jù)影響概率為每個(gè)消息構(gòu)造一個(gè)加權(quán)圖來(lái)模擬該消息的真實(shí)傳播軌跡.如圖2的②所示，如果在消息A1中用戶V1接受消息A1的時(shí)間早于用戶V2接受消息A1的時(shí)間，則從用戶V1引出一條邊指向用戶V2，邊上的權(quán)值表示用戶V1對(duì)用戶V2的影響概率，由式(1)計(jì)算.在得到加權(quán)圖后，我們?cè)賹?duì)加權(quán)圖歸一化，使得每個(gè)節(jié)點(diǎn)出邊的概率和為1，如圖2的③所示.為了模擬真實(shí)的傳播路徑，我們?cè)跉w一化的加權(quán)圖上根據(jù)邊上的概率進(jìn)行隨機(jī)游走.每次游走的開(kāi)始節(jié)點(diǎn)都是接受消息的第1個(gè)用戶，例如圖2的③中的V1.針對(duì)每個(gè)消息，我們采樣K條路徑，并且每條路徑的長(zhǎng)度為T(mén).當(dāng)游走過(guò)程中遇到某條路徑長(zhǎng)度小于T的時(shí)候，在后面若干補(bǔ)充位，讓每條路徑長(zhǎng)度都等于T.在抽取了所有消息的傳播路徑后，我們使用詞向量方法Word2vec計(jì)算每個(gè)用戶的初始特征向量，細(xì)節(jié)見(jiàn)3.3節(jié).

Fig.2 Constructing a weighted graph of message propagation圖2 構(gòu)造消息傳播的加權(quán)圖

3.2 其他消息影響向量

社交網(wǎng)中消息與消息之間存在著不同程度的聯(lián)系，一個(gè)消息的傳播可能促進(jìn)或者抑制另一個(gè)消息的傳播.例如國(guó)家個(gè)人所得稅更改方案公布時(shí)，短時(shí)間內(nèi)對(duì)稅率信息查詢有促進(jìn)傳播的作用.此外，用戶上網(wǎng)瀏覽消息的時(shí)間有限，對(duì)于某些消息的關(guān)注增加，對(duì)其他消息的關(guān)注就會(huì)降低.

下面介紹其他消息對(duì)目標(biāo)消息的影響能力.該影響能力通過(guò)一個(gè)影響向量來(lái)刻畫(huà).設(shè)當(dāng)前的目標(biāo)消息為a，a發(fā)生時(shí)間為ta.如果消息A1在消息a之前發(fā)生，并且消息A1的發(fā)生時(shí)間與消息a的發(fā)生時(shí)間距離較近，那么消息A1的傳播很可能會(huì)對(duì)消息a的傳播產(chǎn)生影響.基于這一思想，我們獲取在ta之前很短的時(shí)間段τ內(nèi)發(fā)生的消息集合Sa={A1,A2,…,Am}，該集合內(nèi)每個(gè)消息對(duì)消息a傳播的影響都需要考慮.假設(shè)影響消息集合Sa={A1,A2,…,Am}中每個(gè)消息截至?xí)r刻ta的傳播范圍分別為n1，n2，…，nm，發(fā)生時(shí)間分別為t1，t2，…，tm，并且滿足t1

(2)

消息Ai的傳播能力pi來(lái)自于參與消息Ai的用戶傳播能力，因此消息Ai的傳播能力pi可以表示為

(3)

其中，pi表示影響消息Ai的傳播向量，xj是使用Word2vec的skip-gram模型從傳播路徑上得到的用戶向量，因?yàn)橄i的傳播范圍為ni，所以有ni個(gè)不同的用戶向量xj.對(duì)于消息ei的影響向量qi，本文使用梯度下降算法求解，使式(2)的目標(biāo)函數(shù)最小化，具體算法如算法1所示.在得到影響消息集合Sa={A1,A2,…,Am}中每個(gè)消息的影響向量{q1,q2,…,qk}后，我們計(jì)算整個(gè)消息集合Sa對(duì)當(dāng)前目標(biāo)消息a的影響向量qSa.

(4)

算法1.計(jì)算其他消息影響向量.

輸入:其他消息的傳播向量pi(i=1,2,…,m)、其他消息的當(dāng)前傳播范圍ni(i=1,2,…,m)、學(xué)習(xí)率λ;

輸出:其他消息的影響向量qi(i=1,2,…,m).

① Initqi(i=1,2,…,m)；

② repeat

④qi←qi-λΔg；

⑤ until convergence.

3.3 目標(biāo)消息傳播向量

在抽取了所有消息的傳播路徑后，我們將每條傳播路徑當(dāng)作一個(gè)句子，路徑上的每個(gè)用戶當(dāng)作句子中的單詞，輸入到Word2vec[16]的skip-gram模型中，得到每個(gè)用戶初始的特征向量.假設(shè)用戶特征向量的維度為H.

為了知道消息在傳播過(guò)程中會(huì)被哪些用戶影響，我們使用相同的方法再?gòu)暮笙蚯疤幚砺窂缴系拿總€(gè)用戶.因此本文使用的是雙向GRU(Bi-GRU)，拼接隱藏狀態(tài)的輸出得到對(duì)應(yīng)用戶的最終向量表示.具體通過(guò)式(5)對(duì)用戶向量進(jìn)行更新:

(5)

其中j表示傳播路徑中第j個(gè)節(jié)點(diǎn)，模型輸入的用戶節(jié)點(diǎn)向量xj和隱藏狀態(tài)hi-1一起作為輸入，并通過(guò)GRU的公式計(jì)算更新.其中W和U作為訓(xùn)練期間學(xué)習(xí)的GRU參數(shù).

如圖1的④所示，每條傳播路徑經(jīng)過(guò)GRU處理后，會(huì)得到該路徑上每個(gè)用戶的最終向量表示h1,h2,…；然后我們使用注意力機(jī)制合并這些用戶的最終向量表示h1,h2,…，計(jì)算該傳播路徑的向量表示；最后對(duì)所有傳播路徑的向量表示累加求和，得到目標(biāo)消息傳播向量pa：

(6)

3.4 傳播范圍預(yù)測(cè)

目標(biāo)消息a的傳播范圍依賴于目標(biāo)消息a的傳播向量pa和其他消息的影響向量qSa，因此我們將目標(biāo)消息a的傳播向量pa和其他消息的影響向量qSa融合為一條向量la，即：

la=pa+αqSa，

(7)

其中，α為其他消息影響向量的權(quán)重，實(shí)驗(yàn)部分給出了參數(shù)α的選擇過(guò)程.將融合后的向量la作為一個(gè)多層感知機(jī)的輸入，輸出預(yù)測(cè)的傳播范圍f(a)=fMLP(la)，其中MLP為一個(gè)多層感知機(jī)，f(a)為消息a的預(yù)測(cè)傳播范圍.

4 實(shí)驗(yàn)結(jié)果及分析

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

本文中我們使用2套無(wú)拓?fù)浣Y(jié)構(gòu)的傳播數(shù)據(jù)進(jìn)行實(shí)驗(yàn)并對(duì)結(jié)果評(píng)估.數(shù)據(jù)描述如表1所示：

Table1 Dataset Statistics表1 實(shí)驗(yàn)數(shù)據(jù)描述

1) 微博[18].微博是基于用戶關(guān)系的信息分享、傳播的社交媒體.我們從論文中提供的數(shù)據(jù)中選取在2012-09-28—2012-10-29之間發(fā)生的1 280個(gè)消息的動(dòng)作日志.截取的數(shù)據(jù)中包含261 839個(gè)用戶、1 280個(gè)消息以及933 683條傳播記錄.

2) Flixster[11].Flixster是一個(gè)電影社交網(wǎng)站，可以讓用戶分享電影的評(píng)分，討論新的電影.我們使用1 000個(gè)消息的動(dòng)作日志.其中包含109 816個(gè)用戶和581 202條傳播記錄.

實(shí)驗(yàn)中預(yù)測(cè)消息傳播范圍時(shí)通過(guò)調(diào)整時(shí)間長(zhǎng)度t和Δt來(lái)選擇預(yù)測(cè)的時(shí)間區(qū)間.t表示消息從發(fā)生開(kāi)始到當(dāng)前時(shí)刻所經(jīng)過(guò)的時(shí)間，也就是消息已經(jīng)發(fā)生了多久；Δt表示在時(shí)間t之后的時(shí)間長(zhǎng)度.實(shí)驗(yàn)中我們選擇t與Δt的大小分別為12 h,24 h,36 h來(lái)對(duì)消息的傳播范圍進(jìn)行預(yù)測(cè).實(shí)驗(yàn)中需要進(jìn)行其他消息影響向量和用戶特征向量占用空間存儲(chǔ).實(shí)驗(yàn)中將數(shù)據(jù)按7∶1∶2的比例分為訓(xùn)練集、驗(yàn)證集、測(cè)試集.數(shù)據(jù)集中每個(gè)消息的全部動(dòng)作日志只出現(xiàn)在訓(xùn)練集、測(cè)試集、驗(yàn)證集中的一個(gè).我們?cè)谟?xùn)練集中訓(xùn)練模型，在驗(yàn)證集中調(diào)整超參數(shù)，在測(cè)試集中測(cè)試方法的性能.

4.2 評(píng)估指標(biāo)

本文使用均方誤差(mean squared error, MSE)來(lái)評(píng)估傳播范圍預(yù)測(cè)效果.這是回歸任務(wù)中常見(jiàn)的評(píng)估指標(biāo).它是由預(yù)測(cè)值與真實(shí)值差的平方和求平均得到，定義為

(8)

本文使用精確率、召回率、F1_score來(lái)評(píng)估消息熱點(diǎn)預(yù)測(cè)效果.在熱點(diǎn)消息預(yù)測(cè)時(shí)，我們只進(jìn)行采樣12 h的傳播并預(yù)測(cè)消息的最終傳播范圍.實(shí)驗(yàn)中設(shè)置一個(gè)閾值，超過(guò)閾值會(huì)被認(rèn)為是熱點(diǎn)消息，實(shí)驗(yàn)中選擇的閾值為1 000.具體如下：

1)TP(真正例).TP表示預(yù)測(cè)傳播范圍大于閾值，并且實(shí)際傳播范圍大于閾值的消息數(shù).

2)FN(假負(fù)例).FN表示預(yù)測(cè)傳播范圍大于閾值，但實(shí)際傳播范圍小于閾值的消息數(shù).

3)FP(假正例).FP表示預(yù)測(cè)傳播范圍小于閾值，但實(shí)際傳播范圍大于閾值的消息數(shù).

4)TN(真負(fù)例).TN表示預(yù)測(cè)傳播范圍小于閾值，并且實(shí)際傳播范圍小于閾值的消息數(shù).

5) 精確率P(precision).P表示在所有被預(yù)測(cè)為熱點(diǎn)的消息中，實(shí)際為熱點(diǎn)的消息所占的百分比,即：

(9)

6) 召回率R(recall).R表示在所有實(shí)際為熱點(diǎn)的消息中，被預(yù)測(cè)為熱點(diǎn)的消息所占的百分比，即：

(10)

7)F1分?jǐn)?shù)(F1_score).F1_score是統(tǒng)計(jì)學(xué)中同時(shí)兼顧精確率和召回率的一種指標(biāo)，即：

(11)

4.3 對(duì)比方法

1) Embedding-IC[19].它是一種嵌入版本的獨(dú)立級(jí)聯(lián)模型，充分考慮用戶之間的相互影響，把用戶嵌入到隱藏投影空間中，借助EM(expectation-maximization)算法求發(fā)送方和接收方的嵌入向量，推測(cè)傳播概率.根據(jù)計(jì)算出的傳播概率計(jì)算最終消息傳播范圍.

2) Deepcas[6].它是一種消息傳播范圍預(yù)測(cè)方法.通過(guò)隨機(jī)采樣獲得消息擴(kuò)散的路徑，使用GRU網(wǎng)絡(luò)將路徑轉(zhuǎn)換為路徑的表達(dá)向量.最后通過(guò)注意力機(jī)制來(lái)預(yù)測(cè)消息的傳播范圍.

3) NT-EP-T.它是NT-EP的一種變體.通過(guò)時(shí)間衰減游走采樣傳播路徑，不利用消息的相互影響.

4) NT-EP-R.它是NT-EP的一種變體.不使用時(shí)間衰減游走(使用傳統(tǒng)的隨機(jī)游走)采樣傳播路徑，但是利用消息的相互影響.

實(shí)驗(yàn)中，傳播序列的選擇算法使用C語(yǔ)言編寫(xiě)，在VS環(huán)境下編譯運(yùn)行，對(duì)比算法也使用C語(yǔ)言編寫(xiě).NT-EP中神經(jīng)網(wǎng)絡(luò)部分使用python語(yǔ)言和tensorflow框架編寫(xiě)，在Anaconda3環(huán)境下編譯運(yùn)行.評(píng)價(jià)標(biāo)準(zhǔn)也使用python語(yǔ)言進(jìn)行處理.所使用的臺(tái)式機(jī)環(huán)境為Intel?Core i7-7700K 4.2 GHz CPU，16 GB RAM，操作系統(tǒng)為Windows10.

4.4 參數(shù)選擇

Fig.3 Influence of different d of user vector on MSE圖3 用戶向量不同維度d對(duì)MSE的影響

我們?cè)隍?yàn)證集中調(diào)整模型的超參數(shù)，包括用戶向量維度d、其他消息影響向量的權(quán)重α、時(shí)間差的影響參數(shù)μ、學(xué)習(xí)率λ、消息抽取的路徑數(shù)K、路徑長(zhǎng)度T等.實(shí)驗(yàn)中設(shè)置算法1中計(jì)算消息影響向量的學(xué)習(xí)率λ=0.000 5.

參數(shù)選擇均使用微博數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，采樣12 h傳播序列，預(yù)測(cè)未來(lái)12 h傳播范圍，圖3～7為不同參數(shù)下NT-EP方法的MSE值.我們先隨機(jī)固定其他參數(shù)來(lái)考察用戶向量維度d對(duì)MSE的影響，實(shí)驗(yàn)結(jié)果如圖3所示.隨著維度d的增加，MSE的值在逐漸減小，表明預(yù)測(cè)效果越來(lái)越好；但當(dāng)維度超過(guò)50時(shí)，預(yù)測(cè)效果改善并不明顯.為了平衡預(yù)測(cè)效果和運(yùn)行時(shí)間，本文后面的所有實(shí)驗(yàn)都采用用戶向量維度d=50.

Fig.4 Influence of different α of selection on MSE圖4 α選取對(duì)MSE的影響

Fig.5 Influence of μ value selection on MSE圖5 μ值選取對(duì)MSE的影響

Fig.6 Influence of K value selection on MSE圖6 K值的選擇對(duì)MSE的影響

Fig.7 Influence of T value selection on MSE圖7 T值的選擇對(duì)MSE的影響

其他參數(shù)的選取也采用上述類(lèi)似的處理方式.在選取其他消息影響向量的權(quán)重α?xí)r，我們固定用戶向量維度d=50.圖4為α選取過(guò)程，我們選取α?xí)r在0到1之間每0.2取值，其中α=0.8時(shí)MSE的取值最優(yōu)，因此本文后面的所有實(shí)驗(yàn)都采用α=0.8.圖5給出了參數(shù)μ的選擇過(guò)程，先固定用戶向量維度d=50和α=0.8，其他參數(shù)隨機(jī)選擇，觀察參數(shù)μ對(duì)MSE的影響，在μ=1時(shí)MSE值最小.因此后續(xù)實(shí)驗(yàn)選擇μ=1時(shí)作為時(shí)間衰減游走采樣的參數(shù)值.傳播路徑數(shù)量K與傳播路徑長(zhǎng)度T的選擇過(guò)程如圖6和圖7所示，因此后續(xù)實(shí)驗(yàn)中我們固定K=200和T=10作為傳播路徑數(shù)量和傳播路徑長(zhǎng)度.

4.5 實(shí)驗(yàn)結(jié)果

不同方法對(duì)傳播范圍的預(yù)測(cè)效果如表2和表3所示.其中表2為微博數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)中分別采樣12 h,24 h,36 h，然后對(duì)未來(lái)12 h,24 h,36 h的傳播范圍預(yù)測(cè).表3為Flixster數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)中分別采樣10 d,20 d,30 d，然后對(duì)未來(lái)10 d,20 d,30 d的傳播范圍預(yù)測(cè).從表2和表3可以看出，本文方法NT-EP及其變體NT-EP-R和NT-EP-T的預(yù)測(cè)效果均優(yōu)于對(duì)比方法Deepcas和Embedding-IC.表3中的實(shí)驗(yàn)結(jié)果好于表2中的結(jié)果，其原因在于Flixster數(shù)據(jù)比微博數(shù)據(jù)的消息數(shù)更多、每個(gè)消息的傳播范圍更廣，能讓各種模型學(xué)習(xí)得更充分.

Embedding-IC方法所在行只有一個(gè)實(shí)驗(yàn)結(jié)果，因?yàn)镋mbedding-IC方法和時(shí)間長(zhǎng)度Δt無(wú)關(guān).Embedding-IC把所有用戶映射到一個(gè)向量空間中，通過(guò)距離計(jì)算用戶之間的影響概率.該方法考慮所有用戶對(duì)當(dāng)前用戶的影響，導(dǎo)致許多無(wú)關(guān)的用戶也進(jìn)行計(jì)算，但實(shí)際上激活時(shí)間上相近的用戶才可能產(chǎn)生影響,所以Embedding-IC方法很容易導(dǎo)致過(guò)擬合，預(yù)測(cè)效果較差.Deepcas使用傳統(tǒng)隨機(jī)游走采樣傳播路徑，沒(méi)有考慮時(shí)間差對(duì)傳播消息的影響，而且Deepcas也沒(méi)有考慮消息之間的相互影響，因此預(yù)測(cè)效果并不理想.

Table 2 MSE Result of Weibo Dataset表2 微博數(shù)據(jù)傳播范圍預(yù)測(cè)MSE結(jié)果

Notes:tis the sampling time, Δtis the future sampling time, the best results are in bold.

Table 3 MSE Result of Flixster Dataset表3 Flixster數(shù)據(jù)集傳播范圍預(yù)測(cè)結(jié)果

Notes:tis the sampling time, Δtis the future sampling time, the best results are in bold.

NT-EP方法的變體NT-EP-T是通過(guò)時(shí)間衰減游走采樣傳播路徑，不利用消息的相互影響預(yù)測(cè)時(shí)間傳播范圍.從表2和表3可以看出，NT-EP-T優(yōu)于Deepcas，說(shuō)明時(shí)間差對(duì)消息的傳播起重要作用，消息之間確實(shí)存在相互影響.NT-EP的變體NT-EP-R利用消息的相互影響，但不使用時(shí)間衰減游走采樣傳播路徑.從表2和3可以看出，NT-EP方法同時(shí)考慮消息的相互影響與時(shí)間差對(duì)消息傳播的作用，預(yù)測(cè)效果明顯優(yōu)于Deepcas,NT-EP-T和NT-EP-R.

為了進(jìn)一步驗(yàn)證本文方法的有效性，我們也對(duì)熱點(diǎn)消息進(jìn)行了預(yù)測(cè)，實(shí)驗(yàn)結(jié)果如表4所示.實(shí)驗(yàn)中我們使用微博數(shù)據(jù)采樣12 h，對(duì)未來(lái)12 h,24 h,36 h是否會(huì)成為熱點(diǎn)消息進(jìn)行預(yù)測(cè)，我們?cè)趯?shí)驗(yàn)中設(shè)置的閾值為1 000.如果傳播范圍預(yù)測(cè)值大于閾值，則預(yù)測(cè)為熱點(diǎn)消息.實(shí)驗(yàn)結(jié)果再次表明本文方法NT-EP優(yōu)于現(xiàn)有方法，也再次證明了消息之間的相互影響確實(shí)存在以及消息傳播具有時(shí)間衰減等特性.

Table 4 Precision,Recall,F1_score Results of Weibo Data表4 微博數(shù)據(jù)精確率、召回率、F1_score結(jié)果

Notes:tis the sampling time, the best results are in bold.

5 結(jié) 論

本文研究了無(wú)拓?fù)浣Y(jié)構(gòu)條件下的消息傳播范圍預(yù)測(cè)問(wèn)題，提出一種社交消息傳播范圍預(yù)測(cè)方法NT-EP.NT-EP首次利用消息之間的相互影響來(lái)提高范圍預(yù)測(cè)的準(zhǔn)確性.實(shí)驗(yàn)結(jié)果表明：NT-EP在多個(gè)評(píng)價(jià)指標(biāo)上優(yōu)于現(xiàn)有的方法Deepcas和Embedding-IC.未來(lái)研究我們準(zhǔn)備加入用戶興趣向量和用戶基本屬性進(jìn)行范圍預(yù)測(cè)，以及增加多層注意力機(jī)制嘗試改善預(yù)測(cè)性能.