基于監督隨機游走的有影響力用戶發現算法

唐明偉，高振偉,2，王彥婷，王 鎮，鄧加鈺，陳曉亮

（1.西華大學計算機與軟件工程學院，四川 成都 610039；2.中電科大數據研究院，貴州 貴陽 550022）

隨著網絡的發展，網絡社交平臺（如微博等）的出現改變了人們的生活。興趣愛好類似的個體之間會相互關注。個體間的交互也較大地影響著網絡的拓撲關系。基于用戶的行為特征去判斷其影響力是熱點研究內容之一。基于微博的社交關系特性，挖掘信息的發送者，尤其是具有很大影響力的關鍵核心用戶是非常重要的。但是，大量的“僵尸粉”充斥著微博，依據粉絲數等特征不能有效地判斷該用戶的真實影響力。剔除微博中的“僵尸粉”，挖掘該用戶的真實影響力，具有重要的現實意義。網絡結構和文本信息是識別有影響力用戶的重要因素。

1 相關工作

基于隨機游走思想的PageRank 算法已在社交網絡得到廣泛研究。該算法為節點分配代表其重要性的數值，測算每個節點值，并確定網絡的結構。基于微博的個體特征及其行為特征，原野等[1]使用博文的規則和互動量計算公式，提出了基于MapReduce 和Spark 的并行計算框架。基于用戶的粉絲數與其所發布的相關信息傳播擴散速度的正相關性，Kwak 等[2]利用Twitter 社交網絡和PageRank 變形提出了TunkRank 算法。Romero 等[3]分析了被影響的用戶數和沒有被影響的用戶數，得出影響力是建立在粉絲被動性及關注者積極性上的結論。Mao 等[4]采用一種基于學習的方法來分析和測算用戶的社會影響力，進而判斷用戶傳播信息的能力。Agarwal 等[5]根據博文的評論、內容、互動程度及外部鏈接等特征對博客用戶影響力進行全面評估與分析。Zhang 等[6]基于用戶評論等交互行為，計算在不同時段用戶的影響強弱。Huang 等[7]將PageRank 算法應用到用戶活動特征中來評價微博用戶的影響力。Tang 等[8]研究和分析了用戶的會話內容等特征，采用加權的社會網絡來評估用戶的顯式和隱式影響力。基于用戶的活動因素、歷史關注和微博的傳播力因素，Chen 等[9]提出了一種用戶影響力排名算法。通過用戶之間存在的交互程度，Sheikhahmadi 等[10]提出了一種在社交網絡中識別有影響力用戶的方法。Wang 等[11]提出了一種基于情緒一致性的算法來查找Topk有影響力的用戶。

文本內容是被用來評估用戶影響力的因素之一。根據主題敏感程度和用戶的互動等，Weng 等[12]分析用戶和鏈接關系的局部相似性提出TwitterRank算法。Xiao 等[13]基于特征的共現詞檢測標簽去檢測新聞主題相關的用戶社區，并分別從轉發和提及2 方面對主題社區下的活躍用戶影響力進行了評估。Li 等[14]提出一種基于在線學習社區的混合框架的意見領袖發現算法。從用戶內容中提取主題以及利用主題之間的分布相似性，Pal 等[15]提出了使用主題建模的方法去判斷用戶影響值大小。結合不同主題下的影響力的傳播模型（TAP），Hu 等[16]通過綜合分析當前網絡拓撲和所有節點的主題分布，構建了基于主題因子的傳播模型（TFG）。融合主題模型和影響力，Bi 等[17]提出了一個比潛狄利克雷分配模型（LDA）更復雜的混合模型（FLDA模型）。根據用戶對話題的情感極性，Eliacik 等[18]提出了一種在社交網絡中計算影響力用戶的算法。Backstrom 等[19]提出了基于監督的隨機游走（supervised random walks，SRW）算法。

研究者常常更注重依賴網絡結構去發現有影響力的用戶，但是微博社交平臺有影響力的用戶通常只擅長某一領域，也只會影響具有相似度高的一批用戶；因此，本文將鏈路預測的方法應用到有影響力用戶檢測中，提出了基于用戶主題偏好的監督的隨機游走算法（topic preferences supervised random walks，簡稱TP-SRW）。

