唐明偉，高振偉,2，王彥婷，王 鎮(zhèn)，鄧加鈺，陳曉亮

（1.西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都 610039；2.中電科大數(shù)據(jù)研究院，貴州 貴陽(yáng) 550022）

隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)社交平臺(tái)（如微博等）的出現(xiàn)改變了人們的生活。興趣愛(ài)好類(lèi)似的個(gè)體之間會(huì)相互關(guān)注。個(gè)體間的交互也較大地影響著網(wǎng)絡(luò)的拓?fù)潢P(guān)系。基于用戶的行為特征去判斷其影響力是熱點(diǎn)研究?jī)?nèi)容之一?；谖⒉┑纳缃魂P(guān)系特性，挖掘信息的發(fā)送者，尤其是具有很大影響力的關(guān)鍵核心用戶是非常重要的。但是，大量的“僵尸粉”充斥著微博，依據(jù)粉絲數(shù)等特征不能有效地判斷該用戶的真實(shí)影響力。剔除微博中的“僵尸粉”，挖掘該用戶的真實(shí)影響力，具有重要的現(xiàn)實(shí)意義。網(wǎng)絡(luò)結(jié)構(gòu)和文本信息是識(shí)別有影響力用戶的重要因素。

1 相關(guān)工作

基于隨機(jī)游走思想的PageRank 算法已在社交網(wǎng)絡(luò)得到廣泛研究。該算法為節(jié)點(diǎn)分配代表其重要性的數(shù)值，測(cè)算每個(gè)節(jié)點(diǎn)值，并確定網(wǎng)絡(luò)的結(jié)構(gòu)?；谖⒉┑膫€(gè)體特征及其行為特征，原野等[1]使用博文的規(guī)則和互動(dòng)量計(jì)算公式，提出了基于MapReduce 和Spark 的并行計(jì)算框架?；谟脩舻姆劢z數(shù)與其所發(fā)布的相關(guān)信息傳播擴(kuò)散速度的正相關(guān)性，Kwak 等[2]利用Twitter 社交網(wǎng)絡(luò)和PageRank 變形提出了TunkRank 算法。Romero 等[3]分析了被影響的用戶數(shù)和沒(méi)有被影響的用戶數(shù)，得出影響力是建立在粉絲被動(dòng)性及關(guān)注者積極性上的結(jié)論。Mao 等[4]采用一種基于學(xué)習(xí)的方法來(lái)分析和測(cè)算用戶的社會(huì)影響力，進(jìn)而判斷用戶傳播信息的能力。Agarwal 等[5]根據(jù)博文的評(píng)論、內(nèi)容、互動(dòng)程度及外部鏈接等特征對(duì)博客用戶影響力進(jìn)行全面評(píng)估與分析。Zhang 等[6]基于用戶評(píng)論等交互行為，計(jì)算在不同時(shí)段用戶的影響強(qiáng)弱。Huang 等[7]將PageRank 算法應(yīng)用到用戶活動(dòng)特征中來(lái)評(píng)價(jià)微博用戶的影響力。Tang 等[8]研究和分析了用戶的會(huì)話內(nèi)容等特征，采用加權(quán)的社會(huì)網(wǎng)絡(luò)來(lái)評(píng)估用戶的顯式和隱式影響力。基于用戶的活動(dòng)因素、歷史關(guān)注和微博的傳播力因素，Chen 等[9]提出了一種用戶影響力排名算法。通過(guò)用戶之間存在的交互程度，Sheikhahmadi 等[10]提出了一種在社交網(wǎng)絡(luò)中識(shí)別有影響力用戶的方法。Wang 等[11]提出了一種基于情緒一致性的算法來(lái)查找Topk有影響力的用戶。

