預(yù)測信息傳播中的轉(zhuǎn)發(fā)選擇

王永慶, 沈華偉, 程學(xué)旗

(中國科學(xué)院 計(jì)算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重量實(shí)驗(yàn)室，北京 100190)

預(yù)測信息傳播中的轉(zhuǎn)發(fā)選擇

王永慶, 沈華偉, 程學(xué)旗

(中國科學(xué)院 計(jì)算技術(shù)研究所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重量實(shí)驗(yàn)室，北京 100190)

在信息傳播中，用戶在重復(fù)接收同一信息的情況下其轉(zhuǎn)發(fā)行為會(huì)具有一定的傾向性。對這種轉(zhuǎn)發(fā)的傾向性建模是影響力分析、傳播動(dòng)力學(xué)、社會(huì)推薦等一系列信息傳播相關(guān)應(yīng)用研究領(lǐng)域中的一個(gè)關(guān)鍵問題。本文假設(shè)用戶的轉(zhuǎn)發(fā)選擇行為主要由用戶間的人際影響力決定。人際影響力的大小由信息傳播者的影響力和信息接收者的易感性共同作用。本文從真實(shí)的信息傳播記錄中推斷出用戶隱式的影響力和易感性，進(jìn)而提出了一種轉(zhuǎn)發(fā)選擇模型。該模型能夠有效解決目前方法存在的對轉(zhuǎn)發(fā)選擇行為建模不充分和模型泛化能力差的問題。本文選取典型的轉(zhuǎn)發(fā)選擇建模方法作為比較，將所提的轉(zhuǎn)發(fā)選擇模型在新浪微博數(shù)據(jù)上進(jìn)行對比驗(yàn)證。實(shí)驗(yàn)表明，本文所提的模型在兩種評(píng)價(jià)指標(biāo)上均取得更好效果，證明了所提模型的有效性。

信息傳播；轉(zhuǎn)發(fā)選擇；影響力；易感性

1 引言

社會(huì)媒體(Social media)的誕生極大提高了人們獲取和傳遞信息的能力。例如通過博客、論壇、微博、百科等平臺(tái)，用戶利用互動(dòng)式的交流和表達(dá)方式，使得信息經(jīng)由用戶的社會(huì)關(guān)系有序傳播。在這種信息傳播中，社會(huì)媒體用戶能夠有較多機(jī)會(huì)通過其社交關(guān)系重復(fù)接收同一信息： 一方面加深用戶對該信息的認(rèn)識(shí)使得用戶有更高的概率對該信息進(jìn)行轉(zhuǎn)發(fā)；另一方面，用戶必須從多個(gè)信息源的轉(zhuǎn)發(fā)中做出轉(zhuǎn)發(fā)選擇?，F(xiàn)有文獻(xiàn)表明，用戶的轉(zhuǎn)發(fā)選擇行為具有一定的傾向性。一般而言，這種轉(zhuǎn)發(fā)選擇行為被視作是人際影響力的直接體現(xiàn)[1- 2]。因此如何理解用戶在轉(zhuǎn)發(fā)選擇時(shí)的行為傾向，是研究人際影響力的切入點(diǎn)之一，建模并預(yù)測轉(zhuǎn)發(fā)選擇行為也是影響力分析[3]、傳播動(dòng)力學(xué)[1, 4]、社會(huì)推薦[5]等一系列信息傳播相關(guān)應(yīng)用研究領(lǐng)域中的一個(gè)關(guān)鍵問題。