2 基于用戶主題偏好的監督隨機游走算法（TP-SRW 算法）

2.1 監督隨機游走

基于用戶主題偏好的監督隨機游走的模型框架如圖1 所示。由于無監督隨機游走的不確定性，因此本文在隨機游走的基礎上加上監督的方式去指導游走節點進行游走。它巧妙地融合了網絡結構、節點和邊的特征，使游走的節點更加傾向于目的節點。

重啟隨機游走是隨機游走的一種改進,當將要進行下一步轉移時有2 種選擇：根據狀態轉移矩陣以一定的概率隨機地選擇下一個節點；以一定的概率回到初始節點重新開始游走。

圖1 基于用戶主題偏好的監督隨機游走模型

社交網絡可以用有向圖G=(V,E)表示,V表示節點的集合，E表示節點與節點之間相連的邊。2 個節點之間存在邊，代表用戶與用戶之間有社交互動，具體來說：邊ei j表示用戶ui與用戶uj發生了互動關系，對于每一條邊，建立一個特征向量 φuv去描述2 節點相連的邊以及節點本身的關系。特征向量 φuv有以下特征：粉絲數、微博數量、關注數、興趣主題、微博被轉發數。對于每一個節點可以根據該用戶的歷史微博得出該用戶的主題概率分布，用suv表示2 個節點之間的主題相似性評分。在有監督隨機游走的過程中，需要學習出一個邊權重的參數，首先用PageRank 生成一組有影響力的節點I={i1,i2,···,in}和一組沒有影響力的節點IN={n1,n2,···,nn}，其目的就是讓隨機游走出來的結果包含I但是不包含IN。因此，在隨機游走算法中利用邊權重計算函數fw(φuv)和主題相似度評分suv來計算邊的重要度auv=fw(φuv)suv。邊的重要度就是隨機游走過程中節點間的轉移概率。

2.2 基于LDA 主題模型的用戶主題偏好

微博文本字數有限，通常小于140 個字符，除去一些噪聲信息，可利用的信息有限。本文首先把每位用戶在特定時間內所有微博、評論以及反饋等信息收集到一個文件中，并一一對應；然后使用LTP 分詞工具對該文件進行預處理，只保留名詞等關鍵信息；接著利用LDA 主題模型對每篇文檔的主題進行抽取，并將結果保存在用戶-主題偏好矩陣中。假設主題集合數為m，用戶數為n，每個用戶都有矩陣中對應的各個主題的偏好概率。根據各個主題偏好的概率，建立D=U×IT矩陣，其中U代表微博用戶集合，IT代表主題偏好集合。在D矩陣中，元素anm表示用戶vn所發表的微博文本中關于主題tm的概率，它描述用戶對主題社區的偏好程度。用戶-主題偏好矩陣為

2.3 微博用戶主題相似度計算

在微博社區中，同質性代表具有相同或者相似興趣愛好的用戶。當一個用戶發表了1 篇微博，與該用戶具有同質性的用戶會對該微博產生興趣，行為上主要體現在對該微博進行轉發、評論、回復、點贊等操作。因此，可以根據用戶的微博文本的主題相似度來衡量用戶的同質性，再依據排序算法，對某一特定主題下具有同質性的用戶進行排序，進而找出特定主題下有影響力的用戶。

本文將每個微博用戶所有發表、轉發和評論的內容歸集到1 篇文檔中，然后用2.2 節的LDA主題模型進行分類，并將分類結果保存在用戶-主題偏好矩陣D中。準確來說，給定所有用戶的主題分布，通過計算相應主題的概率分布來計算用戶所發微博、回復、評論所形成的文檔之間的相似度。

1）主題相異度Dis(i,j)，表示2 主題分布的差異程度。

式中，TS(i,j)是Jensen-Shannon 散度,它是相對熵（Kullback-Leibler Divergence，KL 距離）一種變種，主要用來衡量2 個變量的相似度，其表達式[20]為

其中，M是2個概率分布的平均值，Ai和Aj是不同用戶i,j對應的文檔的主題概率分布，是Ai和Aj2 個向量之間的 Kullback-Leibler 散度，也是衡量2 個概率分布的差異程度。

