微博背后的那些算法_數(shù)據(jù)分析師

引言

微博是一個很多人都在用的社交應用。天天刷微博的人每天都會進行著這樣幾個操作：原創(chuàng)、轉發(fā)、回復、閱讀、關注、@等。其中，前四個是針對短博文，最后的關注和@則針對的是用戶之間的關系，關注某個人就意味著你成為他的粉絲，而他成為你的好友；@某個人意味著你想要他看到你的微博信息。

微博被人們認為是“自媒體”，即普通大眾分享與本身相關的“新聞”的途徑。最近，有些人使用自己在自媒體上的影響力而盈利的報道屢見不鮮。那微博上個人影響力是怎樣計算的呢？微博上還有哪些算法作為看不見的手在管理著我們？我們的每一個行為怎樣影響著算法呢？

直觀上看，微博其實是人類社會的一個簡單的縮影，微博網(wǎng)絡的一些特點，也許可以啟發(fā)我們得到真實的社會網(wǎng)絡上的規(guī)律。得益于社交網(wǎng)絡的爆發(fā)式發(fā)展，“社會計算”尤其是社交網(wǎng)絡分析成為數(shù)據(jù)挖掘的新寵兒。下面我們就針對微博網(wǎng)絡分析的一些算法進行簡單的介紹，其中的有些算法對于其他的社交應用可能也適用。

標簽傳播

微博用戶量浩大，不同的人有不同的興趣。挖掘每個用戶的興趣有助于更加精準的廣告投放、內容推薦。為了得到每個用戶的興趣，可以為用戶打上標簽，每個標簽代表用戶的一個興趣，用戶可以擁有一個或多個標簽。為了得到最終的用戶標簽，先做第一個假設：

每個用戶的好友(或粉絲)中與該用戶具有相同興趣的人占多數(shù)。

這就引出了本文介紹的第一個算法，即標簽傳播算法。在這個算法中，每個用戶的標簽取其好友或粉絲中標簽最多的一個或多個。當然，可以將好友和粉絲的標簽都考慮進來，整合的時候可以考慮賦予好友的標簽和粉絲的標簽不同的權重。標簽傳播算法的過程如下：

1)對一部分用戶給出初始標簽；

2)對每一個用戶，統(tǒng)計其好友和粉絲的標簽數(shù)目，賦予該用戶出現(xiàn)次數(shù)最多的一個或者多個標簽。

3)循環(huán)進行第2步，直到用戶的標簽不再發(fā)生大的變化為止。

用戶相似度計算

標簽傳播算法實現(xiàn)起來比較簡單，其缺點在于當所做的假設不符合事實時，比如為了社交上的禮貌，我們一般會把自己的親友添加關注，這些人不一定和我們擁有同樣的標簽；該算法的結果就會變得很差。解決的辦法就是通過計算用戶之間的相似度來衡量好友或粉絲的標簽對用戶標簽的貢獻率。因而得到第二個假設：

與用戶越相似的好友或粉絲，其標簽越可能是用戶的標簽。

那么，如何衡量用戶之間的相似度呢？這就需要考慮到用戶發(fā)表的微博信息了，包括轉發(fā)的和原創(chuàng)的。這里是要考慮用戶之間的相似度而不是用戶微博之間的相似度，因而在實際計算時，將某個用戶的所有微博信息聚集到一起進行計算。一個可選的方法是使用詞袋法將微博信息表示成詞語向量，然后直接使用余弦方法等計算其相似度。但這個方法太過簡單，不容易達到好的結果，這里介紹一種基于LDA（隱含狄利克雷分布）的相似度計算方法。

LDA仍然使用詞袋法表示文本，但是在中間添加了一個主題層，形成了“文檔-主題-詞語”三層概率模型，即每篇文檔看成是主題的一種概率分布，主題又被看成是單詞的概率分布。在LDA模型下，文檔可以被看成按照如下方式生成：

1)對于每篇文檔：

2)從主題分布中抽取一個主題；

3)從該主題的詞語分布中抽取一個詞語；

4)重復第2步和第3步，直到該文檔的所有詞語都生成。