現(xiàn)有嘗試對用戶人際影響力進(jìn)行建模的方法可大致分為三類： 利用網(wǎng)絡(luò)結(jié)構(gòu)，利用歷史傳播記錄信息和利用用戶傳播屬性的建模。利用網(wǎng)絡(luò)結(jié)構(gòu)的影響力分析主要是從度分布(degree distribution)[6]，聚集系數(shù)(clustering coefficient)[7]，連接強(qiáng)度(tie strength)[8]，介數(shù)(betweenness)[9]，中心度度量(centrality)[10-11]等網(wǎng)絡(luò)的物理性質(zhì)上進(jìn)行討論。在利用歷史傳播記錄信息的影響力建模方面，Tang等人[12]提出了綜合主題模型(topic model)及傳播記錄的建模方式，在引文網(wǎng)絡(luò)中較好識(shí)別了各話題下的代表性人物及發(fā)表論文。Gomez等人[13]提出了基于生存模型的建模方法，該方法假設(shè)用戶在一次信息傳播的過程中，不斷地被周圍新“感染”的鄰居影響，直至最終轉(zhuǎn)發(fā)消息。Myers[14]等人提出了針對外部消息源影響力的建模方法，并較好擬合了信息傳播的爆發(fā)曲線。在利用用戶傳播屬性建模方面，Saito等人[15]提出了顯式的用戶屬性建模方法，估計(jì)用戶個(gè)體間的信息傳播概率，并預(yù)測信息的傳播發(fā)生情況。Cui等人[16]提出了隱式的用戶及文檔屬性建模方法，并用于推斷用戶對影響用戶的偏好以及用戶對內(nèi)容的偏好問題。以上所述方法利用了對人際影響力的不同認(rèn)識(shí)，部分解釋了信息傳播中的現(xiàn)象，但仍無法較好解決主要由人際影響力所導(dǎo)致的轉(zhuǎn)發(fā)選擇問題。所存在的主要問題有： 1)基于網(wǎng)絡(luò)分析的方法忽略了平臺(tái)本身的異質(zhì)性，這類分析方法無法保證某一網(wǎng)絡(luò)的物理性質(zhì)與存在傳播現(xiàn)象之間存在關(guān)聯(lián)的普適性，因果分析不夠準(zhǔn)確； 2)基于歷史傳播記錄信息的建模方法目前還沒有較好泛化能力，只能就觀測節(jié)點(diǎn)對間的傳播情況進(jìn)行推斷及預(yù)測，缺失大量節(jié)點(diǎn)對間的傳播記錄信息會(huì)使得該分類中的建模方式失效。3)大量的傳播及用戶數(shù)據(jù)以匿名化的方式存在，這使得顯式的用戶傳播屬性較難獲得。并且目前沒有較為系統(tǒng)的研究工作支持人際影響力與用戶傳播屬性之間的關(guān)系。

為了避免上述問題，有效建模信息傳播中用戶的轉(zhuǎn)發(fā)選擇行為，本文提出了轉(zhuǎn)發(fā)選擇模型(Forwarding-Preference Model，F(xiàn)PM)。FPM模型能夠?qū)﹄[式的用戶傳播屬性進(jìn)行建模，將用戶傳播屬性按照用戶在信息傳播中的傳播者及接收者角色分為影響力(influence)及易感性(susceptibility)屬性[17]。在信息傳播過程中，傳播者與接收者間的人際影響力由傳播者的影響力向量和接收者的易感性向量的內(nèi)積確定。用戶的轉(zhuǎn)發(fā)選擇行為是信息接收者以較高概率選擇對其更具影響力的傳播者的選擇過程。目前而言，這種從人際影響力角度對轉(zhuǎn)發(fā)選擇行為的建模工作是一個(gè)較新的信息傳播應(yīng)用問題。本文形式化了轉(zhuǎn)發(fā)選擇問題，并對該應(yīng)用問題給出了一種建模求解的方法。FPM模型的優(yōu)勢在于：

1) FPM模型有較好的泛化能力。所推斷隱式的用戶影響力與易感性屬性與用戶節(jié)點(diǎn)相關(guān)，與用戶間的連邊無關(guān)。對于缺失的節(jié)點(diǎn)對間的傳播記錄信息，其人際影響仍可通過節(jié)點(diǎn)與其他節(jié)點(diǎn)的歷史交互推斷獲得。

2) FPM模型是對人際影響力導(dǎo)致的用戶轉(zhuǎn)發(fā)選擇行為的直接建模，量化并推斷人際影響力。通過實(shí)際數(shù)據(jù)的驗(yàn)證表明，本文所提模型與原有估計(jì)方法相比在評(píng)價(jià)指標(biāo)上具有較大幅度的提升。表明了人際影響力與用戶轉(zhuǎn)發(fā)選擇行為之間存在相關(guān)性，并證實(shí)了所提模型的有效性。

3) 相比建模用戶顯式的傳播屬性，F(xiàn)PM模型所推斷的隱式用戶傳播屬性僅需歷史傳播記錄信息，受數(shù)據(jù)獲取的限制更少，這使得所提模型具有較好的適用性。

