基于傳播模擬的消息流行度預測

萬圣賢，郭嘉豐，蘭艷艷，程學旗

（1.中國科學院 計算技術研究所，北京100190；2.中國科學院大學，北京100190）

1 引言

近年來，在線社交網(wǎng)絡快速發(fā)展，已經(jīng)逐漸成為人們發(fā)布和獲取信息的主要平臺之一，這也為研究社會網(wǎng)絡的人們提供了良好的實驗平臺。在較為流行的微博客網(wǎng)站（Twitter，新浪微博等）中，每個用戶可以一次性發(fā)布不多于140字的消息，同時，用戶可以使用follow的方式訂閱其他用戶發(fā)布或分享的消息并從其訂閱的消息中選擇一部分分享給其follower。正是由于這種遞歸的口口相傳（word of mouth）的分享行為，一個用戶發(fā)布的消息可能傳播到整個網(wǎng)絡，從而使得社交網(wǎng)絡成為有效的消息傳播途徑。

社交網(wǎng)絡上每天新產(chǎn)生數(shù)以億計的消息，這些消息的流行度具有很大的差別［1］。如果能夠準確預測一條消息的流行度，將對于信息推薦、病毒式營銷以及網(wǎng)絡輿情預警等應用有著重要的意義。一種常用的消息流行度的定義是消息的被轉發(fā)（分享）次數(shù)，所以消息流行度可以認為是用戶轉發(fā)行為的累積效應。然而消息的傳播是用戶和用戶，用戶和消息之間相互作用的結果，影響用戶轉發(fā)行為的因素非常復雜，這使得消息流行度預測成為一個非常困難的問題［2］。本文中，我們嘗試用一種新的思路來解決這個問題，我們使用機器學習的方法將可能影響用戶轉發(fā)行為的因素融合在一起，得到用戶接收消息后的轉發(fā)概率，并結合經(jīng)典的傳播模型在真實的社會網(wǎng)絡中對消息的傳播進行模擬，從而完成消息流行度的預測。我們在Twitter數(shù)據(jù)集上進行了實驗，結果表明，相對于傳統(tǒng)的分類方法（logistic regression），我們的方法取得了更高的準確度和穩(wěn)定性。

本文的主要貢獻是提出了一種通過學習用戶轉發(fā)行為并結合傳播模型模擬消息傳播過程從而進行消息流行度預測的方法。和之前方法的不同點在于，我們基于特定的傳播模型使用機器學習的方法學習消息傳播的微觀性質(zhì)，并將微觀性質(zhì)應用于模擬消息傳播的宏觀涌現(xiàn)，從而更充分的利用了社會網(wǎng)絡的結構和用戶特征信息并取得了更好的預測效果。

2 相關工作

關于社交網(wǎng)絡上消息傳播機制和消息流行度預測問題目前已經(jīng)有很多研究工作，一部分工作側重于分析消息傳播的宏觀性質(zhì)，例如，消息轉發(fā)數(shù)的增長模式、消息傳播與網(wǎng)絡結構的關系以及影響傳播的用戶和消息特征等，并建立模型來模擬和預測消息流行度的增長曲線［1－3］或直接使用機器學習的方法預測消息的最終流行度［4－5］；另一部分工作側重于分析影響消息傳播的微觀性質(zhì)，主要集中于用戶轉發(fā)行為的分析和預測［6－7］。

Suh［8］等人對可能影響轉發(fā)行為的特征做了大量的統(tǒng)計分析，發(fā)現(xiàn)消息內(nèi)容、用戶度分布等特征對轉發(fā)行為有一定影響。Hong［5］等人將消息流行度預測問題形式化為分類問題，并使用logistic regression分別對消息是否被轉發(fā)和消息轉發(fā)次數(shù)兩個目標進行了預測。Bakshy［4］等人使用URL的流行度度量用戶的影響力，并使用回歸樹模型（regression tree model）對其進行預測，根據(jù)實驗結果，Bakshy認為針對特定用戶或URL的流行度預測是不可靠的。Lerman［2］等人對digg.com上的用戶瀏覽行為進行建模，提出了一個模擬用戶瀏覽行為的隨機模型，并利用消息的初始傳播信息來預測消息的最終流行度。然而，這些基于宏觀角度的流行度預測方法沒有能夠充分考慮消息傳播的微觀過程。