文本內(nèi)容是被用來(lái)評(píng)估用戶影響力的因素之一。根據(jù)主題敏感程度和用戶的互動(dòng)等，Weng 等[12]分析用戶和鏈接關(guān)系的局部相似性提出TwitterRank算法。Xiao 等[13]基于特征的共現(xiàn)詞檢測(cè)標(biāo)簽去檢測(cè)新聞主題相關(guān)的用戶社區(qū)，并分別從轉(zhuǎn)發(fā)和提及2 方面對(duì)主題社區(qū)下的活躍用戶影響力進(jìn)行了評(píng)估。Li 等[14]提出一種基于在線學(xué)習(xí)社區(qū)的混合框架的意見(jiàn)領(lǐng)袖發(fā)現(xiàn)算法。從用戶內(nèi)容中提取主題以及利用主題之間的分布相似性，Pal 等[15]提出了使用主題建模的方法去判斷用戶影響值大小。結(jié)合不同主題下的影響力的傳播模型（TAP），Hu 等[16]通過(guò)綜合分析當(dāng)前網(wǎng)絡(luò)拓?fù)浜退泄?jié)點(diǎn)的主題分布，構(gòu)建了基于主題因子的傳播模型（TFG）。融合主題模型和影響力，Bi 等[17]提出了一個(gè)比潛狄利克雷分配模型（LDA）更復(fù)雜的混合模型（FLDA模型）。根據(jù)用戶對(duì)話題的情感極性，Eliacik 等[18]提出了一種在社交網(wǎng)絡(luò)中計(jì)算影響力用戶的算法。Backstrom 等[19]提出了基于監(jiān)督的隨機(jī)游走（supervised random walks，SRW）算法。

研究者常常更注重依賴網(wǎng)絡(luò)結(jié)構(gòu)去發(fā)現(xiàn)有影響力的用戶，但是微博社交平臺(tái)有影響力的用戶通常只擅長(zhǎng)某一領(lǐng)域，也只會(huì)影響具有相似度高的一批用戶；因此，本文將鏈路預(yù)測(cè)的方法應(yīng)用到有影響力用戶檢測(cè)中，提出了基于用戶主題偏好的監(jiān)督的隨機(jī)游走算法（topic preferences supervised random walks，簡(jiǎn)稱(chēng)TP-SRW）。

2 基于用戶主題偏好的監(jiān)督隨機(jī)游走算法（TP-SRW 算法）

2.1 監(jiān)督隨機(jī)游走

基于用戶主題偏好的監(jiān)督隨機(jī)游走的模型框架如圖1 所示。由于無(wú)監(jiān)督隨機(jī)游走的不確定性，因此本文在隨機(jī)游走的基礎(chǔ)上加上監(jiān)督的方式去指導(dǎo)游走節(jié)點(diǎn)進(jìn)行游走。它巧妙地融合了網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)和邊的特征，使游走的節(jié)點(diǎn)更加傾向于目的節(jié)點(diǎn)。

重啟隨機(jī)游走是隨機(jī)游走的一種改進(jìn),當(dāng)將要進(jìn)行下一步轉(zhuǎn)移時(shí)有2 種選擇：根據(jù)狀態(tài)轉(zhuǎn)移矩陣以一定的概率隨機(jī)地選擇下一個(gè)節(jié)點(diǎn)；以一定的概率回到初始節(jié)點(diǎn)重新開(kāi)始游走。

圖1 基于用戶主題偏好的監(jiān)督隨機(jī)游走模型

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

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

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

2.3 微博用戶主題相似度計(jì)算

在微博社區(qū)中，同質(zhì)性代表具有相同或者相似興趣愛(ài)好的用戶。當(dāng)一個(gè)用戶發(fā)表了1 篇微博，與該用戶具有同質(zhì)性的用戶會(huì)對(duì)該微博產(chǎn)生興趣，行為上主要體現(xiàn)在對(duì)該微博進(jìn)行轉(zhuǎn)發(fā)、評(píng)論、回復(fù)、點(diǎn)贊等操作。因此，可以根據(jù)用戶的微博文本的主題相似度來(lái)衡量用戶的同質(zhì)性，再依據(jù)排序算法，對(duì)某一特定主題下具有同質(zhì)性的用戶進(jìn)行排序，進(jìn)而找出特定主題下有影響力的用戶。

本文將每個(gè)微博用戶所有發(fā)表、轉(zhuǎn)發(fā)和評(píng)論的內(nèi)容歸集到1 篇文檔中，然后用2.2 節(jié)的LDA主題模型進(jìn)行分類(lèi)，并將分類(lèi)結(jié)果保存在用戶-主題偏好矩陣D中。準(zhǔn)確來(lái)說(shuō)，給定所有用戶的主題分布，通過(guò)計(jì)算相應(yīng)主題的概率分布來(lái)計(jì)算用戶所發(fā)微博、回復(fù)、評(píng)論所形成的文檔之間的相似度。

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

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

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