本文設(shè)計(jì)了迭代算法，通過所觀測的用戶轉(zhuǎn)發(fā)偏好，學(xué)習(xí)獲得用戶隱式的影響力及易感性屬性。在實(shí)驗(yàn)部分，在新浪微博數(shù)據(jù)上對FPM模型及所選典型的比較方法進(jìn)行評(píng)測。實(shí)驗(yàn)結(jié)果表明，F(xiàn)PM模型能夠在本文所給定的兩個(gè)評(píng)價(jià)標(biāo)準(zhǔn)上均取得較為顯著的預(yù)測性能提升，模型對用戶轉(zhuǎn)發(fā)選擇行為的建模是有效的。

文章的后續(xù)部分組織如下： 第二章是相關(guān)工作的介紹；第三章形式化和建模用戶由人際影響力所產(chǎn)生的轉(zhuǎn)發(fā)選擇過程，給出FPM模型，并給出對應(yīng)的學(xué)習(xí)算法。第四章對實(shí)驗(yàn)數(shù)據(jù)、評(píng)價(jià)指標(biāo)、對照方法以及比較結(jié)果進(jìn)行介紹及說明。最后在第五章中給出本文的結(jié)論。

2 相關(guān)工作

對用戶在信息傳播中的轉(zhuǎn)發(fā)選擇行為建模和推斷的工作是目前信息傳播領(lǐng)域一個(gè)新的應(yīng)用研究問題。對該問題的認(rèn)識(shí)，目前主要認(rèn)為用戶在信息傳播中的轉(zhuǎn)發(fā)選擇行為主要由人際影響力所決定。大量的相關(guān)工作主要集中于用戶在信息傳播中的傳播動(dòng)力學(xué)研究。

信息傳播動(dòng)力學(xué)的相關(guān)實(shí)證研究工作利用統(tǒng)計(jì)規(guī)律發(fā)現(xiàn)信息傳播的相關(guān)因素和因果聯(lián)系。Romero等人[18]利用在Twitter上醫(yī)藥信息的傳播記錄發(fā)現(xiàn)，信息傳播相較于疾病傳播是一種更為復(fù)雜的傳播方式。與疾病傳播不同，用戶在同一信息下暴露多次時(shí)會(huì)產(chǎn)生明顯的邊際效應(yīng)。Leskovec等人[4]研究了病毒式營銷市場的傳播動(dòng)力學(xué)，揭示了信息傳播與其他傳播系統(tǒng)的不同，并初步探討了影響信息傳播的用戶屬性。Huang等人[5]通過豆瓣數(shù)據(jù)實(shí)證了用戶評(píng)價(jià)對其他用戶評(píng)分的影響，證明病毒式營銷市場中用戶之間影響力的確實(shí)存在。Gruhl等人[19]通過博客數(shù)據(jù)分別從宏觀的話題層次與微觀的用戶層次對信息傳播的動(dòng)力學(xué)進(jìn)行探討，并提出了基于宏觀與微觀層次的影響力模型。Leskovec[20]利用博客關(guān)系圖及圖上的傳播模式模擬博客空間中的信息傳播。Ugander等人[1]在Twitter數(shù)據(jù)中分析了傳播網(wǎng)絡(luò)的結(jié)構(gòu)特征，揭示了傳播網(wǎng)絡(luò)的結(jié)構(gòu)多樣性與信息傳播之間的聯(lián)系。Crane等人[21]度量了信息傳播中觸發(fā)評(píng)論行為的內(nèi)源及外源因素。Bao等人[2]證實(shí)了信息傳播中的累積效應(yīng)(cumulative effects)，并利用傳播網(wǎng)絡(luò)的結(jié)構(gòu)分析方法對用戶的轉(zhuǎn)發(fā)選擇進(jìn)行了初步探索。Tang等人[12]結(jié)合話題與社會(huì)網(wǎng)絡(luò)，建模了話題相關(guān)的影響力模型，并在引文網(wǎng)絡(luò)中進(jìn)行驗(yàn)證。Aral等人[3]引入了影響力與易感性兩種傳播屬性的度量方式，利用Twitter數(shù)據(jù)對信息傳播中用戶傳播屬性的分布進(jìn)行了實(shí)證研究。Cui等人[16]建模了文檔層次的人際影響力模型，提出了用戶與文檔的相關(guān)隱屬性向量。這些工作在一定程度上給予我們對信息傳播動(dòng)力學(xué)的理解，啟發(fā)我們對轉(zhuǎn)發(fā)選擇行為的建模工作。

3 轉(zhuǎn)發(fā)選擇行為建模