作為微博上消息傳播的主要方式，轉發(fā)（retweet）行為的分析和預測是人們關注的熱點之一。Yang［6］等人使用半監(jiān)督學習的方式預測特定用戶是否會轉發(fā)一條消息。Galuba［7］等人同樣對用戶的轉發(fā)行為建立概率模型并進行預測。然而，這些工作主要關注轉發(fā)行為預測結果的準確率和召回率，并沒有嘗試預測消息的流行度，這些方法也不能直接應用于消息流行度預測。

3 傳播模型

在許多在線社交網(wǎng)絡尤其是微博客上，用戶的轉發(fā)行為是消息傳播的主要途徑。用戶從其follow的用戶（followee）那里接收消息，并從其接收到的消息中選擇一部分轉發(fā)給其所有的follower，從而形成傳播級聯(lián)（cascade）。

我們記社會網(wǎng)絡為有向圖G（V，E），其中V為節(jié)點集合，也就是所有用戶集合，E為有向邊集合，也就是用戶關系集合。定義fd（u）為用戶u的followee集合，fl（u）為用戶u的follower集合。在常見的傳播模型中，每個節(jié)點通常具有兩種狀態(tài)，激活和未激活狀態(tài)，初始時V中大部分節(jié)點為未激活狀態(tài)，消息從已經(jīng)被激活的節(jié)點開始傳播，根據(jù)不同的假設，主要包括以下兩種傳播模型［9］。

1.線性閾值模型（linear threshold model，LT模型）。LT模型假設用戶u的每個followee v對該用戶u有一定的影響力buv。每個用戶u有隨機的被激活閾值θu，傳播的每一步中，假設fd（u）中當前被激活的所有用戶為active＿fd（u），那么如果則用戶u被激活。激活了的用戶u會在傳播的下一步中對fl（u）中節(jié)點的狀態(tài)產(chǎn)生影響，直到?jīng)]有新的節(jié)點被激活為止。

2.獨立級聯(lián)模型（independent cascade model，IC模型）。IC模型假設每個節(jié)點u以概率puv獨立的受到其followee節(jié)點v的影響。如果節(jié)點v在某一步t被激活，在t＋1步中，v有一次以概率puv激活節(jié)點u的機會，直到?jīng)]有新的節(jié)點被激活為止。

在微博客的消息傳播場景中，由于“RT＠”等標記的存在，我們明確的知道當前轉發(fā)用戶是受到哪個上層用戶的影響而轉發(fā)，可以較為直接的使用概率模型學習轉發(fā)概率。另外，LT模型中用戶被激活的概率隨著其followee的激活線性增長，然而在微博客中，除了用戶和用戶之間的影響力，消息內(nèi)容對轉發(fā)行為有很大的影響，同一內(nèi)容對同一用戶的多次曝光起到的邊際效用往往是衰減的，Ler－man［10］等人對Digg數(shù)據(jù)的分析也證明了這一點。所以，我們使用IC模型進行傳播模擬。

此外，經(jīng)典的IC模型中，用戶只有一次被激活的機會，然而在消息的轉發(fā)行為中，同一用戶可能多次轉發(fā)同一消息，用戶的多次轉發(fā)會增加其follower看到消息的概率從而增加其follower的轉發(fā)概率，最終對后續(xù)的傳播過程帶來影響。所以，在我們的場景中我們使用經(jīng)典IC模型的變體，允許用戶被多次激活，并且用戶的每次激活都會嘗試激活其所有的follower。

在IC模型中，任意一條有向邊（follow關系）（u→v）上都存在激活概率puv。IC模型本身并沒有指定如何獲取這些概率參數(shù)，不同的應用場景中存在不同的參數(shù)估計方法。在本文的消息傳播場景中，對于同一條有向邊（u→v），不同消息的轉發(fā)概率存在較大差別，所以我們需要考慮消息本身的因素，也就是說我們需要獲取的參數(shù)是puvm，其中，m表示一條特定消息。

4 轉發(fā)概率學習

本節(jié)中我們具體討論IC模型中轉發(fā)概率的學習，包括正負例選取、概率模型以及特征選擇。

4.1 正負例選取