2）用戶主題相似度計(jì)算。主題相似度可以通過(guò)用戶對(duì)應(yīng)的主題分布的Jensen-Shannon 散度進(jìn)行計(jì)算，用 topici j表示。其中，topici j是介于0-1 的值，主題相關(guān)度越大，說(shuō)明2 個(gè)用戶感興趣主題越相似。可通過(guò)對(duì)數(shù)據(jù)進(jìn)行規(guī)范化處理，有效地提升算法魯棒性。

2.4 基于主題偏好的監(jiān)督隨機(jī)游走算法

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

監(jiān)督隨機(jī)游走算法中用到的參數(shù)最優(yōu)化問(wèn)題定義為

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

在學(xué)習(xí)邊權(quán)重參數(shù)前，首先建立邊權(quán)重函數(shù)fw(φuv)與邊權(quán)重參數(shù)w以及主題偏好隨機(jī)游走得分p聯(lián)系。具體來(lái)說(shuō)，給定邊的權(quán)重函數(shù)和主題相似性評(píng)分求出邊的重要度auv,根據(jù)這個(gè)邊的重要度來(lái)指導(dǎo)隨機(jī)游走。

定義從節(jié)點(diǎn)u到節(jié)點(diǎn)v的轉(zhuǎn)移矩陣Q和轉(zhuǎn)移概率PQ為：

由式（9）（10）可知，主題相似度越高，邊的權(quán)重越大，轉(zhuǎn)移概率越高越容易找到更有影響力的節(jié)點(diǎn)。

在隨機(jī)游走過(guò)程中，會(huì)遇到鏈路中斷等情況，因此引入了重啟動(dòng)隨機(jī)游走機(jī)制，也就是節(jié)點(diǎn)在隨機(jī)游走過(guò)程中會(huì)以一定的概率回到初始節(jié)點(diǎn)重新開(kāi)始隨機(jī)游走，設(shè)重啟概率為γ，假設(shè)s為初始節(jié)點(diǎn)，那么

且

在網(wǎng)絡(luò)中按照轉(zhuǎn)移矩陣Q*中的概率進(jìn)行重啟動(dòng)的隨機(jī)游走，最終會(huì)達(dá)到一個(gè)穩(wěn)定的狀態(tài)，此時(shí)，每一個(gè)節(jié)點(diǎn)都能得到一個(gè)概率值，即從初始節(jié)點(diǎn)出發(fā)按照重啟隨機(jī)游走概率矩陣Q*的概率在網(wǎng)絡(luò)上游走訪問(wèn)到該節(jié)點(diǎn)的概率，此時(shí)主題偏好隨機(jī)游走概率滿足式（13）。

式（13）使節(jié)點(diǎn)的PageRank 評(píng)分pu∈p以及邊權(quán)重計(jì)算函數(shù)的fw(φuv)學(xué)習(xí)參數(shù)w通過(guò)隨機(jī)游走轉(zhuǎn)移矩陣Q聯(lián)系到一起。F(w)相對(duì)于w的梯度，為

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

輸出：最佳參數(shù)w。

step 1:選初始點(diǎn)w0，收斂誤差ε ＞0，存儲(chǔ)最近m次的迭代數(shù)據(jù)。

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

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

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

step 5:計(jì)算步長(zhǎng)ak＞0，對(duì)下面的式子進(jìn)行一維搜索。

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

step 8:計(jì)算并保持。

step 9:用two-loop recursion 算法計(jì)算rk。

step 10:k=k+1，并轉(zhuǎn)入step 3。

根據(jù)上述算法求出最佳參數(shù)向量w，計(jì)算對(duì)應(yīng)節(jié)點(diǎn)的轉(zhuǎn)移概率來(lái)進(jìn)行有影響力的用戶發(fā)現(xiàn)。TPSRW 算法如圖2 所示。

圖2 用戶主題偏好的監(jiān)督隨機(jī)游走算法偽代碼

3 TP-SRW 算法實(shí)驗(yàn)