表 1 符號(hào)及對應(yīng)描述

圖 1 (a)社會(huì)網(wǎng)絡(luò)；(b)三條消息的傳播記錄；(c)由(b)中所示傳播記錄所構(gòu)建的三個(gè)傳播網(wǎng)絡(luò)；(d)根據(jù)所有傳播記錄綜合構(gòu)建的傳播網(wǎng)絡(luò)。

根據(jù)傳播網(wǎng)絡(luò)的定義，在傳播網(wǎng)絡(luò)中，一個(gè)用戶的所有父親節(jié)點(diǎn)都是該用戶在某次信息傳播中潛在的影響者。對此我們定義如下：

在一次信息傳播中，用戶v影響鄰居集合內(nèi)的所有節(jié)點(diǎn)都可能對用戶v造成影響，并促成用戶v對該信息進(jìn)行轉(zhuǎn)發(fā)?；谛畔鞑サ囊话慵僭O(shè)[22]： 1)一個(gè)用戶對一條信息有且僅能產(chǎn)生一次有效轉(zhuǎn)發(fā)；2)當(dāng)用戶轉(zhuǎn)發(fā)某信息時(shí)，其轉(zhuǎn)發(fā)行為能夠立即被網(wǎng)絡(luò)中其他關(guān)聯(lián)用戶感知并造成影響；3)一個(gè)用戶在一次信息傳播中，有且僅能影響某一可能被其影響的用戶一次。根據(jù)信息傳播的一般假設(shè)，我們定義真實(shí)影響鄰居集合如下：

定義2 真實(shí)影響鄰居集合。關(guān)于信息m的一次信息傳播，用戶v的真實(shí)影響鄰居集合

根據(jù)以上的符號(hào)及定義，本文采用離散選擇模型(discrete choice model)[23]建模用戶在轉(zhuǎn)發(fā)信息m時(shí)所作的選擇行為，其形式化如下：

圖2 FPM的概率圖模型

假設(shè)用戶間的轉(zhuǎn)發(fā)選擇過程相互獨(dú)立，信息m傳播中所有的轉(zhuǎn)發(fā)選擇過程可以建立其概率似然分布如下：

進(jìn)一步地，假設(shè)各信息的傳播獨(dú)立。則在所有的信息傳播C中，用戶轉(zhuǎn)發(fā)選擇行為的概率似然分布可以表示為

求解目標(biāo)是獲得用戶的屬性矩陣I和S，使得等式在觀測數(shù)據(jù)下獲得最大似然。為了方便求解，本文將優(yōu)化目標(biāo)取負(fù)對數(shù)形式化為：

這里采用投影梯度法(Projected Gradient)[24]對公式進(jìn)行求解優(yōu)化。梯度的計(jì)算如下：

該算法的具體步驟在算法1中具體描述。

算法1 參數(shù)估計(jì)輸入：給定時(shí)間內(nèi)的傳播記錄，最大迭代步R輸出：用戶的影響力屬性矩陣I和易感性屬性矩陣S1．通過傳播記錄構(gòu)建傳播網(wǎng)絡(luò)；2．隨機(jī)初始化參數(shù)矩陣I，S；3．repeat4． fori=1tondo5． 計(jì)算?L/?Iu和?L/?Sv6． endfor7． 更新I和S8．until最大迭代步完成

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

本節(jié)將通過新浪微博數(shù)據(jù)對本文所提模型進(jìn)行驗(yàn)證。首先，詳細(xì)介紹所采用數(shù)據(jù)集的格式，抽取方法及訓(xùn)練、測試集的設(shè)定。接著引入兩種評(píng)價(jià)方法對轉(zhuǎn)發(fā)選擇的預(yù)測結(jié)果進(jìn)行評(píng)價(jià)，并討論分析FPM模型中各參數(shù)對模型結(jié)果的影響。最后，選取幾種較為典型的轉(zhuǎn)發(fā)選擇模型，通過與這些典型的轉(zhuǎn)發(fā)選擇模型比較，驗(yàn)證FPM模型的有效性。

