王永慶, 沈華偉, 程學旗
(中國科學院 計算技術研究所網絡數據科學與技術重量實驗室,北京 100190)
預測信息傳播中的轉發選擇
王永慶, 沈華偉, 程學旗
(中國科學院 計算技術研究所網絡數據科學與技術重量實驗室,北京 100190)
在信息傳播中,用戶在重復接收同一信息的情況下其轉發行為會具有一定的傾向性。對這種轉發的傾向性建模是影響力分析、傳播動力學、社會推薦等一系列信息傳播相關應用研究領域中的一個關鍵問題。本文假設用戶的轉發選擇行為主要由用戶間的人際影響力決定。人際影響力的大小由信息傳播者的影響力和信息接收者的易感性共同作用。本文從真實的信息傳播記錄中推斷出用戶隱式的影響力和易感性,進而提出了一種轉發選擇模型。該模型能夠有效解決目前方法存在的對轉發選擇行為建模不充分和模型泛化能力差的問題。本文選取典型的轉發選擇建模方法作為比較,將所提的轉發選擇模型在新浪微博數據上進行對比驗證。實驗表明,本文所提的模型在兩種評價指標上均取得更好效果,證明了所提模型的有效性。
信息傳播;轉發選擇;影響力;易感性
社會媒體(Social media)的誕生極大提高了人們獲取和傳遞信息的能力。例如通過博客、論壇、微博、百科等平臺,用戶利用互動式的交流和表達方式,使得信息經由用戶的社會關系有序傳播。在這種信息傳播中,社會媒體用戶能夠有較多機會通過其社交關系重復接收同一信息: 一方面加深用戶對該信息的認識使得用戶有更高的概率對該信息進行轉發;另一方面,用戶必須從多個信息源的轉發中做出轉發選擇。現有文獻表明,用戶的轉發選擇行為具有一定的傾向性。一般而言,這種轉發選擇行為被視作是人際影響力的直接體現[1- 2]。因此如何理解用戶在轉發選擇時的行為傾向,是研究人際影響力的切入點之一,建模并預測轉發選擇行為也是影響力分析[3]、傳播動力學[1, 4]、社會推薦[5]等一系列信息傳播相關應用研究領域中的一個關鍵問題。
現有嘗試對用戶人際影響力進行建模的方法可大致分為三類: 利用網絡結構,利用歷史傳播記錄信息和利用用戶傳播屬性的建模。利用網絡結構的影響力分析主要是從度分布(degree distribution)[6],聚集系數(clustering coefficient)[7],連接強度(tie strength)[8],介數(betweenness)[9],中心度度量(centrality)[10-11]等網絡的物理性質上進行討論。在利用歷史傳播記錄信息的影響力建模方面,Tang等人[12]提出了綜合主題模型(topic model)及傳播記錄的建模方式,在引文網絡中較好識別了各話題下的代表性人物及發表論文。Gomez等人[13]提出了基于生存模型的建模方法,該方法假設用戶在一次信息傳播的過程中,不斷地被周圍新“感染”的鄰居影響,直至最終轉發消息。Myers[14]等人提出了針對外部消息源影響力的建模方法,并較好擬合了信息傳播的爆發曲線。在利用用戶傳播屬性建模方面,Saito等人[15]提出了顯式的用戶屬性建模方法,估計用戶個體間的信息傳播概率,并預測信息的傳播發生情況。Cui等人[16]提出了隱式的用戶及文檔屬性建模方法,并用于推斷用戶對影響用戶的偏好以及用戶對內容的偏好問題。以上所述方法利用了對人際影響力的不同認識,部分解釋了信息傳播中的現象,但仍無法較好解決主要由人際影響力所導致的轉發選擇問題。所存在的主要問題有: 1)基于網絡分析的方法忽略了平臺本身的異質性,這類分析方法無法保證某一網絡的物理性質與存在傳播現象之間存在關聯的普適性,因果分析不夠準確; 2)基于歷史傳播記錄信息的建模方法目前還沒有較好泛化能力,只能就觀測節點對間的傳播情況進行推斷及預測,缺失大量節點對間的傳播記錄信息會使得該分類中的建模方式失效。3)大量的傳播及用戶數據以匿名化的方式存在,這使得顯式的用戶傳播屬性較難獲得。并且目前沒有較為系統的研究工作支持人際影響力與用戶傳播屬性之間的關系。
為了避免上述問題,有效建模信息傳播中用戶的轉發選擇行為,本文提出了轉發選擇模型(Forwarding-Preference Model,FPM)。FPM模型能夠對隱式的用戶傳播屬性進行建模,將用戶傳播屬性按照用戶在信息傳播中的傳播者及接收者角色分為影響力(influence)及易感性(susceptibility)屬性[17]。在信息傳播過程中,傳播者與接收者間的人際影響力由傳播者的影響力向量和接收者的易感性向量的內積確定。用戶的轉發選擇行為是信息接收者以較高概率選擇對其更具影響力的傳播者的選擇過程。目前而言,這種從人際影響力角度對轉發選擇行為的建模工作是一個較新的信息傳播應用問題。本文形式化了轉發選擇問題,并對該應用問題給出了一種建模求解的方法。FPM模型的優勢在于:
1) FPM模型有較好的泛化能力。所推斷隱式的用戶影響力與易感性屬性與用戶節點相關,與用戶間的連邊無關。對于缺失的節點對間的傳播記錄信息,其人際影響仍可通過節點與其他節點的歷史交互推斷獲得。
2) FPM模型是對人際影響力導致的用戶轉發選擇行為的直接建模,量化并推斷人際影響力。通過實際數據的驗證表明,本文所提模型與原有估計方法相比在評價指標上具有較大幅度的提升。表明了人際影響力與用戶轉發選擇行為之間存在相關性,并證實了所提模型的有效性。
3) 相比建模用戶顯式的傳播屬性,FPM模型所推斷的隱式用戶傳播屬性僅需歷史傳播記錄信息,受數據獲取的限制更少,這使得所提模型具有較好的適用性。
本文設計了迭代算法,通過所觀測的用戶轉發偏好,學習獲得用戶隱式的影響力及易感性屬性。在實驗部分,在新浪微博數據上對FPM模型及所選典型的比較方法進行評測。實驗結果表明,FPM模型能夠在本文所給定的兩個評價標準上均取得較為顯著的預測性能提升,模型對用戶轉發選擇行為的建模是有效的。
文章的后續部分組織如下: 第二章是相關工作的介紹;第三章形式化和建模用戶由人際影響力所產生的轉發選擇過程,給出FPM模型,并給出對應的學習算法。第四章對實驗數據、評價指標、對照方法以及比較結果進行介紹及說明。最后在第五章中給出本文的結論。
對用戶在信息傳播中的轉發選擇行為建模和推斷的工作是目前信息傳播領域一個新的應用研究問題。對該問題的認識,目前主要認為用戶在信息傳播中的轉發選擇行為主要由人際影響力所決定。大量的相關工作主要集中于用戶在信息傳播中的傳播動力學研究。
信息傳播動力學的相關實證研究工作利用統計規律發現信息傳播的相關因素和因果聯系。Romero等人[18]利用在Twitter上醫藥信息的傳播記錄發現,信息傳播相較于疾病傳播是一種更為復雜的傳播方式。與疾病傳播不同,用戶在同一信息下暴露多次時會產生明顯的邊際效應。Leskovec等人[4]研究了病毒式營銷市場的傳播動力學,揭示了信息傳播與其他傳播系統的不同,并初步探討了影響信息傳播的用戶屬性。Huang等人[5]通過豆瓣數據實證了用戶評價對其他用戶評分的影響,證明病毒式營銷市場中用戶之間影響力的確實存在。Gruhl等人[19]通過博客數據分別從宏觀的話題層次與微觀的用戶層次對信息傳播的動力學進行探討,并提出了基于宏觀與微觀層次的影響力模型。Leskovec[20]利用博客關系圖及圖上的傳播模式模擬博客空間中的信息傳播。Ugander等人[1]在Twitter數據中分析了傳播網絡的結構特征,揭示了傳播網絡的結構多樣性與信息傳播之間的聯系。Crane等人[21]度量了信息傳播中觸發評論行為的內源及外源因素。Bao等人[2]證實了信息傳播中的累積效應(cumulative effects),并利用傳播網絡的結構分析方法對用戶的轉發選擇進行了初步探索。Tang等人[12]結合話題與社會網絡,建模了話題相關的影響力模型,并在引文網絡中進行驗證。Aral等人[3]引入了影響力與易感性兩種傳播屬性的度量方式,利用Twitter數據對信息傳播中用戶傳播屬性的分布進行了實證研究。Cui等人[16]建模了文檔層次的人際影響力模型,提出了用戶與文檔的相關隱屬性向量。這些工作在一定程度上給予我們對信息傳播動力學的理解,啟發我們對轉發選擇行為的建模工作。