LDA模型參數(shù)的估計算法不在本文的討論范圍之內。這里只需要知道，通過LDA可以得到每個用戶的微博信息的主題分布。然后使用余弦方法、KL距離等計算相似度的方法來得到用戶間主題分布的相似度，以之作為用戶之間的相似度。而后使用該相似度對標簽傳播進行加權。

時間因素和網(wǎng)絡因素

上述的算法還有什么缺點呢？

隨著時間的變化，用戶的興趣是會變化的，計算用戶相似度的時候每次都把所有微博信息都聚合在一起不太合理。對此，可以通過選取距離當前時間較近的N條微博。比如，對每個用戶，選取距離當前時間最近的50條微博聚在一起放到LDA中訓練。此處的N既不能太大也不能太小。太大則不容易反映用戶興趣的時間變化，太小則由于用戶發(fā)表微博的隨機性容易引起興趣的漂移。為了使效果最好，可以不拘泥于一個固定的N，比如可以考慮對每個用戶按照其發(fā)表微博的時間序列做N值的自適應。

至此，在算法中還沒有考慮微博關系中由回復、轉發(fā)、@等所構成的網(wǎng)絡信息。以轉發(fā)為例，如果在用戶的微博中頻繁的轉發(fā)某個好友的微博，那么用戶和該好友的相似度相比其他好友來說應該會更高。這里可以看做是假設三：

用戶轉發(fā)某好友的微博的頻率越高，用戶與該好友的興趣相似度越大。

相似的，可以得到假設四：

用戶微博中@某用戶的頻率越高，用戶與該好友的興趣相似度越大。

由此就得到了計算相似度的另外的因素。有很多方法可以添加一個新的因素到原有的相似度計算方法中，比如可以考慮將轉發(fā)頻率量化為值，作為權重添加到相似度的衡量中去。

社區(qū)發(fā)現(xiàn)

微博社區(qū)是指在微博中關系緊密的人組成的團體，社區(qū)內部的人之間聯(lián)系緊密，社區(qū)之間的聯(lián)系則比較稀疏。這里所指的關系緊密有兩層含義，第一是社區(qū)內部的人之間的興趣相似度大；第二是指社區(qū)內部的人之間的關系要近，比如要求社區(qū)內部的兩個用戶不能超過二度關聯(lián)，二度關聯(lián)即好友的好友。

興趣相似度在上文已有敘述，關系相似度則需要利用用戶之間的關注關系來進行計算。以用戶的關注關系為單向鏈，可以將所有的微博用戶之間的關系表示為一個巨大的有向圖。用戶之間的關系相似度可以簡單的考慮，比如使用用戶間的最短路徑的倒數(shù)。但是這種方法衡量的不精確，我們知道，在現(xiàn)實世界中，存在著六度理論，在微博網(wǎng)絡及其他社交網(wǎng)絡中，往往關系會更加緊密。因而這種簡單的關系相似度只能有至多六個離散值，顯然不夠精確。

為了達到更好的效果，這里不僅以最短路徑作為顯式量度，還要考慮一些隱式的量度。這里先給出兩個假設，分別為假設五和假設六：

• 兩個用戶的共同好友越多，這兩個好友的關系相似度越高。
• 兩個用戶的共同粉絲越多，這兩個好友的關系相似度越高。

這里可以借鑒Jaccard相似度的計算方式，將這兩種假設的量化函數(shù)表示為交集的大小與并集的大小之商。以假設五為例，其量化指標又被稱為共指向性相似度，量化時使用兩個用戶共同好友的數(shù)目除以兩個用戶所有好友的數(shù)目。假設六的量化指標被稱為共被指向性相似度，計算方式與共指向性相似度類似。從意義上講，這兩種相似度不僅僅是關系上的度量，在一定程度上也衡量了用戶之間的興趣相似程度，直觀上看，兩個用戶共同關注的好友越多，他們的興趣相似程度也越大。這兩種相似度還有一個專業(yè)的名字，是基于結構情景的相似度計算。

得到了最短路徑相似度、共指向性相似度、共被指向性相似度后，可以采用一種加權函數(shù)將它們融合起來，得到最后的相似度。之后，可以采用一些聚類算法如K-Means、DBSCAN等進行聚類操作，得到最后的社區(qū)簇。也可以采用相似度加權的標簽傳播算法，把具有相同標簽的人作為一個社區(qū)。