4.1 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集來自新浪微博，該數(shù)據(jù)集由WISE 2012 Challenge*http://www.wise2012.cs.ucy.ac.cy/challenge.html發(fā)布提供。數(shù)據(jù)集抓取了新浪微博從2009年9月17日至2012年2月17日的所有傳播記錄。本文選擇其中2011年1月1日至2月15日的傳播記錄進(jìn)行實(shí)驗(yàn)，將所抽取的數(shù)據(jù)按時(shí)間切分為三個(gè)等長的片段，分別記作數(shù)據(jù)集D1，D2，D3。去除了沒有同時(shí)出現(xiàn)于三個(gè)切分片段數(shù)據(jù)上的用戶及其對應(yīng)傳播記錄，以保證在實(shí)驗(yàn)中所有用戶的轉(zhuǎn)發(fā)選擇在一個(gè)閉集內(nèi)。在實(shí)際傳播過程中，存在用戶僅在某信息下暴露一次就轉(zhuǎn)發(fā)的實(shí)例。在這種情況下，真實(shí)影響鄰居的集合大小為1，不需要對其進(jìn)行轉(zhuǎn)發(fā)選擇行為的預(yù)測。因此本文的樣本僅保留用戶在某一信息下多次暴露的情況。實(shí)驗(yàn)采用交叉驗(yàn)證的方式共進(jìn)行三組，所得的三個(gè)模型分別記作M1，M2，M3。交叉驗(yàn)證的策略如下： 第一輪R1在數(shù)據(jù)D1上訓(xùn)練獲得模型M1，在數(shù)據(jù)D2和D3上進(jìn)行測試；第二輪R2在數(shù)據(jù)D2上訓(xùn)練獲得模型M2，在數(shù)據(jù)D1和D3上進(jìn)行測試；第一輪R3在數(shù)據(jù)D3上訓(xùn)練獲得模型M3，在數(shù)據(jù)D1和D2上進(jìn)行測試；數(shù)據(jù)集的基本統(tǒng)計(jì)信息見表 2。

表 2 數(shù)據(jù)集的基本統(tǒng)計(jì)信息

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文引入了兩種評(píng)價(jià)標(biāo)準(zhǔn)用于判斷模型對預(yù)測用戶轉(zhuǎn)發(fā)選擇行為的準(zhǔn)確度度量。

準(zhǔn)確率： 準(zhǔn)確率度量用于判斷模型是否準(zhǔn)確判斷了用戶的轉(zhuǎn)發(fā)選擇，計(jì)算其在總體預(yù)測樣本上的準(zhǔn)確率。其形式如下：

模型在準(zhǔn)確率上的值越大，則模型的預(yù)測效果越好。

MRR (序值倒數(shù)的平均Mean Reciprocal Rank)： MRR[25]是一種在信息檢索領(lǐng)域中較為常見的統(tǒng)計(jì)測量方法，主要用于度量在排序中真實(shí)的首位元素在預(yù)測排序中的正確程度。MRR的具體定義如下：

4.3 參數(shù)設(shè)置

為了能夠讓FPM模型取得較好的結(jié)果，本文設(shè)計(jì)了一系列實(shí)驗(yàn)對FPM模型參數(shù)進(jìn)行調(diào)整。FPM所需要調(diào)整的主要參數(shù)包括了隱用戶影響力與易感性屬性維度和算法最大迭代步數(shù)。

隱用戶影響力與易感性屬性維度d： 用戶的影響力與易感性屬性維度d與FPM模型的表達(dá)能力直接相關(guān)，但是過高的維度同時(shí)會(huì)導(dǎo)致模型的過高的優(yōu)化代價(jià)。因此需要對維度d的大小進(jìn)行討論，設(shè)置一個(gè)較為合適的維度值用于FPM模型。在實(shí)驗(yàn)過程中，本文取d=5,10,15,20,25,30,35,40，分別進(jìn)行了測試。

圖 3(a)展示了實(shí)驗(yàn)結(jié)果，由于訓(xùn)練數(shù)據(jù)分布于三個(gè)不同的傳播時(shí)間區(qū)間，因此其傳播表現(xiàn)存在一定的區(qū)分，這導(dǎo)致了所示曲線的差異?？梢园l(fā)現(xiàn)在三個(gè)模型關(guān)于維度d的調(diào)整中，均呈現(xiàn)維度與評(píng)價(jià)指標(biāo)的正相關(guān)性，即維度越高FPM模型的預(yù)測性能在準(zhǔn)確率和MRR兩個(gè)度量指標(biāo)上的結(jié)果更好。實(shí)驗(yàn)結(jié)果與本文的認(rèn)識(shí)保持一致： FPM的表達(dá)能力提高能夠明顯改善模型的預(yù)測效果?？紤]計(jì)算復(fù)雜度與效率的平衡問題，三個(gè)模型中同時(shí)取d=40。