現(xiàn)進(jìn)行僵尸粉識(shí)別ASDM 模型（advertising spammers detecting model）實(shí)驗(yàn)和有影響力用戶發(fā)現(xiàn)TP-SRW 算法（topic preferences supervised random walks）實(shí)驗(yàn)，其實(shí)驗(yàn)流程如圖3 所示。

圖3 實(shí)驗(yàn)流程圖

實(shí)驗(yàn)數(shù)據(jù)主要包括微博用戶的ID、用戶發(fā)表微博帖子內(nèi)容、用戶的關(guān)注數(shù)量和粉絲數(shù)量，以及關(guān)注轉(zhuǎn)發(fā)評(píng)論等關(guān)系信息。微博數(shù)據(jù)的獲取途徑有2 種：數(shù)據(jù)集1 利用微博爬蟲(chóng)對(duì)新浪微博平臺(tái)進(jìn)行微博數(shù)據(jù)的爬取，共爬取了6 萬(wàn)4 168 條微博數(shù)據(jù)；數(shù)據(jù)集2 來(lái)自于2016 年第五屆全國(guó)社會(huì)媒體處理大會(huì)（SMP2016）中比賽用的微博數(shù)據(jù)集，有4 萬(wàn)8 162 條微博數(shù)據(jù)。本文將數(shù)據(jù)集1 作為訓(xùn)練集，數(shù)據(jù)集2 作為測(cè)試集。

本文采用LTP 系統(tǒng)對(duì)微博短文本切詞、分詞等微博數(shù)據(jù)進(jìn)行處理[23]。

為分析用戶的主題偏好，本文把同一用戶在一定時(shí)間內(nèi)所有博文、評(píng)論以及回復(fù)集中到1 篇文檔中，然后對(duì)文檔進(jìn)行切詞、分詞處理，接著利用Mahout 機(jī)器學(xué)習(xí)平臺(tái)，采用LDA 主題模型對(duì)文檔的主題進(jìn)行分析。部分關(guān)鍵詞表示如表1 所示。

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

表1 主題對(duì)應(yīng)關(guān)鍵詞

表2 用戶相關(guān)微博的比例

3.1 “僵尸粉”識(shí)別實(shí)驗(yàn)與結(jié)果分析

3.1.1 “僵尸粉”標(biāo)注

由于“僵尸粉”的不斷變異升級(jí)，在分類(lèi)“僵尸粉”時(shí)沒(méi)有可以利用的現(xiàn)成標(biāo)注過(guò)的訓(xùn)練集，因此本文采用手工標(biāo)注的方式去標(biāo)注數(shù)據(jù)集中的僵尸粉。在度量用戶的影響力時(shí)僅僅是活躍的“僵尸粉”才會(huì)對(duì)用戶影響力產(chǎn)生影響。該類(lèi)“僵尸粉”表面上看和正常用戶是區(qū)分不開(kāi)的，但該類(lèi)用戶會(huì)轉(zhuǎn)發(fā)或者發(fā)布大量的營(yíng)銷(xiāo)類(lèi)博文；因此，本文通過(guò)二人雙盲的方式標(biāo)注用戶的微博文本。首先通過(guò)標(biāo)注的文本和垃圾微博占的比例來(lái)確認(rèn)該用戶是否為“僵尸粉”，然后分析該類(lèi)用戶在用戶屬性和行為上和正常用戶的差異性。

對(duì)于微博文本，本文采用LDA 主題模型進(jìn)行分析，統(tǒng)計(jì)出正常隨機(jī)用戶和“僵尸粉”用戶在微博文本主題上分布的差異性，其結(jié)果如表3 所示?？梢钥闯?，營(yíng)銷(xiāo)類(lèi)“僵尸粉”用戶和隨機(jī)用戶在微博文本主題分布上很有大的差異。隨機(jī)用戶中概率較高的主題為親子、旅行、生活、經(jīng)濟(jì)、政治等，而營(yíng)銷(xiāo)類(lèi)“僵尸粉”概率較高的主題多為有獎(jiǎng)抽獎(jiǎng)推廣、商品推廣、鏈接推薦、婚紗攝影推廣等。可見(jiàn)，將微博文本特征用于識(shí)別廣告類(lèi)“僵尸粉”是可行的。

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