2）用戶主題相似度計算。主題相似度可以通過用戶對應的主題分布的Jensen-Shannon 散度進行計算，用 topici j表示。其中，topici j是介于0-1 的值，主題相關度越大，說明2 個用戶感興趣主題越相似。可通過對數據進行規范化處理，有效地提升算法魯棒性。

2.4 基于主題偏好的監督隨機游走算法

在微博社交網絡中，假如用戶A 發表了1 篇微博，A 的粉絲B 受到A 的影響以一定的概率轉發了用戶A 的微博，則此概率就是節點A到節點B之間的轉移概率。傳統的方式是采用PageRank 算法來計算節點之間的轉移概率，然而在微博中，用戶興趣深刻地影響著用戶的轉發等行為；因此，在計算轉移概率時要考慮2 個節點興趣的相似度和邊的屬性特征。在進行隨機游走前，利用優化的方法去計算邊的重要度，對于每一條邊，建立一個特征向量φuv去描述2 節點相連的邊以及節點本身的關系，本文采用來表示。這里的auv就是隨機游走過程中節點間的轉移概率，用特征向量w來表示邊權重計算函數fw(φuv)的參數。與文獻[20]提出方法類似，本文通過計算邊的權重來確定更有影響力的節點，最終確定最佳參數w（即邊權重函數f的參數）。

監督隨機游走算法中用到的參數最優化問題定義為

式中：I為具有影響力的節點集合；IN為沒有影響力的節點集合；λ為正則化參數，用作平衡模型的復雜度與其結果約束條件強弱之間的關系。它的值越大，說明約束條件越強，反之則越弱，對錯分情況的容忍度越大。在實驗中，λ過小容易發生過擬合的風險。在本文中，當λ=1時，實驗效果達到最好。為了解決最優化問題，采用改進L-BFGS 算法[21]去尋找最優的w，使得F(w)最小。損失函數h通過不同的pi-pn進行懲罰，如果pi-pn＞0也就是h(·)=0，即沒有違反約束，反之，pi-pn＜0即h(·)＞0。在這里采用了Wilcoxon-Mann-Whitney（WMW）損失函數[22]，為

在學習邊權重參數前，首先建立邊權重函數fw(φuv)與邊權重參數w以及主題偏好隨機游走得分p聯系。具體來說，給定邊的權重函數和主題相似性評分求出邊的重要度auv,根據這個邊的重要度來指導隨機游走。

定義從節點u到節點v的轉移矩陣Q和轉移概率PQ為：

由式（9）（10）可知，主題相似度越高，邊的權重越大，轉移概率越高越容易找到更有影響力的節點。

在隨機游走過程中，會遇到鏈路中斷等情況，因此引入了重啟動隨機游走機制，也就是節點在隨機游走過程中會以一定的概率回到初始節點重新開始隨機游走，設重啟概率為γ，假設s為初始節點，那么

且

在網絡中按照轉移矩陣Q*中的概率進行重啟動的隨機游走，最終會達到一個穩定的狀態，此時，每一個節點都能得到一個概率值，即從初始節點出發按照重啟隨機游走概率矩陣Q*的概率在網絡上游走訪問到該節點的概率，此時主題偏好隨機游走概率滿足式（13）。

式（13）使節點的PageRank 評分pu∈p以及邊權重計算函數的fw(φuv)學習參數w通過隨機游走轉移矩陣Q聯系到一起。F(w)相對于w的梯度，為

其中δin=pi-pn，已知loss()損失函數，可以求出關于w的損失函數，這里需要計算的是，根據式（13）可以得到

輸出：最佳參數w。

step 1:選初始點w0，收斂誤差ε ＞0，存儲最近m次的迭代數據。

step 2:k=0,r=?F(w0)。

step 3:如果‖?F(wk+1)‖≤ε，則返回最優解w，否則轉入step 4。

step 4:計算本次迭代的可行方向pk=-rk。

step 5:計算步長ak＞0，對下面的式子進行一維搜索。

step 7:如果大于，保留最近 次的向量對，刪除。

step 8:計算并保持。

step 9:用two-loop recursion 算法計算rk。

step 10:k=k+1，并轉入step 3。

根據上述算法求出最佳參數向量w，計算對應節點的轉移概率來進行有影響力的用戶發現。TPSRW 算法如圖2 所示。