圖3 FPM模型的參數(shù)設(shè)置

迭代步數(shù)R： 本文采用最大迭代步作為投影梯度法的收斂策略(其他的收斂策略見文獻(xiàn)[24])。為了提高算法的運(yùn)行效率，需要設(shè)置一個(gè)較為合理的最大迭代步。如圖3(b)所示，三個(gè)模型在算法迭代到50次左右時(shí)都取得了較為良好的收斂效果。為了保證算法收斂，本文在三個(gè)模型中同時(shí)取最大迭代步R為100。

4.4 比較方法

為了評(píng)價(jià)FPM模型的有效性，本文引入了幾種典型的轉(zhuǎn)發(fā)選擇模型進(jìn)行比較：

1) 偏好模型(Preference Attachment Model，PAM)[6]。偏好模型是經(jīng)典的網(wǎng)絡(luò)生長模型，該模型認(rèn)為網(wǎng)絡(luò)中新加入的節(jié)點(diǎn)容易與節(jié)點(diǎn)度較高的節(jié)點(diǎn)產(chǎn)生鏈接。這里本文將其應(yīng)用于信息傳播中，假設(shè)用戶容易與傳播網(wǎng)絡(luò)中節(jié)點(diǎn)度較高的節(jié)點(diǎn)發(fā)生轉(zhuǎn)發(fā)行為。

2) 伯努利分布模型(Bernoulli Distribution Model，BDM)[26]。伯努利分布模型認(rèn)為用戶間的轉(zhuǎn)發(fā)概率服從伯努利分布，該分布可以從歷史傳播記錄中通過最大似然方法統(tǒng)計(jì)獲得。用戶的轉(zhuǎn)發(fā)選擇過程容易發(fā)生在具有較高轉(zhuǎn)發(fā)概率的用戶節(jié)點(diǎn)對之間。

3) 杰卡德系數(shù)模型(Jaccard Index Model，JIM)[26]。不同于伯努利模型，杰卡德系數(shù)模型認(rèn)為用戶間的轉(zhuǎn)發(fā)概率服從杰卡德系數(shù)，該分布可以從歷史傳播記錄中通過杰卡德系數(shù)的計(jì)算獲得。用戶的轉(zhuǎn)發(fā)選擇過程容易發(fā)生在具有較高轉(zhuǎn)發(fā)概率的用戶節(jié)點(diǎn)對之間。

4) 最大期望模型(EM Model，EMM)[27]。最大期望模型利用EM方法根據(jù)歷史傳播記錄估計(jì)用戶間的轉(zhuǎn)發(fā)概率。用戶的轉(zhuǎn)發(fā)選擇過程容易發(fā)生在具有較高轉(zhuǎn)發(fā)概率的用戶節(jié)點(diǎn)對之間。

5) 轉(zhuǎn)發(fā)第一消息源策略(Forward First Strategy，F(xiàn)RS)。這種轉(zhuǎn)發(fā)策略認(rèn)為用戶會(huì)從其真實(shí)影響鄰居中轉(zhuǎn)發(fā)最早發(fā)布該消息的用戶。

6) 轉(zhuǎn)發(fā)最末消息源策略(Forward Last Strategy，F(xiàn)LS)。這種轉(zhuǎn)發(fā)策略認(rèn)為用戶會(huì)從其真實(shí)影響鄰居中轉(zhuǎn)發(fā)最近發(fā)布該消息的用戶。

7) 任意轉(zhuǎn)發(fā)策略(Forward Randomly Strategy，F(xiàn)RS)。這種轉(zhuǎn)發(fā)策略認(rèn)為用戶會(huì)從其真實(shí)影響鄰居中隨機(jī)轉(zhuǎn)發(fā)發(fā)布該消息用戶。

4.5 比較結(jié)果