表 1 符號及對應描述


圖 1 (a)社會網絡;(b)三條消息的傳播記錄;(c)由(b)中所示傳播記錄所構建的三個傳播網絡;(d)根據所有傳播記錄綜合構建的傳播網絡。
根據傳播網絡的定義,在傳播網絡中,一個用戶的所有父親節點都是該用戶在某次信息傳播中潛在的影響者。對此我們定義如下:
在一次信息傳播中,用戶v影響鄰居集合內的所有節點都可能對用戶v造成影響,并促成用戶v對該信息進行轉發。基于信息傳播的一般假設[22]: 1)一個用戶對一條信息有且僅能產生一次有效轉發;2)當用戶轉發某信息時,其轉發行為能夠立即被網絡中其他關聯用戶感知并造成影響;3)一個用戶在一次信息傳播中,有且僅能影響某一可能被其影響的用戶一次。根據信息傳播的一般假設,我們定義真實影響鄰居集合如下:
定義2 真實影響鄰居集合。關于信息m的一次信息傳播,用戶v的真實影響鄰居集合

根據以上的符號及定義,本文采用離散選擇模型(discrete choice model)[23]建模用戶在轉發信息m時所作的選擇行為,其形式化如下:


圖2 FPM的概率圖模型
假設用戶間的轉發選擇過程相互獨立,信息m傳播中所有的轉發選擇過程可以建立其概率似然分布如下:
進一步地,假設各信息的傳播獨立。則在所有的信息傳播C中,用戶轉發選擇行為的概率似然分布可以表示為
求解目標是獲得用戶的屬性矩陣I和S,使得等式在觀測數據下獲得最大似然。為了方便求解,本文將優化目標取負對數形式化為:
這里采用投影梯度法(Projected Gradient)[24]對公式進行求解優化。梯度的計算如下:

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