圖2 用戶主題偏好的監督隨機游走算法偽代碼

3 TP-SRW 算法實驗

現進行僵尸粉識別ASDM 模型（advertising spammers detecting model）實驗和有影響力用戶發現TP-SRW 算法（topic preferences supervised random walks）實驗，其實驗流程如圖3 所示。

圖3 實驗流程圖

實驗數據主要包括微博用戶的ID、用戶發表微博帖子內容、用戶的關注數量和粉絲數量，以及關注轉發評論等關系信息。微博數據的獲取途徑有2 種：數據集1 利用微博爬蟲對新浪微博平臺進行微博數據的爬取，共爬取了6 萬4 168 條微博數據；數據集2 來自于2016 年第五屆全國社會媒體處理大會（SMP2016）中比賽用的微博數據集，有4 萬8 162 條微博數據。本文將數據集1 作為訓練集，數據集2 作為測試集。

本文采用LTP 系統對微博短文本切詞、分詞等微博數據進行處理[23]。

為分析用戶的主題偏好，本文把同一用戶在一定時間內所有博文、評論以及回復集中到1 篇文檔中，然后對文檔進行切詞、分詞處理，接著利用Mahout 機器學習平臺，采用LDA 主題模型對文檔的主題進行分析。部分關鍵詞表示如表1 所示。

針對LDA 模型，文獻[20]認為主題數選取在20 左右得出的結論效果較好。本文計算用戶主題偏好時，僅需要對用戶偏好進行模糊評估，因此，選取主題數小于所有可能的話題數，降低了擬牛頓法訓練過程中參數w的收斂時間。表2示出部分用戶對于指定的5 個主題的偏好概率分布情況。相關主題概率越大，代表著其越偏向于某個主題。

表1 主題對應關鍵詞

表2 用戶相關微博的比例

3.1 “僵尸粉”識別實驗與結果分析

3.1.1 “僵尸粉”標注

由于“僵尸粉”的不斷變異升級，在分類“僵尸粉”時沒有可以利用的現成標注過的訓練集，因此本文采用手工標注的方式去標注數據集中的僵尸粉。在度量用戶的影響力時僅僅是活躍的“僵尸粉”才會對用戶影響力產生影響。該類“僵尸粉”表面上看和正常用戶是區分不開的，但該類用戶會轉發或者發布大量的營銷類博文；因此，本文通過二人雙盲的方式標注用戶的微博文本。首先通過標注的文本和垃圾微博占的比例來確認該用戶是否為“僵尸粉”，然后分析該類用戶在用戶屬性和行為上和正常用戶的差異性。

對于微博文本，本文采用LDA 主題模型進行分析，統計出正常隨機用戶和“僵尸粉”用戶在微博文本主題上分布的差異性，其結果如表3 所示。可以看出，營銷類“僵尸粉”用戶和隨機用戶在微博文本主題分布上很有大的差異。隨機用戶中概率較高的主題為親子、旅行、生活、經濟、政治等，而營銷類“僵尸粉”概率較高的主題多為有獎抽獎推廣、商品推廣、鏈接推薦、婚紗攝影推廣等。可見，將微博文本特征用于識別廣告類“僵尸粉”是可行的。

表3 隨機用戶和廣告“僵尸粉”用戶的主題分布

3.1.2 實驗評價指標

為了評估僵尸粉識別ASDM 模型的性能，分別使用準確率P（precision）、召回率R（recall）和F值（F-value）。P和R相互影響和相互制約，F值則表示綜合考慮準確率和召回率二者關系。其定義為

式中：WCorrected表示被正確識別是“僵尸粉”的個數；WAllspam表示樣本中是“僵尸粉”的總個數；WAll表示數據集中提取到的用戶總個數。

3.1.3 實驗結果及分析∑

實驗將α從0 開始緩慢的增加，在每個α下計算準確率、召回率、F值，得出的結果如圖4 所示。由圖可知，在本文模型中，即使是營銷類的“僵尸粉”自己所發布微博的重復率也比較低，在整體上其影響不如轉發的微博，這是因為該類用戶往往是營銷機構為了擴大傳播能力而注冊的小號，該類帳戶往往是以轉發其他有需求的營銷帳號的微博為主。統計結果表明，當α=0.14時，F值為最大，等于0.933。