3.1.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

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

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

3.1.3 實(shí)驗(yàn)結(jié)果及分析∑

實(shí)驗(yàn)將α從0 開(kāi)始緩慢的增加，在每個(gè)α下計(jì)算準(zhǔn)確率、召回率、F值，得出的結(jié)果如圖4 所示。由圖可知，在本文模型中，即使是營(yíng)銷(xiāo)類(lèi)的“僵尸粉”自己所發(fā)布微博的重復(fù)率也比較低，在整體上其影響不如轉(zhuǎn)發(fā)的微博，這是因?yàn)樵擃?lèi)用戶往往是營(yíng)銷(xiāo)機(jī)構(gòu)為了擴(kuò)大傳播能力而注冊(cè)的小號(hào)，該類(lèi)帳戶往往是以轉(zhuǎn)發(fā)其他有需求的營(yíng)銷(xiāo)帳號(hào)的微博為主。統(tǒng)計(jì)結(jié)果表明，當(dāng)α=0.14時(shí)，F(xiàn)值為最大，等于0.933。

圖4 不同的參數(shù)α 取值下算法的評(píng)價(jià)效果

為了評(píng)估算法性能，將ASDM 模型與張艷梅等[24]提出的SVM 算法和張錫英等[25]提出的Naive Bayes 算法進(jìn)行對(duì)比，其結(jié)果如圖5 所示。ASDM模型分類(lèi)準(zhǔn)確率超過(guò)了94%，其性能優(yōu)于其他算法。在識(shí)別“僵尸粉”實(shí)驗(yàn)中，ASDM 模型的綜合性能更好。

圖5 ASMD、SVM 及Naive Bayes 對(duì)比實(shí)驗(yàn)

3.2 TP-SRW 算法實(shí)驗(yàn)與結(jié)果分析

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

3.2.1 參數(shù)設(shè)置和評(píng)價(jià)指標(biāo)

TP-SRW 算法有2 個(gè)評(píng)估有影響力用戶挖掘效果的指標(biāo)：肯德?tīng)柕燃?jí)相關(guān)系數(shù)（Kendall Tau Correlation）[26]和覆蓋度[27]?？系?tīng)柕燃?jí)相關(guān)系數(shù)是用來(lái)度量2 個(gè)隨機(jī)變量是否具有相關(guān)性。在真實(shí)的社交網(wǎng)絡(luò)中，一方面影響力不會(huì)僅僅介于直接交互的鄰居用戶間，另一方面影響力隨著路徑的增大將會(huì)逐漸減弱；因此，本文將單步覆蓋度和全路徑覆蓋度做平均，其平均值作為對(duì)有影響力用戶挖掘效果的初始評(píng)估指標(biāo)。

TP-SRW 算法引入了重啟的隨機(jī)游走。其重啟概率的大小會(huì)影響節(jié)點(diǎn)隨機(jī)游走的狀態(tài)。重啟概率值越大，節(jié)點(diǎn)隨機(jī)游走過(guò)程中回到初始節(jié)點(diǎn)的概率也就越大，結(jié)果會(huì)更偏向于距離近的節(jié)點(diǎn)。通過(guò)對(duì)比不同的重啟概率值對(duì)實(shí)驗(yàn)結(jié)果的影響，發(fā)現(xiàn)當(dāng)重啟概率等于0.65 時(shí)，該算法的效果最好。

3.2.2 算法實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

4 結(jié)論

本文研究了監(jiān)督的隨機(jī)游走，并將鏈路預(yù)測(cè)的方法用到影響力用戶發(fā)現(xiàn)上。根據(jù)用戶的微博愛(ài)好，構(gòu)建用戶的興趣偏好概率矩陣，計(jì)算用戶與用戶之間的相似度，然后給出了邊權(quán)重參數(shù)的訓(xùn)練，針對(duì)給定一組有影響力的節(jié)點(diǎn)和一組沒(méi)有影響力的節(jié)點(diǎn)，采用最優(yōu)化的方法并結(jié)合邊和節(jié)點(diǎn)的特征去指導(dǎo)隨機(jī)游走，發(fā)現(xiàn)更有影響力的節(jié)點(diǎn)。

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