算法1 參數估計輸入:給定時間內的傳播記錄,最大迭代步R輸出:用戶的影響力屬性矩陣I和易感性屬性矩陣S1.通過傳播記錄構建傳播網絡;2.隨機初始化參數矩陣I,S;3.repeat4. fori=1tondo5. 計算?L/?Iu和?L/?Sv6. endfor7. 更新I和S8.until最大迭代步完成
本節將通過新浪微博數據對本文所提模型進行驗證。首先,詳細介紹所采用數據集的格式,抽取方法及訓練、測試集的設定。接著引入兩種評價方法對轉發選擇的預測結果進行評價,并討論分析FPM模型中各參數對模型結果的影響。最后,選取幾種較為典型的轉發選擇模型,通過與這些典型的轉發選擇模型比較,驗證FPM模型的有效性。
4.1 數據集
實驗數據集來自新浪微博,該數據集由WISE 2012 Challenge*http://www.wise2012.cs.ucy.ac.cy/challenge.html發布提供。數據集抓取了新浪微博從2009年9月17日至2012年2月17日的所有傳播記錄。本文選擇其中2011年1月1日至2月15日的傳播記錄進行實驗,將所抽取的數據按時間切分為三個等長的片段,分別記作數據集D1,D2,D3。去除了沒有同時出現于三個切分片段數據上的用戶及其對應傳播記錄,以保證在實驗中所有用戶的轉發選擇在一個閉集內。在實際傳播過程中,存在用戶僅在某信息下暴露一次就轉發的實例。在這種情況下,真實影響鄰居的集合大小為1,不需要對其進行轉發選擇行為的預測。因此本文的樣本僅保留用戶在某一信息下多次暴露的情況。實驗采用交叉驗證的方式共進行三組,所得的三個模型分別記作M1,M2,M3。交叉驗證的策略如下: 第一輪R1在數據D1上訓練獲得模型M1,在數據D2和D3上進行測試;第二輪R2在數據D2上訓練獲得模型M2,在數據D1和D3上進行測試;第一輪R3在數據D3上訓練獲得模型M3,在數據D1和D2上進行測試;數據集的基本統計信息見表 2。