影響力計算

在社區(qū)發(fā)現(xiàn)中，使用微博中的關系網(wǎng)絡可以提高相似度計算的精確度。但關系網(wǎng)絡能做的事情還有很多，影響力計算便是其中比較重要的應用。

說到影響力的計算，這里借鑒了網(wǎng)頁排名中的算法。網(wǎng)頁排名中廣為人知的算法當屬PageRank了，該算法由google創(chuàng)始人拉里·佩奇和謝爾蓋·布林發(fā)明，隨著google在商業(yè)上的成功而聲名鵲起。該算法根據(jù)網(wǎng)頁之間的鏈接來確定網(wǎng)頁的排名，其核心在于一個假設，質量高的網(wǎng)頁所指向的網(wǎng)頁的質量必定也高。

根據(jù)PageRank的思想，可以得到微博上影響力的假設，稱之為假設七：

影響力高的用戶關注的用戶的影響力必定也高。

將用戶看成是PageRank中的網(wǎng)頁，將關注關系看做是網(wǎng)頁中的鏈接關系。從而，可以根據(jù)PageRank的算法流程得到在微博關注網(wǎng)絡上的影響力計算算法：

1)賦予所有用戶相同的影響力權重；

2)將每個用戶的影響力權重按照其關注的人數(shù)等量分配；

3)對每個用戶來說，其影響力等于其粉絲分配給他的權重之和；

4)第2步和第3步迭代，直到權重不再發(fā)生大的變化為止。

在網(wǎng)頁排名中，基于網(wǎng)絡關系的算法還有HITS、HillTop算法等，這些算法也可以借鑒到影響力計算中來。

上面的算法有什么缺點呢？

如果只是基于關系網(wǎng)絡的話，那么很容易就造成，粉絲數(shù)目多的人影響力必然會很高。這樣就導致有些用戶去購買一些僵尸粉就可以達到很高的影響力了。這樣的算法顯然是不能應對實際情況的，因為還有太多的信息沒有用到。

用戶的影響力除了他的微博關系之外，還與他的個人屬性有很大的關系，比如用戶的活躍度、微文的質量等。用戶的活躍度可以使用其發(fā)表微博的頻度來衡量，微文的質量可以采用其被轉發(fā)的數(shù)目、被回復的數(shù)目來得到。通過對這些值進行衡量，再加上上面算法的結果，就可以得到更加精確的影響力結果。

當然，也可以這樣考慮，用戶之間的回復關系、轉發(fā)關系、@關系均可以構成網(wǎng)絡，它們也有相應的假設，分別為假設八、假設九、假設十：

影響力越高的用戶回復的微博的影響力越高，從而使該微博主人的影響力變高。

影響力越高的用戶轉發(fā)的微博的影響力越高，從而使該微博原創(chuàng)作者的影響力變高。

影響力越高的用戶傾向于在其微博中@影響力高的用戶。

這樣就又得到了轉發(fā)網(wǎng)絡、回復網(wǎng)絡、@網(wǎng)絡三種網(wǎng)絡，借鑒PageRank算法，可以得到另外的三種影響力結果。將它們與關系網(wǎng)絡的影響力結果進行融合，就可以最終的影響力結果了。這里的融合可以簡單的考慮成結果的加權和，復雜的融合方法不在本文的范圍之內。

話題因素和領域因素

得到了影響力的計算方法之后，可以做些什么呢？

可以對當前的熱點話題進行影響力分析，得到誰在微博上成為當前熱點話題的意見領袖。具體做法是這樣，找到和當前熱點話題相關的微文，從而找到參與當前熱點話題的用戶。如何找到和當前熱點話題相關的微文呢？有話題標簽的微文自不必說，對于沒有話題標簽的微文來說，可以使用上文中介紹的LDA算法，它可以在用戶的所有微文中找到用戶的主題分布，也可以對一條微文找到主題分布，一般來說，由于微文的字數(shù)限制在140以內，比較短，因而一條微文包含的主題數(shù)目不會太多，取該微文的主題分布中概率最高的主題當做其主題即可。

找到話題對應的微文與用戶之后，運行影響力計算算法，就可以得到該話題中影響力較大的用戶了。這也是輿情監(jiān)測、社會熱點監(jiān)控的一個方面。