根據(jù)前述的實(shí)驗(yàn)方法，本文將FPM模型與選用的典型轉(zhuǎn)發(fā)選擇模型在真實(shí)數(shù)據(jù)集上進(jìn)行比較，并通過兩種評(píng)價(jià)指標(biāo)進(jìn)行了結(jié)果展示，實(shí)驗(yàn)結(jié)果列于表 4中。由于FRS，F(xiàn)LS，F(xiàn)RS策略僅考慮被轉(zhuǎn)發(fā)用戶，因此無法計(jì)算MRR值，表中對應(yīng)部分空缺。從表中可以明顯地發(fā)現(xiàn)，本文所提的FPM模型，在預(yù)測的準(zhǔn)確率和MRR兩項(xiàng)評(píng)價(jià)標(biāo)準(zhǔn)上均明顯優(yōu)于其他方法，特別是在準(zhǔn)確率的度量上，顯著高于次優(yōu)的比較方法。這是因?yàn)镕PM模型能夠有效解決目前存在方法泛化能力不足的問題。將三個(gè)切分?jǐn)?shù)據(jù)集所構(gòu)成的傳播網(wǎng)絡(luò)進(jìn)行對照發(fā)現(xiàn)，接近70%的網(wǎng)絡(luò)連邊在對照網(wǎng)絡(luò)中沒有出現(xiàn)，而典型的轉(zhuǎn)發(fā)選擇模型在處理這些情況時(shí)，其預(yù)測效果接近隨機(jī)猜測。另外，F(xiàn)PM模型的結(jié)果同時(shí)也驗(yàn)證了對用戶轉(zhuǎn)發(fā)選擇行為建模的有效性： 用戶的轉(zhuǎn)發(fā)選擇行為主要取決于人際影響力，本文所提的FPM模型是對人際影響力的一種較為準(zhǔn)確的建模方法。

表4 PFM與比較方法在評(píng)價(jià)標(biāo)準(zhǔn)上的表現(xiàn)

5 結(jié)束語

本文提出了信息傳播中所存在的用戶轉(zhuǎn)發(fā)選擇問題，本文形式化了這一問題，并提出了一種用戶轉(zhuǎn)發(fā)選擇模型，用于對用戶的轉(zhuǎn)發(fā)選擇行為進(jìn)行預(yù)測。本文認(rèn)為用戶的轉(zhuǎn)發(fā)選擇行為主要由人際影響力導(dǎo)致，這種人際影響力同時(shí)取決于信息發(fā)送者的影響力和信息接受者的易感性。本文建模了用戶的隱影響力和易感性屬性，提出了用戶轉(zhuǎn)發(fā)選擇的FPM模型，并給出了高效的計(jì)算方式。該模型克服了目前存在工作中對轉(zhuǎn)發(fā)選擇行為的認(rèn)識(shí)不足，模型泛化能力差和依賴用戶傳播屬性獲取的問題。通過在真實(shí)的新浪微博數(shù)據(jù)實(shí)驗(yàn)，我們對模型的運(yùn)行參數(shù)和性能進(jìn)行了調(diào)整和驗(yàn)證。通過與其他典型的轉(zhuǎn)發(fā)選擇模型比較，所提的FPM模型在準(zhǔn)確率與MRR兩項(xiàng)評(píng)價(jià)指標(biāo)上均有顯著提高。實(shí)驗(yàn)結(jié)果證明了FPM的有效性，本文所提的FPM模型是一種較為準(zhǔn)確的對用戶轉(zhuǎn)發(fā)選擇行為進(jìn)行建模的方法。

[1] J Ugander, L Backstrom, C Marlow, et al. Structural diversity in social contagion[J]. Proceedings of the National Academy of Sciences, 2012, 109(16): 5962-5966.

[2] P Bao, H Shen, W Chen, et al. Cumulative effect in information diffusion: empirical study on a microblogging network[J]. PLoS ONE, 2013, 8(10): e76027.

[3] S Aral and D Walker. Identifying influential and susceptible members of social networks[J]. Science, 2012, 337 (6092): 337-341.

[4] J Leskovec, L A Adamic, and B A Huberman. The dynamics of viral marketing[J]. ACM Transactions on the Web (TWEB), 2007, 1(1): 5.