圖4 不同的參數α 取值下算法的評價效果

為了評估算法性能，將ASDM 模型與張艷梅等[24]提出的SVM 算法和張錫英等[25]提出的Naive Bayes 算法進行對比，其結果如圖5 所示。ASDM模型分類準確率超過了94%，其性能優于其他算法。在識別“僵尸粉”實驗中，ASDM 模型的綜合性能更好。

圖5 ASMD、SVM 及Naive Bayes 對比實驗

3.2 TP-SRW 算法實驗與結果分析

為了驗證算法有效性，本文首先對已有的數據集進行處理，將數據集中每一位用戶的微博文本歸集到1 篇文檔，用LDA 主題模型對上述文檔進行主題分析，統計出數據集中用戶的主題偏好。本文選取比例前四的主題：科技(16.63%)、娛樂(15.36%)、旅游(13.29%)、軍事(12.5%)去評價TP-SRW 算法的性能。

3.2.1 參數設置和評價指標

TP-SRW 算法有2 個評估有影響力用戶挖掘效果的指標：肯德爾等級相關系數（Kendall Tau Correlation）[26]和覆蓋度[27]。肯德爾等級相關系數是用來度量2 個隨機變量是否具有相關性。在真實的社交網絡中，一方面影響力不會僅僅介于直接交互的鄰居用戶間，另一方面影響力隨著路徑的增大將會逐漸減弱；因此，本文將單步覆蓋度和全路徑覆蓋度做平均，其平均值作為對有影響力用戶挖掘效果的初始評估指標。

TP-SRW 算法引入了重啟的隨機游走。其重啟概率的大小會影響節點隨機游走的狀態。重啟概率值越大，節點隨機游走過程中回到初始節點的概率也就越大，結果會更偏向于距離近的節點。通過對比不同的重啟概率值對實驗結果的影響，發現當重啟概率等于0.65 時，該算法的效果最好。

3.2.2 算法實驗結果與分析

為了驗證TP-SRW 算法在不同的主題下識別有影響力用戶的有效性，將其與Twitter rank 算法[12]、Inf luence rank 算法[28]以及Leader rank 算法[29]進行實驗與對比。

由于微博從發布到消亡有一個過程，本文利用覆蓋度指標去評判識別出的有影響力用戶在一定時間內影響的人數。對發帖后的2、8、24、48 h 的情況進行實驗，圖6 和圖7 給出前20 和前50 個有影響力的用戶的覆蓋度。其結果表明： TP-SRW 算法性能優于Twitter rank 算法、Inf luence rank 算法以及Leader rank 算法。Leader rank 算法沒有考慮粉絲質量，粉絲中的大量發送垃圾廣告的營銷類“僵尸粉”的存在會對用戶影響力的評估造成一定的負面影響。Twitter rank 方法在計算用戶的影響力時把重點放到用戶發微博頻次上，沒有考慮用戶和用戶之間的互動，這同樣影響到用戶的影響力。TP-SRW 算法綜合考慮了粉絲質量及用戶和用戶之間的互動關系。

圖6 排名前20 的有影響力用戶的影響力覆蓋度

圖7 排名前50 的有影響力用戶的影響力覆蓋度

4 結論

本文研究了監督的隨機游走，并將鏈路預測的方法用到影響力用戶發現上。根據用戶的微博愛好，構建用戶的興趣偏好概率矩陣，計算用戶與用戶之間的相似度，然后給出了邊權重參數的訓練，針對給定一組有影響力的節點和一組沒有影響力的節點，采用最優化的方法并結合邊和節點的特征去指導隨機游走，發現更有影響力的節點。

在“僵尸粉”識別的實驗中，首先進行數據的標注，然后進行訓練，最后在測試集上進行測試，并和其他算法做了對比。在有影響力用戶發現實驗中，著重對比了不同主題社區下前20 和前50 的有影響力用戶發布微博的覆蓋率。其結果表明，TPSRW 算法的性能更好。在下一步工作中，將考慮話題熱度和粉絲的真實性等因素，以期進一步提高TP-SRW 算法的性能。