對于標簽傳播算法得到的結果，對同一標簽下的用戶運行影響力計算算法，可以得到該標簽下的影響力排名，即領域內影響力排名。比如，李開復在全部領域內的影響力或許不是最高的，但在IT領域，其影響力絕對是數(shù)一數(shù)二的。

垃圾用戶識別

在影響力計算中，提到要避免僵尸用戶對影響力計算的干擾。在算法中，如果可以識別這樣的用戶，在計算影響力時將其排出在外，不僅可以提高效果，還可以降低計算量。

與影響力計算相似，垃圾用戶的識別要同時考慮用戶屬性與鏈接關系兩方面的因素。

對于垃圾用戶來說，有一些統(tǒng)計上的特征與正常用戶不同。比如如下幾點：

垃圾用戶一般發(fā)微文具有一定的時間規(guī)律性，可以使用熵值對此進行衡量，熵是衡量隨機性的一種量度，隨機性越大，熵值越小。具體做法為將一定的粒度進行時間切片統(tǒng)計，得到每個時間片內的博文概率，然后依照概率進行熵值的計算。熵值越大代表用戶發(fā)微文的時間越有規(guī)律，越有可能是垃圾用戶。

垃圾用戶有些傾向于在微文中惡意的@其他人，因而有些垃圾用戶的微文中@使用的比例比一般用戶高。

有些垃圾用戶的微文中為了進行廣告的推廣，添加大量的URL?？梢酝ㄟ^微文中的URL比例進行衡量。也有些用戶為了騙取URL的點擊，微文中的內容與URL對應界面的內容不一致，這時需要判斷微文與URL內容的一致程度，簡單的做法可以使用詞袋法將微文與URL對應界面表示成詞語向量，查看微文中的詞語在URL對應網(wǎng)頁中出現(xiàn)的頻度。

對于那些為做廣告推銷的用戶，還可以對其微文進行文本分類，判斷其微文是否是廣告，如果某用戶的相當一部分微文是廣告，則該用戶可能是垃圾用戶。

垃圾用戶一般隨意的關注用戶，故其粉絲數(shù)目與好友數(shù)目的比例與正常用戶會有差別。而且正常用戶一般是通過好友關系添加好友的，這樣會形成關注三角形，如A看到其好友B關注了C，那么若A也去關注C，就形成了A關注B、C，B關注C的三角形。一般來說，由于垃圾用戶關注的隨意性，其關注三角形的比例與正常用戶不同。

當然，垃圾用戶與正常用戶的不同之處不止這些，本文不再一一枚舉。垃圾用戶的識別本質上是一個二分類問題，獲得了這些屬性之后，就可以將這些信息輸入到一個機器學習的分類模型中，比如邏輯斯蒂回歸（LR）、決策樹、樸素貝葉斯等，就可以對其進行分類了。

當然，還沒有用到鏈接信息。一般來說，垃圾用戶會去關注正常用戶，而正常用戶不會關注垃圾用戶。這即是假設十一：

正常用戶不傾向于關注垃圾用戶。

這樣就可以再次使用PageRank算法來對用戶是否是垃圾用戶的概率進行計算。這里需要注意的是，算法初始化時采用上面的分類器結果，將垃圾用戶的概率設為1，正常用戶的概率設為0。在PageRank計算過程中，不能通過簡單的求和公式計算，比如如果一個用戶關注了多個垃圾用戶的時候，求和后概率可能大于1；因而需要使用一些歸一化方法或指數(shù)族函數(shù)進行概率的更新。

結語

本文對微博中常見的問題的對應算法進行了簡單的介紹，在實際應用中的算法比介紹的要復雜的多。當然，本文覆蓋的主題并不全，比如好友推薦、熱點跟蹤等就沒有涉及到。但古人云“窺一斑而見全豹”，希望本文的介紹能幫助大家更好的理解微博這樣的社交網(wǎng)絡應用。

在文中，可以看到黑體標出的假設，這些假設看起來都與我們的直觀感覺一致。而根據(jù)這些可以引申出很多有效的算法。所以有時候，只要你肯發(fā)現(xiàn)，算法就在身邊。