微博是一個(gè)很多人都在用的社交應(yīng)用。天天刷微博的人每天都會進(jìn)行著這樣幾個(gè)操作：原創(chuàng)、轉(zhuǎn)發(fā)、回復(fù)、閱讀、關(guān)注、@等。其中，前四個(gè)是針對短博文，最后的關(guān)注和@則針對的是用戶之間的關(guān)系，關(guān)注某個(gè)人就意味著你成為他的粉絲，而他成為你的好友;@某個(gè)人意味著你想要他看到你的微博信息。
微博被人們認(rèn)為是“自媒體”，即普通大眾分享與本身相關(guān)的“新聞”的途徑。最近，有些人使用自己在自媒體上的影響力而盈利的報(bào)道屢見不鮮。那微博上個(gè)人影響力是怎樣計(jì)算的呢?微博上還有哪些算法作為看不見的手在管理著我們?我們的每一個(gè)行為怎樣影響著算法呢?
直觀上看，微博其實(shí)是人類社會的一個(gè)簡單的縮影，微博網(wǎng)絡(luò)的一些特點(diǎn)，也許可以啟發(fā)我們得到真實(shí)的社會網(wǎng)絡(luò)上的規(guī)律。得益于社交網(wǎng)絡(luò)的爆發(fā)式發(fā)展，“社會計(jì)算”尤其是社交網(wǎng)絡(luò)分析成為數(shù)據(jù)挖掘的新寵兒。下面我們就針對微博網(wǎng)絡(luò)分析的一些算法進(jìn)行簡單的介紹，其中的有些算法對于其他的社交應(yīng)用可能也適用。
標(biāo)簽傳播
微博用戶量浩大，不同的人有不同的興趣。挖掘每個(gè)用戶的興趣有助于更加精準(zhǔn)的廣告投放、內(nèi)容推薦。為了得到每個(gè)用戶的興趣，可以為用戶打上標(biāo)簽，每個(gè)標(biāo)簽代表用戶的一個(gè)興趣，用戶可以擁有一個(gè)或多個(gè)標(biāo)簽。為了得到最終的用戶標(biāo)簽，先做第一個(gè)假設(shè)：
每個(gè)用戶的好友(或粉絲)中與該用戶具有相同興趣的人占多數(shù)。
這就引出了本文介紹的第一個(gè)算法，即標(biāo)簽傳播算法。在這個(gè)算法中，每個(gè)用戶的標(biāo)簽取其好友或粉絲中標(biāo)簽最多的一個(gè)或多個(gè)。當(dāng)然，可以將好友和粉絲的標(biāo)簽都考慮進(jìn)來，整合的時(shí)候可以考慮賦予好友的標(biāo)簽和粉絲的標(biāo)簽不同的權(quán)重。標(biāo)簽傳播算法的過程如下：
1)對一部分用戶給出初始標(biāo)簽;
2)對每一個(gè)用戶，統(tǒng)計(jì)其好友和粉絲的標(biāo)簽數(shù)目，賦予該用戶出現(xiàn)次數(shù)最多的一個(gè)或者多個(gè)標(biāo)簽。
3)循環(huán)進(jìn)行第2步，直到用戶的標(biāo)簽不再發(fā)生大的變化為止。
用戶相似度計(jì)算
標(biāo)簽傳播算法實(shí)現(xiàn)起來比較簡單，其缺點(diǎn)在于當(dāng)所做的假設(shè)不符合事實(shí)時(shí)，比如為了社交上的禮貌，我們一般會把自己的親友添加關(guān)注，這些人不一定和我們擁有同樣的標(biāo)簽;該算法的結(jié)果就會變得很差。解決的辦法就是通過計(jì)算用戶之間的相似度來衡量好友或粉絲的標(biāo)簽對用戶標(biāo)簽的貢獻(xiàn)率。因而得到第二個(gè)假設(shè)：
與用戶越相似的好友或粉絲，其標(biāo)簽越可能是用戶的標(biāo)簽。
那么，如何衡量用戶之間的相似度呢?這就需要考慮到用戶發(fā)表的微博信息了，包括轉(zhuǎn)發(fā)的和原創(chuàng)的。這里是要考慮用戶之間的相似度而不是用戶微博之間的相似度，因而在實(shí)際計(jì)算時(shí)，將某個(gè)用戶的所有微博信息聚集到一起進(jìn)行計(jì)算。一個(gè)可選的方法是使用詞袋法將微博信息表示成詞語向量，然后直接使用余弦方法等計(jì)算其相似度。但這個(gè)方法太過簡單，不容易達(dá)到好的結(jié)果，這里介紹一種基于LDA(隱含狄利克雷分布)的相似度計(jì)算方法。
LDA仍然使用詞袋法表示文本，但是在中間添加了一個(gè)主題層，形成了“文檔-主題-詞語”三層概率模型，即每篇文檔看成是主題的一種概率分布，主題又被看成是單詞的概率分布。在LDA模型下，文檔可以被看成按照如下方式生成：
1)對于每篇文檔：
2)從主題分布中抽取一個(gè)主題;
3)從該主題的詞語分布中抽取一個(gè)詞語;
4)重復(fù)第2步和第3步，直到該文檔的所有詞語都生成。
LDA模型參數(shù)的估計(jì)算法不在本文的討論范圍之內(nèi)。這里只需要知道，通過LDA可以得到每個(gè)用戶的微博信息的主題分布。然后使用余弦方法、KL距離等計(jì)算相似度的方法來得到用戶間主題分布的相似度，以之作為用戶之間的相似度。而后使用該相似度對標(biāo)簽傳播進(jìn)行加權(quán)。
時(shí)間因素和網(wǎng)絡(luò)因素
上述的算法還有什么缺點(diǎn)呢?
隨著時(shí)間的變化，用戶的興趣是會變化的，計(jì)算用戶相似度的時(shí)候每次都把所有微博信息都聚合在一起不太合理。對此，可以通過選取距離當(dāng)前時(shí)間較近的N條微博。比如，對每個(gè)用戶，選取距離當(dāng)前時(shí)間最近的50條微博聚在一起放到LDA中訓(xùn)練。此處的N既不能太大也不能太小。太大則不容易反映用戶興趣的時(shí)間變化，太小則由于用戶發(fā)表微博的隨機(jī)性容易引起興趣的漂移。為了使效果最好，可以不拘泥于一個(gè)固定的N，比如可以考慮對每個(gè)用戶按照其發(fā)表微博的時(shí)間序列做N值的自適應(yīng)。
至此，在算法中還沒有考慮微博關(guān)系中由回復(fù)、轉(zhuǎn)發(fā)、@等所構(gòu)成的網(wǎng)絡(luò)信息。以轉(zhuǎn)發(fā)為例，如果在用戶的微博中頻繁的轉(zhuǎn)發(fā)某個(gè)好友的微博，那么用戶和該好友的相似度相比其他好友來說應(yīng)該會更高。這里可以看做是假設(shè)三：
用戶轉(zhuǎn)發(fā)某好友的微博的頻率越高，用戶與該好友的興趣相似度越大。
相似的，可以得到假設(shè)四：
用戶微博中@某用戶的頻率越高，用戶與該好友的興趣相似度越大。
由此就得到了計(jì)算相似度的另外的因素。有很多方法可以添加一個(gè)新的因素到原有的相似度計(jì)算方法中，比如可以考慮將轉(zhuǎn)發(fā)頻率量化為值，作為權(quán)重添加到相似度的衡量中去。
社區(qū)發(fā)現(xiàn)
微博社區(qū)是指在微博中關(guān)系緊密的人組成的團(tuán)體，社區(qū)內(nèi)部的人之間聯(lián)系緊密，社區(qū)之間的聯(lián)系則比較稀疏。這里所指的關(guān)系緊密有兩層含義，第一是社區(qū)內(nèi)部的人之間的興趣相似度大;第二是指社區(qū)內(nèi)部的人之間的關(guān)系要近，比如要求社區(qū)內(nèi)部的兩個(gè)用戶不能超過二度關(guān)聯(lián)，二度關(guān)聯(lián)即好友的好友。
興趣相似度在上文已有敘述，關(guān)系相似度則需要利用用戶之間的關(guān)注關(guān)系來進(jìn)行計(jì)算。以用戶的關(guān)注關(guān)系為單向鏈，可以將所有的微博用戶之間的關(guān)系表示為一個(gè)巨大的有向圖。用戶之間的關(guān)系相似度可以簡單的考慮，比如使用用戶間的最短路徑的倒數(shù)。但是這種方法衡量的不精確，我們知道，在現(xiàn)實(shí)世界中，存在著六度理論，在微博網(wǎng)絡(luò)及其他社交網(wǎng)絡(luò)中，往往關(guān)系會更加緊密。因而這種簡單的關(guān)系相似度只能有至多六個(gè)離散值，顯然不夠精確。
為了達(dá)到更好的效果，這里不僅以最短路徑作為顯式量度，還要考慮一些隱式的量度。這里先給出兩個(gè)假設(shè)，分別為假設(shè)五和假設(shè)六：
兩個(gè)用戶的共同好友越多，這兩個(gè)好友的關(guān)系相似度越高。
兩個(gè)用戶的共同粉絲越多，這兩個(gè)好友的關(guān)系相似度越高。
這里可以借鑒Jaccard相似度的計(jì)算方式，將這兩種假設(shè)的量化函數(shù)表示為交集的大小與并集的大小之商。以假設(shè)五為例，其量化指標(biāo)又被稱為共指向性相似度，量化時(shí)使用兩個(gè)用戶共同好友的數(shù)目除以兩個(gè)用戶所有好友的數(shù)目。假設(shè)六的量化指標(biāo)被稱為共被指向性相似度，計(jì)算方式與共指向性相似度類似。從意義上講，這兩種相似度不僅僅是關(guān)系上的度量，在一定程度上也衡量了用戶之間的興趣相似程度，直觀上看，兩個(gè)用戶共同關(guān)注的好友越多，他們的興趣相似程度也越大。這兩種相似度還有一個(gè)專業(yè)的名字，是基于結(jié)構(gòu)情景的相似度計(jì)算。
得到了最短路徑相似度、共指向性相似度、共被指向性相似度后，可以采用一種加權(quán)函數(shù)將它們?nèi)诤掀饋恚玫阶詈蟮南嗨贫取Ｖ螅梢圆捎靡恍┚垲愃惴ㄈ鏚- Means、DBSCAN等進(jìn)行聚類操作，得到最后的社區(qū)簇。也可以采用相似度加權(quán)的標(biāo)簽傳播算法，把具有相同標(biāo)簽的人作為一個(gè)社區(qū)。
影響力計(jì)算
在社區(qū)發(fā)現(xiàn)中，使用微博中的關(guān)系網(wǎng)絡(luò)可以提高相似度計(jì)算的精確度。但關(guān)系網(wǎng)絡(luò)能做的事情還有很多，影響力計(jì)算便是其中比較重要的應(yīng)用。
說到影響力的計(jì)算，這里借鑒了網(wǎng)頁排名中的算法。網(wǎng)頁排名中廣為人知的算法當(dāng)屬PageRank了，該算法由google創(chuàng)始人拉里·佩奇和謝爾蓋·布林發(fā)明，隨著google在商業(yè)上的成功而聲名鵲起。該算法根據(jù)網(wǎng)頁之間的鏈接來確定網(wǎng)頁的排名，其核心在于一個(gè)假設(shè)，質(zhì)量高的網(wǎng)頁所指向的網(wǎng)頁的質(zhì)量必定也高。
根據(jù)PageRank的思想，可以得到微博上影響力的假設(shè)，稱之為假設(shè)七：
影響力高的用戶關(guān)注的用戶的影響力必定也高。
將用戶看成是PageRank中的網(wǎng)頁，將關(guān)注關(guān)系看做是網(wǎng)頁中的鏈接關(guān)系。從而，可以根據(jù)PageRank的算法流程得到在微博關(guān)注網(wǎng)絡(luò)上的影響力計(jì)算算法：
1)賦予所有用戶相同的影響力權(quán)重;
2)將每個(gè)用戶的影響力權(quán)重按照其關(guān)注的人數(shù)等量分配;
3)對每個(gè)用戶來說，其影響力等于其粉絲分配給他的權(quán)重之和;
4)第2步和第3步迭代，直到權(quán)重不再發(fā)生大的變化為止。
在網(wǎng)頁排名中，基于網(wǎng)絡(luò)關(guān)系的算法還有HITS、HillTop算法等，這些算法也可以借鑒到影響力計(jì)算中來。
上面的算法有什么缺點(diǎn)呢?
如果只是基于關(guān)系網(wǎng)絡(luò)的話，那么很容易就造成，粉絲數(shù)目多的人影響力必然會很高。這樣就導(dǎo)致有些用戶去購買一些僵尸粉就可以達(dá)到很高的影響力了。這樣的算法顯然是不能應(yīng)對實(shí)際情況的，因?yàn)檫€有太多的信息沒有用到。
用戶的影響力除了他的微博關(guān)系之外，還與他的個(gè)人屬性有很大的關(guān)系，比如用戶的活躍度、微文的質(zhì)量等。用戶的活躍度可以使用其發(fā)表微博的頻度來衡量，微文的質(zhì)量可以采用其被轉(zhuǎn)發(fā)的數(shù)目、被回復(fù)的數(shù)目來得到。通過對這些值進(jìn)行衡量，再加上上面算法的結(jié)果，就可以得到更加精確的影響力結(jié)果。
當(dāng)然，也可以這樣考慮，用戶之間的回復(fù)關(guān)系、轉(zhuǎn)發(fā)關(guān)系、@關(guān)系均可以構(gòu)成網(wǎng)絡(luò)，它們也有相應(yīng)的假設(shè)，分別為假設(shè)八、假設(shè)九、假設(shè)十：
影響力越高的用戶回復(fù)的微博的影響力越高，從而使該微博主人的影響力變高。
影響力越高的用戶轉(zhuǎn)發(fā)的微博的影響力越高，從而使該微博原創(chuàng)作者的影響力變高。
影響力越高的用戶傾向于在其微博中@影響力高的用戶。
這樣就又得到了轉(zhuǎn)發(fā)網(wǎng)絡(luò)、回復(fù)網(wǎng)絡(luò)、@網(wǎng)絡(luò)三種網(wǎng)絡(luò)，借鑒PageRank算法，可以得到另外的三種影響力結(jié)果。將它們與關(guān)系網(wǎng)絡(luò)的影響力結(jié)果進(jìn)行融合，就可以最終的影響力結(jié)果了。這里的融合可以簡單的考慮成結(jié)果的加權(quán)和，復(fù)雜的融合方法不在本文的范圍之內(nèi)。
話題因素和領(lǐng)域因素
得到了影響力的計(jì)算方法之后，可以做些什么呢?
可以對當(dāng)前的熱點(diǎn)話題進(jìn)行影響力分析，得到誰在微博上成為當(dāng)前熱點(diǎn)話題的意見領(lǐng)袖。具體做法是這樣，找到和當(dāng)前熱點(diǎn)話題相關(guān)的微文，從而找到參與當(dāng)前熱點(diǎn)話題的用戶。如何找到和當(dāng)前熱點(diǎn)話題相關(guān)的微文呢?有話題標(biāo)簽的微文自不必說，對于沒有話題標(biāo)簽的微文來說，可以使用上文中介紹的LDA算法，它可以在用戶的所有微文中找到用戶的主題分布，也可以對一條微文找到主題分布，一般來說，由于微文的字?jǐn)?shù)限制在140以內(nèi)，比較短，因而一條微文包含的主題數(shù)目不會太多，取該微文的主題分布中概率最高的主題當(dāng)做其主題即可。
找到話題對應(yīng)的微文與用戶之后，運(yùn)行影響力計(jì)算算法，就可以得到該話題中影響力較大的用戶了。這也是輿情監(jiān)測、社會熱點(diǎn)監(jiān)控的一個(gè)方面。
對于標(biāo)簽傳播算法得到的結(jié)果，對同一標(biāo)簽下的用戶運(yùn)行影響力計(jì)算算法，可以得到該標(biāo)簽下的影響力排名，即領(lǐng)域內(nèi)影響力排名。比如，李開復(fù)在全部領(lǐng)域內(nèi)的影響力或許不是最高的，但在IT領(lǐng)域，其影響力絕對是數(shù)一數(shù)二的。
垃圾用戶識別
在影響力計(jì)算中，提到要避免僵尸用戶對影響力計(jì)算的干擾。在算法中，如果可以識別這樣的用戶，在計(jì)算影響力時(shí)將其排出在外，不僅可以提高效果，還可以降低計(jì)算量。
與影響力計(jì)算相似，垃圾用戶的識別要同時(shí)考慮用戶屬性與鏈接關(guān)系兩方面的因素。
對于垃圾用戶來說，有一些統(tǒng)計(jì)上的特征與正常用戶不同。比如如下幾點(diǎn)：
垃圾用戶一般發(fā)微文具有一定的時(shí)間規(guī)律性，可以使用熵值對此進(jìn)行衡量，熵是衡量隨機(jī)性的一種量度，隨機(jī)性越大，熵值越小。具體做法為將一定的粒度進(jìn)行時(shí)間切片統(tǒng)計(jì)，得到每個(gè)時(shí)間片內(nèi)的博文概率，然后依照概率進(jìn)行熵值的計(jì)算。熵值越大代表用戶發(fā)微文的時(shí)間越有規(guī)律，越有可能是垃圾用戶。
垃圾用戶有些傾向于在微文中惡意的@其他人，因而有些垃圾用戶的微文中@使用的比例比一般用戶高。
有些垃圾用戶的微文中為了進(jìn)行廣告的推廣，添加大量的URL。可以通過微文中的URL比例進(jìn)行衡量。也有些用戶為了騙取URL的點(diǎn)擊，微文中的內(nèi)容與URL 對應(yīng)界面的內(nèi)容不一致，這時(shí)需要判斷微文與URL內(nèi)容的一致程度，簡單的做法可以使用詞袋法將微文與URL對應(yīng)界面表示成詞語向量，查看微文中的詞語在 URL對應(yīng)網(wǎng)頁中出現(xiàn)的頻度。
對于那些為做廣告推銷的用戶，還可以對其微文進(jìn)行文本分類，判斷其微文是否是廣告，如果某用戶的相當(dāng)一部分微文是廣告，則該用戶可能是垃圾用戶。
垃圾用戶一般隨意的關(guān)注用戶，故其粉絲數(shù)目與好友數(shù)目的比例與正常用戶會有差別。而且正常用戶一般是通過好友關(guān)系添加好友的，這樣會形成關(guān)注三角形，如A看到其好友B關(guān)注了C，那么若A也去關(guān)注C，就形成了A關(guān)注B、C，B關(guān)注C的三角形。一般來說，由于垃圾用戶關(guān)注的隨意性，其關(guān)注三角形的比例與正常用戶不同。
當(dāng)然，垃圾用戶與正常用戶的不同之處不止這些，本文不再一一枚舉。垃圾用戶的識別本質(zhì)上是一個(gè)二分類問題，獲得了這些屬性之后，就可以將這些信息輸入到一個(gè)機(jī)器學(xué)習(xí)的分類模型中，比如邏輯斯蒂回歸(LR)、決策樹、樸素貝葉斯等，就可以對其進(jìn)行分類了。
當(dāng)然，還沒有用到鏈接信息。一般來說，垃圾用戶會去關(guān)注正常用戶，而正常用戶不會關(guān)注垃圾用戶。這即是假設(shè)十一：
正常用戶不傾向于關(guān)注垃圾用戶。
這樣就可以再次使用PageRank算法來對用戶是否是垃圾用戶的概率進(jìn)行計(jì)算。這里需要注意的是，算法初始化時(shí)采用上面的分類器結(jié)果，將垃圾用戶的概率設(shè)為1，正常用戶的概率設(shè)為0。在PageRank計(jì)算過程中，不能通過簡單的求和公式計(jì)算，比如如果一個(gè)用戶關(guān)注了多個(gè)垃圾用戶的時(shí)候，求和后概率可能大于1;因而需要使用一些歸一化方法或指數(shù)族函數(shù)進(jìn)行概率的更新。
結(jié)語
本文對微博中常見的問題的對應(yīng)算法進(jìn)行了簡單的介紹，在實(shí)際應(yīng)用中的算法比介紹的要復(fù)雜的多。當(dāng)然，本文覆蓋的主題并不全，比如好友推薦、熱點(diǎn)跟蹤等就沒有涉及到。但古人云“窺一斑而見全豹”，希望本文的介紹能幫助大家更好的理解微博這樣的社交網(wǎng)絡(luò)應(yīng)用。
在文中，可以看到黑體標(biāo)出的假設(shè)，這些假設(shè)看起來都與我們的直觀感覺一致。而根據(jù)這些可以引申出很多有效的算法。所以有時(shí)候，只要你肯發(fā)現(xiàn)，算法就在身邊。
(來源：企鵝大數(shù)據(jù))
標(biāo)簽：
大數(shù)據(jù)大數(shù)據(jù)處理
本站文章除注明轉(zhuǎn)載外，均為本站原創(chuàng)或翻譯。歡迎任何形式的轉(zhuǎn)載，但請務(wù)必注明出處、不得修改原文相關(guān)鏈接，如果存在內(nèi)容上的異議請郵件反饋至chenjj@ke049m.cn
半島外圍網(wǎng)上直營 
1次
半島外圍網(wǎng)上直營相關(guān)的文章 
微信
在線咨詢
渝公網(wǎng)安備
50010702500608號
客服熱線