為了學習轉發(fā)概率，首先我們需要找出用于學習的正例和負例。我們結合具體的消息傳播過程進行說明。圖1是微博客中消息傳播的示意圖。圖中的每一棵樹表示一條消息的傳播過程，樹的根節(jié)點表示消息的發(fā)布者，樹中的有向邊表示消息的傳播方向，也就是從消息的發(fā)布者或者轉發(fā)者（傳播者）指向其所有的follower。樹中所有的節(jié)點都是該消息的接收者，其中黑色節(jié)點表示發(fā)布者或者轉發(fā)者，用戶的每一次轉發(fā)都會引入新的接收者（除非該用戶的follower數(shù)為0），所以，樹中的所有葉子節(jié)點用戶接收到消息但沒有轉發(fā)，所有內(nèi)部節(jié)點用戶接收到消息并進行轉發(fā)。需要注意的是，因為存在同一用戶多次接收或者多次轉發(fā)同一條消息的情況，這里的傳播樹并不等同于消息在用戶關系圖上傳播形成的子圖，多次接收或多次轉發(fā)同一條消息的用戶在樹中對應多個不同節(jié)點。

我們選擇所有消息傳播樹中的非葉子節(jié)點（接收并且轉發(fā)的用戶）作為正例，所有葉子節(jié)點（接收但不轉發(fā)的用戶）作為負例。這種正負例的選擇方式和修改后的IC模型吻合，否則，學習得到的概率會存在系統(tǒng)偏差。為了便于說明，我們還定義如下概念。

圖1 消息傳播示意圖

原始用戶：表示消息的原始作者，也就是樹中根節(jié)點表示的用戶，例如，na；

上層用戶：表示一個消息接收者從誰那里接收該消息，也就是樹中節(jié)點的父節(jié)點，例如，用戶na是nb的上層用戶，nc是nd的上層用戶。類似的，還可以定義原始消息和上層消息。

4.2 模型與特征

我們使用最大熵模型［11］學習用戶接收到消息后進行轉發(fā)的概率。最大熵原理是概率模型學習的一個準則，就是在所有可能的模型中選擇熵最大的模型。最大熵模型是對數(shù)線性模型（log linear model）的一種，可以用于學習不同特征下不同輸出的概率。

我們認為Twitter上的轉發(fā)行為主要是由當前用戶對原始消息的信任度和興趣度，上層用戶對當前用戶的影響力以及當前用戶的活躍度三個因素決定?；谶@一認識，我們在模型訓練時使用了以下特征。

1.用戶特征

用戶特征包括用戶的follower數(shù)，用戶的followee數(shù)，用戶歷史發(fā)帖活躍度，用戶歷史轉帖活躍度，用戶歷史被轉發(fā)數(shù)，用戶對用戶歷史轉發(fā)數(shù)，當前用戶和上層用戶是否互相follow。在我們的傳播過程中存在三種用戶（當前用戶，上層用戶和原始用戶），上述用戶特征中，除后兩個之外，都對這三種用戶分別提取。后兩個特征針對當前用戶和上層用戶提取。

2.消息內(nèi)容特征

消息內(nèi)容特征包括內(nèi)容長度，內(nèi)容是否包含hashtag，內(nèi)容是否包含URL，消息的話題分布。

3.消息早期傳播特征

消息早期傳播特征包括消息從發(fā)布到被第5次轉發(fā)經(jīng)歷的時間，消息發(fā)布后5分鐘內(nèi)的總轉發(fā)數(shù)。

4.其他特征

其他特征包括原始消息的發(fā)布時間，上層消息的傳播路徑長度。

5 實驗

5.1 數(shù)據(jù)預處理

我們使用Twitter API采集了Twitter上2011年12月16日到12月30日之間（兩周）的部分數(shù)據(jù)，數(shù)據(jù)內(nèi)容包括Twitter用戶信息，Twitter用戶構成的關系網(wǎng)絡以及這些Twitter用戶這兩周內(nèi)發(fā)布的所有消息。數(shù)據(jù)的總體情況見表1。

表1 Twitter數(shù)據(jù)信息

Twitter API返回的結果中包含每條消息是否為轉發(fā)消息，如果是轉發(fā)消息還返回其上層消息的ID，然而，Twitter用戶也可以手動添加“RT＠”等標記或者使用第三方應用進行消息轉發(fā)，這些轉發(fā)消息的上層消息ID是無法通過API直接獲取的，我們解析轉發(fā)消息內(nèi)容中包含的“RT＠”等標記，尋找上層用戶并從上層用戶的發(fā)布消息列表中找到該轉發(fā)消息的上層消息。獲取了每條轉發(fā)消息的上層消息之后，我們沿著消息的傳播路徑回溯，得到每條轉發(fā)消息的原始消息，如果轉發(fā)路徑中有間斷，則找不到原始消息，我們根據(jù)是否包含“RT＠”等標記判斷一條消息是否為原始消息。這樣，我們可以為每一條原始消息構建其傳播樹，我們?nèi)コ艮D發(fā)次數(shù)小于5的原始消息，最終總共找到1 131條原始消息。圖2是消息轉發(fā)數(shù)的分布圖，服從冪律分布。然而，我們采集到的Twitter用戶并不是非?；钴S，消息最多轉發(fā)次數(shù)只有不到200次。我們?nèi)〉谝恢艿脑枷⒆鳛橛柧毤?，第二周的原始消息作為測試集。