[5] J Huang, X Cheng, H Shen, et al. Exploring social influence via posterior effect of word-of-mouth recommendations[C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining. 2012: 573-582.

[6] A Barabási and R Albert. Emergence of scaling in random networks[J]. Science, 1999, 286 (5439): 509-512.

[7] P W Holland and S Leinhardt. Transitivity in structural models of small groups[J]. Comparative Group Studies, 1971.

[8] M Granovetter. The strength of weak ties[J]. American Journal of Sociology, 1973: 1360-1380.

[9] L C Freeman. A set of measures of centrality based on betweenness[J]. Sociometry, 1977: 35-41.

[10] L Katz. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43.

[11] P Bonacich. Power and centrality: A family of measures[J]. American Journal of Sociology, 1987: 1170-1182.

[12] J Tang, J Sun, C Wang, et al. Social influence analysis in large-scale networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009: 807-816.

[13] M Gomez Rodriguez, J Leskovec, and B Sch?l-kopf. Structure and dynamics of information pathways in online media[C]//Proceedings of the 6th ACM International Conference on Web Search and Data Mining. 2013: 23-32.

[14] S A Myers, C Zhu, and J Leskovec. Information diffusion and external influence in networks[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2012: 33-41.

[15] K Saito, K Ohara, Y Yamagishi, et al. Learning diffusion probability based on node attributes in social networks[C]//Foundations of Intelligent Systems. 2011: 153-162.

[16] P Cui, F Wang, S Liu, et al. Who should share what?: item-level social influence prediction for users and posts ranking[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2011: 185-194.

[17] Y Wang, H Shen, S Liu, et al. Learning influence and susceptibility from information cascades[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015: 477-483.

[18] D M Romero, B Meeder, J Kleinberg. Differences in the mechanics of information diffusion across topics: idioms, political hashtags, and complex contagion on twitter[C]//Proceedings of the 20th international conference on World Wide Web. 2011: 695-704.

[19] D Gruhl, R Guha, D Liben-Nowell, et al. Information diffusion through blogspace[C]//Proceedings of the 13th International Conference on World Wide Web. 2004: 491-501.

[20] J Leskovec, M Mcglohon, C Faloutsos, et al. Patterns of cascading behavior in large blog graphs[C]//Proceedings of SIAM International Conference on Data Mining. 2007: 551-556.

[21] R Crane, D Sornette. Robust dynamic classes revealed by measuring the response function of a social system[J]. Proceedings of the National Academy of Sciences, 2008, 105(41): 15649-15653.

[22] D Kempe, J Kleinberg, é 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. 2003: 137-146.

[23] K Train. Qualitative choice analysis: Theory, econometrics, and an application to automobile demand[M]. MIT Press, 1986.

[24] C J Lin. Projected gradient methods for nonnegative matrix factorization[J]. Neural Computation, 2007, 19(10): 2756-2779.

[25] E M Voorhees. The TREC-8 Question Answering Track Report[C]//Proceeding of TREC. 1999: 77-82.

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

[27] K Saito, R Nakano, and M Kimura. Prediction of information diffusion probabilities for independent cascade model[C]//Knowledge-Based Intelligent Information and Engineering Systems. 2008: 67-75.

Predicting Forwarding Preference in Information Propagation

WANG Yongqing, SHEN Huawei, CHENG Xueqi

(CAS Key Laboratory of Network Data Science & Technology,Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190,China)

In information propagation, users have forwarding preference when receiving same message repeatedly. Modeling forwarding preference is fundamental to information propagation and other related applications, e.g., influence analytics, cascade dynamics and social recommendation. In this paper, we suggest forwarding preference is mainly affected by interpersonal influence, determined by both influence and susceptibility from the sender and the receiver, respectively. We propose to model such user-specific latent influence and susceptibility by the Forwarding Preference Model. We compare our proposed model with state-of-the-art forwarding preference models on the dataset from Weibo, which demonstrates that the proposed model consistently outperforms other methods at two evaluation measures.

information propagation; forwarding preference; influence; susceptibility

王永慶(1986—)，博士研究生，主要研究領(lǐng)域?yàn)樯缃痪W(wǎng)絡(luò)分析、數(shù)據(jù)挖掘。E?mail：wangyongqing@software．ict．a(chǎn)c．cn沈華偉(1982—)，博士，副研究員，碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)科學(xué)、社交網(wǎng)絡(luò)分析、數(shù)據(jù)挖掘。E?mail：shenhuawei@ict．a(chǎn)c．cn程學(xué)旗(1971—)，博士，研究員，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)科學(xué)、網(wǎng)絡(luò)與信息安全、互聯(lián)網(wǎng)搜索與服務(wù)。E?mail：cxq@ict．a(chǎn)c．cn

1003-0077(2016)05-0057-08

2015-09-07 定稿日期： 2016-06-28

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(“973”計(jì)劃)(2014CB340401，2012CB316303)；國家自然科學(xué)基金(61472400，61232010，61202215)；北京市自然科學(xué)基金(4122077)

TP391

A