表 2 數據集的基本統計信息
4.2 評價標準
本文引入了兩種評價標準用于判斷模型對預測用戶轉發選擇行為的準確度度量。
準確率: 準確率度量用于判斷模型是否準確判斷了用戶的轉發選擇,計算其在總體預測樣本上的準確率。其形式如下:
模型在準確率上的值越大,則模型的預測效果越好。
MRR (序值倒數的平均Mean Reciprocal Rank): MRR[25]是一種在信息檢索領域中較為常見的統計測量方法,主要用于度量在排序中真實的首位元素在預測排序中的正確程度。MRR的具體定義如下:

4.3 參數設置
為了能夠讓FPM模型取得較好的結果,本文設計了一系列實驗對FPM模型參數進行調整。FPM所需要調整的主要參數包括了隱用戶影響力與易感性屬性維度和算法最大迭代步數。
隱用戶影響力與易感性屬性維度d: 用戶的影響力與易感性屬性維度d與FPM模型的表達能力直接相關,但是過高的維度同時會導致模型的過高的優化代價。因此需要對維度d的大小進行討論,設置一個較為合適的維度值用于FPM模型。在實驗過程中,本文取d=5,10,15,20,25,30,35,40,分別進行了測試。
圖 3(a)展示了實驗結果,由于訓練數據分布于三個不同的傳播時間區間,因此其傳播表現存在一定的區分,這導致了所示曲線的差異。可以發現在三個模型關于維度d的調整中,均呈現維度與評價指標的正相關性,即維度越高FPM模型的預測性能在準確率和MRR兩個度量指標上的結果更好。實驗結果與本文的認識保持一致: FPM的表達能力提高能夠明顯改善模型的預測效果。考慮計算復雜度與效率的平衡問題,三個模型中同時取d=40。