5.2 Baseline

圖2 消息轉發(fā)次數(shù)分布圖

我們選擇 Hong［5］等人使用的logistic regression方法進行對比，這種分類方法直接根據(jù)原始消息的特征判斷消息的流行度類別。由于這種方法不涉及到傳播過程，所以我們提取特征的時候僅提取了跟原始消息相關的特征，包括原始用戶特征、所有的消息內(nèi)容特征、消息早期傳播特征以及消息發(fā)布時間特征。

我們將原始消息根據(jù)最終轉發(fā)數(shù)分為不同類別，由于轉發(fā)數(shù)是服從冪律分布的，如圖2所示，我們根據(jù)圖2中橫坐標刻度為2.5和3.5的地方將消息分為3個類別，用類別0，1，2表示。我們使用了多種評價指標對結果進行評價。

5.3 實驗結果

為了測試特征的區(qū)分度，我們首先將最大熵模型用于二分類問題，判斷給定用戶接收到一條消息后是否會進行轉發(fā)。由于正例的數(shù)量遠遠小于負例的數(shù)量，我們從負例集合中隨機采樣了和正例數(shù)量相等的負例用于訓練和測試，在測試集上的分類精度為84.24%?？梢姡覀兲崛〉奶卣骶哂休^好的區(qū)分度，可以進一步應用于轉發(fā)概率的學習。

在傳播模擬過程中，我們并不是直接判斷用戶是否轉發(fā)，而是學習用戶轉發(fā)的概率，然后使用IC模型基于真實的社會網(wǎng)絡進行傳播模擬。為了保證與真實概率的一致性，訓練最大熵模型時，我們使用了訓練集中所有的正例和負例。我們對每條消息模擬10次，并取10次模擬的平均結果作為最終的預測轉發(fā)數(shù)。表2中列出了傳播模擬和logistic regression（LR）兩種方法預測結果的混淆矩陣，其中，每一行表示一個真實類別中的元素在兩種分類方法下被分到各個預測類別的數(shù)目。

進一步地，我們使用準確率，召回率和F－measure對各個類別上的分類結果進行評價，評價結果見表3。

表2 分類結果的混淆矩陣

從實驗結果中我們可以看出，我們的方法在準確率上一致地優(yōu)于logistic regression方法，尤其是在第1，2類這些轉發(fā)較多的消息類別上。在召回率上，我們的方法在第1類上取得了相對較好的效果，然而在第2類上效果欠佳。最后，我們分別使用微平均（micro－averaging）和宏平均（macro－averaging）方法計算F－measure。相對于微平均，宏平均能更好地處理類別間數(shù)據(jù)量不平衡帶來的問題，所以更加適用于我們的場景。從結果中可以看出，不管是微平均還是宏平均，我們的方法總體上都優(yōu)于logistic regression方法，尤其是宏平均，我們的方法顯著優(yōu)于logistic regression方法。

表3 分類評價指標結果

此外，由于這3種類別之間存在順序關系（ordinal），第0類＜第1類＜第2類，簡單的使用準確率和召回率并不合適，比如如果將真正屬于第0類的消息誤分到第2類應該比誤分到第1類帶來的損失更大。所以，我們再使用MSE（mean squared error）對結果進行評價，如表4所示。

表4 評價指標MSE的結果

我們的結果在MSE指標下同樣一致地優(yōu)于logistic regression方法，值得注意的是，我們的方法雖然在第2類的召回率和F－measure上比logistic regression差一些，但是在MSE上表現(xiàn)更好，說明我們的方法更加穩(wěn)定，也就是說分類錯誤的消息不會離真實類別偏差太遠。

然而，不管是使用logistic regression的方法還是傳播模擬的方法，都沒能精確的預測出一條消息的流行度，尤其是流行度較高的消息，召回率都比較低。這也再次說明了，影響消息流行度的因素很多，對其進行精確預測是很困難的。