圖3 FPM模型的參數設置
迭代步數R: 本文采用最大迭代步作為投影梯度法的收斂策略(其他的收斂策略見文獻[24])。為了提高算法的運行效率,需要設置一個較為合理的最大迭代步。如圖3(b)所示,三個模型在算法迭代到50次左右時都取得了較為良好的收斂效果。為了保證算法收斂,本文在三個模型中同時取最大迭代步R為100。
4.4 比較方法
為了評價FPM模型的有效性,本文引入了幾種典型的轉發選擇模型進行比較:
1) 偏好模型(Preference Attachment Model,PAM)[6]。偏好模型是經典的網絡生長模型,該模型認為網絡中新加入的節點容易與節點度較高的節點產生鏈接。這里本文將其應用于信息傳播中,假設用戶容易與傳播網絡中節點度較高的節點發生轉發行為。
2) 伯努利分布模型(Bernoulli Distribution Model,BDM)[26]。伯努利分布模型認為用戶間的轉發概率服從伯努利分布,該分布可以從歷史傳播記錄中通過最大似然方法統計獲得。用戶的轉發選擇過程容易發生在具有較高轉發概率的用戶節點對之間。
3) 杰卡德系數模型(Jaccard Index Model,JIM)[26]。不同于伯努利模型,杰卡德系數模型認為用戶間的轉發概率服從杰卡德系數,該分布可以從歷史傳播記錄中通過杰卡德系數的計算獲得。用戶的轉發選擇過程容易發生在具有較高轉發概率的用戶節點對之間。
4) 最大期望模型(EM Model,EMM)[27]。最大期望模型利用EM方法根據歷史傳播記錄估計用戶間的轉發概率。用戶的轉發選擇過程容易發生在具有較高轉發概率的用戶節點對之間。
5) 轉發第一消息源策略(Forward First Strategy,FRS)。這種轉發策略認為用戶會從其真實影響鄰居中轉發最早發布該消息的用戶。
6) 轉發最末消息源策略(Forward Last Strategy,FLS)。這種轉發策略認為用戶會從其真實影響鄰居中轉發最近發布該消息的用戶。
7) 任意轉發策略(Forward Randomly Strategy,FRS)。這種轉發策略認為用戶會從其真實影響鄰居中隨機轉發發布該消息用戶。
4.5 比較結果
根據前述的實驗方法,本文將FPM模型與選用的典型轉發選擇模型在真實數據集上進行比較,并通過兩種評價指標進行了結果展示,實驗結果列于表 4中。由于FRS,FLS,FRS策略僅考慮被轉發用戶,因此無法計算MRR值,表中對應部分空缺。從表中可以明顯地發現,本文所提的FPM模型,在預測的準確率和MRR兩項評價標準上均明顯優于其他方法,特別是在準確率的度量上,顯著高于次優的比較方法。這是因為FPM模型能夠有效解決目前存在方法泛化能力不足的問題。將三個切分數據集所構成的傳播網絡進行對照發現,接近70%的網絡連邊在對照網絡中沒有出現,而典型的轉發選擇模型在處理這些情況時,其預測效果接近隨機猜測。另外,FPM模型的結果同時也驗證了對用戶轉發選擇行為建模的有效性: 用戶的轉發選擇行為主要取決于人際影響力,本文所提的FPM模型是對人際影響力的一種較為準確的建模方法。

表4 PFM與比較方法在評價標準上的表現
本文提出了信息傳播中所存在的用戶轉發選擇問題,本文形式化了這一問題,并提出了一種用戶轉發選擇模型,用于對用戶的轉發選擇行為進行預測。本文認為用戶的轉發選擇行為主要由人際影響力導致,這種人際影響力同時取決于信息發送者的影響力和信息接受者的易感性。本文建模了用戶的隱影響力和易感性屬性,提出了用戶轉發選擇的FPM模型,并給出了高效的計算方式。該模型克服了目前存在工作中對轉發選擇行為的認識不足,模型泛化能力差和依賴用戶傳播屬性獲取的問題。通過在真實的新浪微博數據實驗,我們對模型的運行參數和性能進行了調整和驗證。通過與其他典型的轉發選擇模型比較,所提的FPM模型在準確率與MRR兩項評價指標上均有顯著提高。實驗結果證明了FPM的有效性,本文所提的FPM模型是一種較為準確的對用戶轉發選擇行為進行建模的方法。
[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—),博士研究生,主要研究領域為社交網絡分析、數據挖掘。E?mail:wangyongqing@software.ict.ac.cn沈華偉(1982—),博士,副研究員,碩士生導師,主要研究領域為網絡科學、社交網絡分析、數據挖掘。E?mail:shenhuawei@ict.ac.cn程學旗(1971—),博士,研究員,博士生導師,主要研究領域為網絡科學、網絡與信息安全、互聯網搜索與服務。E?mail:cxq@ict.ac.cn
1003-0077(2016)05-0057-08
2015-09-07 定稿日期: 2016-06-28
國家重點基礎研究發展計劃(“973”計劃)(2014CB340401,2012CB316303);國家自然科學基金(61472400,61232010,61202215);北京市自然科學基金(4122077)
TP391
A