Salganik［12］等人的實驗表明，流行度受到早期傳播的偶然性因素影響很大，很多消息流行度預測方法利用消息流行度的前期趨勢進行預測。所以，我們也統(tǒng)計了Twitter數(shù)據(jù)中早期流行度和最終流行度之間的關聯(lián)關系。從圖3中擬合的曲線可以看出，消息的早期流行度和最終流行度的確是存在正相關關系的，然而對于具體的消息，這種相關關系卻差別很大，這也給預測增加了難度。

總的來說，由于我們的方法融合了大量的特征并且在真實的社會網(wǎng)絡上進行傳播模擬，所以更充分的利用了社會網(wǎng)絡的結構和用戶特征信息，從而能夠更加準確穩(wěn)定的進行消息流行度預測。

然而我們的方法也存在一些問題，多次傳播模擬結果的平均使得預測結果的分布更加平滑，另外，學習微觀轉發(fā)概率時的目標和預測消息流行度的目標之間存在差別，這使得預測的結果和真實數(shù)據(jù)的分布之間存在差別，所以我們的結果中分到第2類的消息較少，而且這些消息雖然正確被分類，但是預測的流行度比真實流行度偏小。

圖3 消息最終流行度排名與前5分鐘轉發(fā)次數(shù)

6 總結和未來工作

本文提出了一種基于傳播模擬的消息流行度預測方法，首先使用最大熵模型學習用戶接收消息后進行轉發(fā)的概率，然后使用IC模型對消息的傳播進行模擬來預測消息的流行度。這種方法能夠更充分的利用網(wǎng)絡結構和用戶特征信息，所以我們的方法取得了更好的結果，在準確率方面一致地優(yōu)于logistic regression方法，并具有較高的穩(wěn)定性。

然而，我們的工作中還存在一些問題，預測結果的分布和真實分布存在差別。另外，時間因素也是影響用戶轉發(fā)行為的重要因素，目前我們并沒有對用戶轉發(fā)的時間進行建模，只是使用了傳播層次來近似這一效果。在未來的工作中，我們會嘗試解決這些問題。

［1］Wu F，Huberman B A.Novelty and collective attention［J］.National Academy of Sciences，2007，104（45）：17599.

［2］Lerman K，Hogg T.Using a model of social dynamics to predict popularity of news［C］／／Proceedings of the ACM，USA，2010：621－630.

［3］Szabo G，Huberman B A.Predicting the popularity of online content ［J］.Communications of the ACM，2010，53（8）：80－88.

［4］Bakshy E， Hofman J M， Mason W A，et al.Everyone's an influencer：quantifying influence on twitter［C］／／Proceedings of the ACM，HK，2011：65－74.

［5］Hong L，Dan O，Davison B D.Predicting popular messages in twitter［C］／／Proceedings of the ACM，2011：57－58.

［6］Yang Z，Guo J，Cai K，et al.Understanding retweeting behaviors in social networks［C］／／Proceedings of the 19th ACM CIKM.Canada，2010：1633－1636.

［7］Galuba W，Aberer K，Chakraborty D，et al.Outtweeting the twitterers－predicting information cascades in microblogs［C］／／Proceedings of the 3rd conference on Online social networks.USA：USENIX Association，2010：3－3.

［8］Suh B，Hong L，Pirolli P，et al.Want to be retweeted？Large scale analytics on factors impacting retweet in Twitter network［C］／／Proceedings of the Social－Com.USA：IEEE，2010：177－184.

［9］Kempe D，Kleinberg J，Tardos Maximizing the spread of influence through a social network［C］／／Proceedings of the ninth ACM SIGKDD.USA，2003：137－146.

［10］Ver S G，Ghosh R，Lerman K.What stops social epidemics［C］／／Proceedings of the Fifth International AAAI Conference on Weblogs and Social Media.USA，2011：377－384.

［11］Berger A L，Pietra V J D，Pietra S A D.A maximum entropy approach to natural language processing［J］.Computational linguistics，1996，22（1）：39－71.

［12］Salganik M J，Dodds P S，Watts D J.Experimental study of inequality and unpredictability in an artificial cultural market［J］.Science，2006，311（5762）：854－856.

［13］Kwak H，Lee C，Park H，et al.What is Twitter，a social network or a news media？［C］／／Proceedings of the 19th ACM，USA，2010：591－600.

［14］Wu S，Hofman J M，Mason W A，et al.Who says what to whom on twitter［C］／／Proceedings of the 20th ACM，USA，2011：705－714.