田霏霏 沈記全

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)

基于用戶影響力的微博數(shù)據(jù)提取算法

田霏霏 沈記全

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)

微博作為輿情分析中基礎(chǔ)數(shù)據(jù)的主要來源之一，如何對(duì)其進(jìn)行有效提取是數(shù)據(jù)獲取的關(guān)鍵問題。為此，提出一種基于用戶影響力的數(shù)據(jù)提取算法，以滿足輿情系統(tǒng)對(duì)數(shù)據(jù)的需求。該算法首先利用模擬登錄技術(shù)獲取用戶關(guān)系并依此構(gòu)建用戶網(wǎng)絡(luò)，再根據(jù)自主設(shè)計(jì)的用戶影響力計(jì)算方法計(jì)算出影響力，進(jìn)而建立符合微博特征的影響力最大化模型挖掘出最具傳播能力的k個(gè)節(jié)點(diǎn)，最后爬取相應(yīng)的微博數(shù)據(jù)。實(shí)驗(yàn)證明，該算法能夠有效提高獲取數(shù)據(jù)的質(zhì)量，為輿情分析提供更好的數(shù)據(jù)支持。

輿情 微博 數(shù)據(jù)獲取 用戶影響力 范圍最大化

0 引 言

微博作為大數(shù)據(jù)時(shí)代新生的網(wǎng)絡(luò)應(yīng)用形式，以建立用戶關(guān)系為基礎(chǔ)，提供了一個(gè)基于信息共享和傳播的平臺(tái)[1]。自其誕生之日起，就以其簡單的組網(wǎng)方式和強(qiáng)大的信息傳播能力吸引了大量用戶[2]。大數(shù)據(jù)背景給予微博平臺(tái)龐大的用戶群體和海量的數(shù)據(jù)，其在社會(huì)輿情的形成中起著重要作用。隨著微博持續(xù)不斷地披露出重大公共事件，其逐漸成為輿情分析的主要數(shù)據(jù)來源。

為進(jìn)行更有效的輿情分析，對(duì)基礎(chǔ)數(shù)據(jù)的質(zhì)量提出新的要求。近年來國內(nèi)外學(xué)者在微博數(shù)據(jù)提取方面做了大量研究。高凱等[3]利用模擬登錄技術(shù)結(jié)合抓包工具對(duì)數(shù)據(jù)包進(jìn)行截取和分析，爬取網(wǎng)頁鏈接和數(shù)據(jù)。陳舜華等[4]通過調(diào)用微博API接口來獲取數(shù)據(jù)信息。由于API不完全對(duì)外開放，因此該方案獲取到的數(shù)據(jù)不夠全面。廉捷等[5]將微博API與Web頁面解析技術(shù)相結(jié)合，對(duì)API調(diào)用頻率進(jìn)行合理控制實(shí)現(xiàn)了微博數(shù)據(jù)的高效獲取。該方法獲取的數(shù)據(jù)雖相對(duì)完整，但數(shù)據(jù)較原始、質(zhì)量較低。盧體廣等[6]使用一種模擬登錄的算法來完成新浪微博的認(rèn)證，通過計(jì)算優(yōu)先級(jí)構(gòu)造優(yōu)先隊(duì)列來進(jìn)行數(shù)據(jù)獲取。馬俊等[7]提出了PBF方法，該方法通過對(duì)用戶個(gè)人屬性進(jìn)行分析計(jì)算出用戶影響力。Aizawa[8]針對(duì)Binary Heaps算法進(jìn)行改進(jìn)，提出一種優(yōu)先隊(duì)列計(jì)算方法來構(gòu)造優(yōu)先隊(duì)列。Weng等[9]提出了基于PageRank原理的TwitterRank算法來計(jì)算某一用戶在某一主題內(nèi)的影響力。Phan等[10]基于Reduce Number of Comparison算法進(jìn)行改進(jìn)，在數(shù)據(jù)獲取時(shí)也進(jìn)行了優(yōu)先隊(duì)列的計(jì)算及構(gòu)造。毛佳昕等[11]通過對(duì)用戶行為特征的分析來評(píng)價(jià)用戶影響力。雖然使用文獻(xiàn)[6-11]中的方案均可獲取到用戶數(shù)據(jù)，但卻沒有將提取目標(biāo)用戶的范圍最大化[12]，忽略了用戶網(wǎng)絡(luò)中的弱連接點(diǎn)。

針對(duì)以上獲取數(shù)據(jù)質(zhì)量方面的不足，本文提出一種基于用戶影響力的微博數(shù)據(jù)提取算法來解決此問題。該算法首先構(gòu)建用戶網(wǎng)絡(luò)，再通過深入分析用戶交互行為計(jì)算用戶影響力，進(jìn)而建立影響力最大化模型挖掘出最具傳播能力的k個(gè)節(jié)點(diǎn)并提取相應(yīng)的微博數(shù)據(jù)，最終完成微博數(shù)據(jù)獲取。通過該算法可以有目的地提取數(shù)據(jù)，為輿情分析提供良好的數(shù)據(jù)來源。

1 用戶影響力計(jì)算

微博平臺(tái)中，用戶通過添加關(guān)注建立起單雙向關(guān)系，從而構(gòu)成整個(gè)用戶網(wǎng)絡(luò)。在此基礎(chǔ)之上，用戶間可進(jìn)行各種交互使信息得到傳播。定義用戶影響力來衡量用戶對(duì)信息的傳播能力：

定義1 用戶影響力[13]是微博網(wǎng)絡(luò)中用戶對(duì)他人的影響能力以及對(duì)信息的傳播能力，是以用戶交互為基礎(chǔ)的一種信息傳播能力，是用戶在社交網(wǎng)絡(luò)中重要性的體現(xiàn)。

由定義1可知影響力大的用戶可以影響到更多的人，使信息的傳播范圍更廣，更有利于輿情的產(chǎn)生。因此本文通過設(shè)計(jì)用戶影響力計(jì)算方法對(duì)影響力進(jìn)行計(jì)算，并以此為基礎(chǔ)進(jìn)行數(shù)據(jù)提取，能夠更好地滿足輿情分析的需要。

1.1PageRank算法

眾所周知的PageRank[14]算法是用來計(jì)算網(wǎng)頁重要性排名的經(jīng)典算法，在用戶影響力的計(jì)算中也被廣泛應(yīng)用。該算法利用網(wǎng)絡(luò)拓?fù)渲械逆溄雨P(guān)系來計(jì)算網(wǎng)頁的重要程度。表達(dá)式如下：

(1)

式中，Pi代表當(dāng)前頁面，L(Pj)表示從頁面Pj鏈出頁面的集合，M(Pi)是Pi的鏈入頁面集合，d是阻尼系數(shù)。計(jì)算后PageRank值越大的網(wǎng)頁越重要。由式(1)可看出，算法中頁面的影響力值是均勻地傳遞到鏈出頁面上的，忽略了各頁面間影響力的不均衡性。

1.2 用戶影響力計(jì)算方法

針對(duì)PageRank算法在影響力傳遞方面的不足，本文通過深入分析用戶交互提出用戶影響率的概念對(duì)其進(jìn)行改進(jìn)，以便更合理地分配用戶影響力，最終計(jì)算出每個(gè)用戶的影響力。用戶影響率是被關(guān)注者對(duì)關(guān)注者的影響力，是一種衡量用戶間交互能力的量，所以應(yīng)從用戶交互的角度去計(jì)算用戶影響率。

用戶交互是以用戶網(wǎng)絡(luò)為背景的，首先應(yīng)針對(duì)用戶間的單雙向關(guān)系構(gòu)建用戶網(wǎng)絡(luò)。定義G=(V,E)代表整個(gè)用戶網(wǎng)絡(luò)，V為所有用戶節(jié)點(diǎn)的集合，E代表用戶間有直接關(guān)系的邊的集合。對(duì)于vm，vn∈V，∈E，代表用戶vm關(guān)注vn，則vm稱為vn的粉絲。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都會(huì)附加該用戶的狀態(tài)信息及行為信息，分別儲(chǔ)存在PROFILES和ACTIONS文件中。其中，狀態(tài)信息包括微博數(shù)量、關(guān)鍵詞等信息，行為信息包括用戶間的轉(zhuǎn)發(fā)、評(píng)論等一系列的互動(dòng)操作信息。可通過對(duì)交互行為的分析來計(jì)算用戶影響率。通常，用戶交互行為包括微博的轉(zhuǎn)發(fā)、評(píng)論、提及(@)和私信等。在以下所有分析中，均有vi，vj∈V，vj關(guān)注vi。

1) 關(guān)注度

伴隨著粉絲微博的發(fā)布，被關(guān)注用戶的微博也一同被推送到該粉絲的微博首頁。因此粉絲關(guān)注的用戶越多，收到的推送信息就越多，從而會(huì)使某用戶的微博在數(shù)據(jù)更新迅速的微博平臺(tái)上被粉絲看到的幾率降低。定義關(guān)注度來衡量這種特殊的關(guān)系，用AS表示如下：

(2)

式中，Tweet(vi)和Tweet(vj)分別代表的是vi和vj在某時(shí)間段內(nèi)發(fā)布的微博總數(shù)，Attention(vj)代表的是用戶vj關(guān)注的用戶集合。

2) 轉(zhuǎn)發(fā)量

用戶vi發(fā)布的微博被推送到vj的首頁時(shí)，若vj對(duì)vi發(fā)布的某條微博感興趣，可對(duì)其進(jìn)行轉(zhuǎn)發(fā)操作，則該微博就被分享并推送給用戶vj的粉絲，此情況下微博的傳播范圍被擴(kuò)大。轉(zhuǎn)發(fā)量作為衡量用戶影響率的指標(biāo)之一，用FS表示如下：

(3)

式中FS(vi,vj)代表用戶vj對(duì)vi的轉(zhuǎn)發(fā)量，F(xiàn)orward(vi,vj)是用戶vj對(duì)vi轉(zhuǎn)發(fā)次數(shù)總和，F(xiàn)orward(vj)表示用戶vj對(duì)所有用戶轉(zhuǎn)發(fā)次數(shù)總和，F(xiàn)orwarded(vi)表示用戶vi被所有用戶轉(zhuǎn)發(fā)次數(shù)總和。轉(zhuǎn)發(fā)量越大，用戶vi對(duì)vj的影響也就越大。

3) 評(píng)論量

當(dāng)用戶vi的微博對(duì)vj產(chǎn)生影響時(shí)，vj也會(huì)對(duì)其進(jìn)行評(píng)論，評(píng)論越多證明該用戶對(duì)其影響越大。用CS來表示評(píng)論量：

(4)

式中，CS(vi,vj)代表用戶vj對(duì)vi的評(píng)論量，Comment(vi,vj)代表用戶vj對(duì)vi進(jìn)行評(píng)論的總次數(shù)，Comment(vj)表示用戶vj對(duì)所有用戶進(jìn)行評(píng)論的總次數(shù)，Commented(vi)表示用戶vi被所有用戶評(píng)論的總次數(shù)。評(píng)論量越大則證明用戶vj對(duì)vi越關(guān)注。

4) 提及量

@操作是微博平臺(tái)上極具特色的操作，一般出現(xiàn)在微博內(nèi)容中，表示發(fā)出者提及接收方來讀取該微博信息，是用戶交互行為的一種，該操作多出現(xiàn)在密友中。用MS表示提及量：

(5)

式中，MS(vi,vj)表示用戶vj對(duì)vi的提及量，Mention(vi,vj)為用戶vj提及vi的總次數(shù)，Mention(vj)表示用戶vj提及其他所有用戶的總次數(shù)，Mentioned(vi)表示用戶vi被所有其他用戶提及的總次數(shù)。提及量越大，信息交互越頻繁，更能夠促進(jìn)信息的傳播。

5) 私信值

私信是微博平臺(tái)新上線的功能，用戶間可以相互發(fā)送私信，體現(xiàn)了用戶間的親密和互動(dòng)的程度。用DM表示私信值如下：

(6)

式中Direct(vi,vj)代表的是用戶vi和vj的私信總次數(shù)，Direct(vj)表示用戶vj私信所有用戶的總次數(shù)，Directed(vi)表示用戶vi被所有用戶私信的總次數(shù)。

6) 關(guān)鍵詞相似度

關(guān)鍵詞集合是描述用戶擅長領(lǐng)域或話題的集合。若兩個(gè)用戶的關(guān)鍵詞有交集，表示二者有著相同的愛好，微博數(shù)據(jù)就更有可能在二者間傳播。關(guān)鍵詞數(shù)據(jù)格式為(keyword1,weight1;keyword2,weight2;…)，分別代表該用戶的關(guān)鍵詞及與之相對(duì)應(yīng)的權(quán)重。則兩個(gè)用戶的關(guān)鍵詞相似度KS表示如下：

(7)

式中，兩用戶關(guān)鍵詞集合總大小為s,wik和wjk分別代表該公共關(guān)鍵詞在兩用戶集合中相應(yīng)的權(quán)重。

7) 用戶影響力的計(jì)算

(8)

為解決不同評(píng)價(jià)指標(biāo)間量綱不同的問題，需將數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，使各指標(biāo)處于同一數(shù)量級(jí)，適合進(jìn)行綜合對(duì)比評(píng)價(jià)。因此，對(duì)IR(vi,vj)進(jìn)行線性變換，使其結(jié)果映射到[0,1]之間。

(9)

式中,INF(v)和INF(v′)分別代表用戶v和v′的影響力，IR(v,v′)和IR(v″,v′)分別代表用戶影響率。式中F(v)代表用戶v的粉絲集合，Attention(v′)代表的是用戶v′關(guān)注的用戶集合，d是阻尼系數(shù)。對(duì)式(9)進(jìn)行迭代可以求出網(wǎng)絡(luò)中所有節(jié)點(diǎn)的影響力INF。

2 影響力最大化模型設(shè)計(jì)

根據(jù)本文提出的影響力計(jì)算方法可求得各節(jié)點(diǎn)的INF值，從而得到用戶影響力的排序。INF值越大的用戶，對(duì)信息的傳播貢獻(xiàn)就越大。假設(shè)某一INF值較小的用戶A擁有INF值較大的粉絲B，此時(shí)A的微博數(shù)據(jù)可以被B在較大的范圍內(nèi)傳播。若直接選取INF排名靠前的k個(gè)節(jié)點(diǎn)作為目標(biāo)數(shù)據(jù)，很可能忽略網(wǎng)絡(luò)中的弱連接點(diǎn)，導(dǎo)致k個(gè)節(jié)點(diǎn)集中在一個(gè)簇內(nèi)，不能保證最終獲取到的用戶節(jié)點(diǎn)影響范圍最大。因此需要建立符合微博網(wǎng)絡(luò)特征的影響力最大化模型來尋找能夠影響最多用戶的節(jié)點(diǎn)。

2.1 影響力最大化定義

定義2 在已知的網(wǎng)絡(luò)G中，給出特定的影響力INF(v)來求解集合S(k)，集合大小為k。S(k)需滿足以該集合中節(jié)點(diǎn)為初始節(jié)點(diǎn)遵循影響力傳播模型進(jìn)行傳播，最終能激活節(jié)點(diǎn)數(shù)目最多。即獲取k個(gè)用戶，使其具有最大的傳播范圍。

LTM模型[15]是一種經(jīng)典的基于節(jié)點(diǎn)的傳播模型。已知社會(huì)網(wǎng)絡(luò)G=(V,E)，定義N(v)={u|(u,v)∈E}表示節(jié)點(diǎn)v在網(wǎng)絡(luò)G中的鄰居節(jié)點(diǎn)集合，buv是已激活節(jié)點(diǎn)u對(duì)它未激活鄰居節(jié)點(diǎn)v的影響力，且∑u∈N(v)buv≤1。定義N(v)中已激活節(jié)點(diǎn)集合為A(v)，每個(gè)節(jié)點(diǎn)v均有一個(gè)特異性閾值θv，在∑u∈A(v)buv≥θv的條件下節(jié)點(diǎn)v被激活。

信息擴(kuò)散步驟如下：

Step1 給定初始傳播種子集合S0，buv為節(jié)點(diǎn)u對(duì)v的影響力，θv為節(jié)點(diǎn)v被激活的閾值。

Step2 在第t步擴(kuò)散時(shí)，滿足激活條件的基于集合St-1節(jié)點(diǎn)將形成新集合St。

Step3 程序循環(huán)進(jìn)行，直到不再有新節(jié)點(diǎn)被激活。

2.2 最大化模型設(shè)計(jì)

LTM是基于節(jié)點(diǎn)的價(jià)值積累傳播模型，其中buv是通過社交網(wǎng)絡(luò)中u對(duì)v的影響權(quán)重來計(jì)算的。但在微博平臺(tái)中，當(dāng)用戶被抽象為節(jié)點(diǎn)后，各節(jié)點(diǎn)間是通過雙向交互來激活網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，最終促進(jìn)信息傳播。因此應(yīng)根據(jù)微博自身的特征設(shè)計(jì)最大化模型來滿足影響力最大化的需要。

通過本文對(duì)微博的深入分析，根據(jù)式(9)可計(jì)算出每個(gè)用戶的影響力INF。各用戶通過雙向交互對(duì)其鄰居節(jié)點(diǎn)的影響力bvv′可表示如下：

(10)

(11)

其中，V是用戶集合，S是已激活節(jié)點(diǎn)集合。由式(11)計(jì)算后選取SeedFind值最大的節(jié)點(diǎn)為初始種子節(jié)點(diǎn)。

根據(jù)上述分析，設(shè)計(jì)具有微博特征的影響力最大化模型表示如下：

Step1 根據(jù)式(9)迭代計(jì)算所得的用戶影響力INF值代入式(10)計(jì)算出傳遞概率bvv′。初始狀態(tài)集合S為空。

Step3 由式(11)計(jì)算出指標(biāo)SeedFind值。

Step4 將SeedFind值最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，以bvv′為傳遞概率進(jìn)行節(jié)點(diǎn)擴(kuò)散。

Step5 每一步擴(kuò)散都選取傳播范圍增量最大的節(jié)點(diǎn)，并將此節(jié)點(diǎn)添加到集合S中。

Step6 集合S.size=k，傳播結(jié)束。

3 算法實(shí)現(xiàn)

本文綜合微博自身特征及用戶屬性，提出一種基于用戶影響力的微博數(shù)據(jù)提取算法來提取微博數(shù)據(jù)，核心步驟如下：

Step1 采用模擬登錄技術(shù)獲取微博用戶初始數(shù)據(jù)，并對(duì)其進(jìn)行結(jié)構(gòu)化和預(yù)處理，獲得用戶關(guān)系。

Step2 構(gòu)建用戶網(wǎng)絡(luò)，同時(shí)得到PROFILES和ACTIONS兩個(gè)文件用來儲(chǔ)存用戶信息。利用式(2)-式(7)分別計(jì)算出AS(v,v′)、FS(v,v′)、CS(v,v′)、MS(v,v′)、DM(v,v′)、KS(v,v′)。

Step3 根據(jù)以上計(jì)算結(jié)果，利用式(8)計(jì)算出IR(v,v′)。

Step4 為用戶INF賦初值1/n，并對(duì)式(9)進(jìn)行迭代，依次求出網(wǎng)絡(luò)中所有用戶的影響力INF。

Step5 根據(jù)式(10)、式(11)計(jì)算出用戶的SeedFind值和傳播概率bvv′。建立基于微博特征的最大化模型，最終獲取到大小為k的用戶集合S。

Step6 根據(jù)集合S中的節(jié)點(diǎn)，應(yīng)用爬蟲技術(shù)提取相應(yīng)的微博并存儲(chǔ)，算法結(jié)束。

根據(jù)以上各步驟，將算法用偽代碼表示如下：

Input: G=(V,E),PROFILES ,ACTIONS ,c,k,θv

Output: the Top-k node set S

1: for each edge ∈E do

2: calculate AS(v,v′),FS(v,v′),CS(v,v′),MS(v,v′),DM(v,v′),KS(v,v′) respectively

3: calculate IR(v,v′)

4: end for

5: set the initial influence value to 1/n,where n is the total number of nodes

6: while (ratio > Threshold)

7: for each v in V do

8: for each v′∈F(v)

9: get the value of IR(v,v′) and INF(v′)

10: for each v″∈ Attention(v′)

11: get IR(v″,v′),then accumulate them and assign to sum

12: end for

13: INFt+1(v)+=IR(v,v′)*INFt(v′)/sum

14: end for

15: INFt+1(v)=INFt+1(v)*c+(1-c)/n

16: end for

17: ratio=max(INFt+1(v)- INFt(v))/max(INFt+1(v))

18: end while

19: for each v in V do

20: get the value of INF(v),then accumulate SeedFind(v)

21: end for

22: Order SeedFind(v) by desc,then Initialize S=φ

23: v = List[0],S = S∪{v},i=1

24: while |S|<=k

25: v = List[i]

26: while v=argmax(I(v)i- I(v)i-1)

27: S = S∪{v}

28: i ++;

29: end while

30: end while

31: return S and extract the data

算法中I(v)代表以節(jié)點(diǎn)v為種子進(jìn)行傳播所激活的節(jié)點(diǎn)集合，其中I(v)i-I(v)i-1表示當(dāng)前節(jié)點(diǎn)新加入后所激活節(jié)點(diǎn)的增量。因此該算法最終輸出大小為k的集合S中的元素都是最具傳播能力的節(jié)點(diǎn)。然后將這些用戶的微博數(shù)據(jù)提取存入數(shù)據(jù)庫，完成數(shù)據(jù)提取。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境及初始數(shù)據(jù)準(zhǔn)備

為驗(yàn)證本文提出的基于用戶影響力的微博數(shù)據(jù)提取算法的有效性，設(shè)計(jì)實(shí)驗(yàn)進(jìn)行驗(yàn)證。測試機(jī)器為Lenovo Y460服務(wù)器，Intel(R)Core(TM)i5 CPU，4 GB內(nèi)存，運(yùn)行環(huán)境為Windows 8.1平臺(tái)下的Microsoft Visual Studio 2010，使用C#語言進(jìn)行開發(fā)和實(shí)現(xiàn)。本文基于瀏覽器模擬登錄技術(shù)完成微博平臺(tái)的認(rèn)證，再通過設(shè)計(jì)爬蟲算法以得到實(shí)驗(yàn)的初始用戶數(shù)據(jù)。模擬登錄后可獲取用來識(shí)別用戶身份的cookie數(shù)據(jù)。將cookie作為訪問微博的header參數(shù)提交request給服務(wù)器，可以收到服務(wù)器的response反饋。在提交POST請(qǐng)求之前，需要GET 獲取“servertime” 和 “nonce”兩個(gè)參數(shù)的值，通過HttpFox觀察POST的數(shù)據(jù)，其中 “su”是加密后的username,“sp”是加密后的password，最終實(shí)現(xiàn)模擬登錄。認(rèn)證成功后便可爬取用戶信息，再對(duì)得到的數(shù)據(jù)進(jìn)行結(jié)構(gòu)化和預(yù)處理(過濾僵尸用戶等)即可完成初始數(shù)據(jù)的準(zhǔn)備工作。數(shù)據(jù)集描述如表1所示。

表1 數(shù)據(jù)集情況

表1顯示了實(shí)驗(yàn)獲取到的8756個(gè)用戶，以及用戶間的單雙向關(guān)系總量，將其抽象為節(jié)點(diǎn)和邊建立用戶網(wǎng)絡(luò)G=(V,E)。用戶的狀態(tài)信息和行為信息分別以JSON數(shù)據(jù)格式儲(chǔ)存在PROFILES文件和ACTIONS文件中。

4.2 實(shí)驗(yàn)評(píng)估及分析

算法通過設(shè)定比率ratio來控制收斂，該值為迭代過程中用戶影響力的增量最大值與最大值的比值。當(dāng)該比值小于已設(shè)定的門限值Threshold時(shí)終止循環(huán)。圖1顯示了實(shí)驗(yàn)過程中比率ratio隨著迭代次數(shù)增加的變化情況。

圖1 迭代次數(shù)與比率ratio變化關(guān)系圖

圖1中顯示了進(jìn)行0～100次迭代ratio值的變化情況，ratio的值隨著迭代次數(shù)的增加而不斷減小。進(jìn)行70次迭代后，ratio已經(jīng)減小到10-5數(shù)量級(jí)，已經(jīng)非常接近0，可以認(rèn)為該循環(huán)結(jié)束，因此門限值Threshold可設(shè)為10-5，即計(jì)算過程中循環(huán)進(jìn)行70次結(jié)束。迭代結(jié)束后可以計(jì)算出用戶影響力值，其分布情況如圖2所示。

圖2 INF值分布圖

圖2中顯示出實(shí)驗(yàn)數(shù)據(jù)集內(nèi)INF值的分布情況，INF較大的用戶集中在小范圍內(nèi)，更多用戶集中在INF值較小的范圍內(nèi)。為防止弱連接點(diǎn)的丟失，需進(jìn)行影響力最大化計(jì)算來擴(kuò)大影響力的范圍。提取結(jié)果數(shù)據(jù)集中INF值Top 10用戶與影響力最大化后的Top 10節(jié)點(diǎn)進(jìn)行對(duì)比說明，如表2和表3所示。

表2 用戶影響力INF值Top 10

表3 影響力最大化后微博用戶Top 10

通過對(duì)比兩表中的數(shù)據(jù)，可見INF值大的用戶與影響力范圍最大化后的節(jié)點(diǎn)集合S不完全相同，INF排名靠前的用戶不一定出現(xiàn)在集合S的Top-k中。原因是某些INF小的用戶可能擁有INF較大的粉絲，這些粉絲對(duì)當(dāng)前用戶的微博進(jìn)行轉(zhuǎn)發(fā)后，相當(dāng)于影響力較大的用戶發(fā)布了該微博，從虛擬的角度增大了當(dāng)前用戶的影響力，所以在結(jié)果集S中出現(xiàn)INF值小的新用戶，從某種程度上初步體現(xiàn)了本文算法獲取數(shù)據(jù)范圍廣的優(yōu)點(diǎn)，保證網(wǎng)絡(luò)中弱連接點(diǎn)不被忽略。

為進(jìn)一步驗(yàn)證本文算法的有效性，與PageRank算法以及TwitterRank算法進(jìn)行對(duì)比。將PageRank算法結(jié)果按降序排列并取出Top-k節(jié)點(diǎn)構(gòu)成集合P1，同理TwitterRank算法對(duì)應(yīng)集合P2，與本文算法最終輸出集合S分別對(duì)比。定義相似性分別為H1、H2：

(12)

H1、H2的計(jì)算結(jié)果如圖3所示。

圖3 相似性曲線

由圖3可看出，H1、H2隨著抓取目標(biāo)集合大小k的增大均呈現(xiàn)先下降后平穩(wěn)上升的趨勢。這是由于隨著獲取節(jié)點(diǎn)的不斷增多，弱連接點(diǎn)也隨之增多，當(dāng)一些弱連接點(diǎn)被挖出時(shí)，相似性就會(huì)相對(duì)降低；當(dāng)獲取節(jié)點(diǎn)個(gè)數(shù)持續(xù)增多時(shí)，弱連接點(diǎn)的個(gè)數(shù)由于不斷被挖掘出來而減少，此時(shí)相似性就呈現(xiàn)出穩(wěn)定增長的狀態(tài)。該對(duì)比進(jìn)一步驗(yàn)證了本文算法的正確性和獲取數(shù)據(jù)完整的優(yōu)點(diǎn)。

為驗(yàn)證本文算法獲取數(shù)據(jù)質(zhì)量高，選取本文算法(以下簡稱Our method)、PageRank算法、TwitterRank算法以及爬蟲算法(Web Spider)的實(shí)驗(yàn)結(jié)果集進(jìn)行對(duì)比。四個(gè)集合中分別選取前十個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，以bvv′為傳播概率構(gòu)成傳播模型來模擬微博數(shù)據(jù)在微博平臺(tái)上的傳播情況。在選取同樣數(shù)量種子節(jié)點(diǎn)的情況下，所激活的節(jié)點(diǎn)個(gè)數(shù)情況如圖4所示。

圖4 激活用戶節(jié)點(diǎn)個(gè)數(shù)比較

圖4中各曲線可看出，在種子集合大小一樣的情況下，四種算法激活的節(jié)點(diǎn)數(shù)都呈上升趨勢，其中爬蟲算法激活的節(jié)點(diǎn)最少，本文算法激活的節(jié)點(diǎn)最多，PageRank和TwitterRank算法則居中。這意味著本文算法獲取到的用戶對(duì)數(shù)據(jù)具有最強(qiáng)的傳播能力，可使數(shù)據(jù)傳播的范圍更廣，對(duì)輿情的形成具有更重要的意義，因此依據(jù)本文算法提取到的微博數(shù)據(jù)質(zhì)量更高。為將四種算法進(jìn)行效率對(duì)比，實(shí)驗(yàn)利用獲取相同個(gè)數(shù)節(jié)點(diǎn)所消耗的時(shí)間來評(píng)估各算法的效率。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 各算法執(zhí)行性能比較

由圖5可以看出，在獲取相同數(shù)量節(jié)點(diǎn)的情況下，爬蟲算法耗時(shí)最長，本文算法與PageRank算法耗時(shí)基本接近，TwitterRank居中。本文算法在耗時(shí)上相對(duì)于爬蟲算法和TwitterRank算法具有明顯的優(yōu)勢。由于本文需要進(jìn)行最大化計(jì)算，在保證耗時(shí)與PageRank基本相同的情況下獲取到的數(shù)據(jù)質(zhì)量更高，相對(duì)提高了數(shù)據(jù)的獲取效率。

將本文算法提取的微博數(shù)據(jù)集與PageRank算法以及TwitterRank算法獲取的用戶數(shù)據(jù)進(jìn)行對(duì)比。將三者的數(shù)據(jù)集分詞后應(yīng)用LDA模型，進(jìn)行熱門話題檢測，比較召回率、準(zhǔn)確率和F值，如表4所示。

表4 話題測評(píng)結(jié)果對(duì)比

表4中可看出，本文算法提取的數(shù)據(jù)在話題檢測中較其他兩種算法占優(yōu)勢，性能較PageRank算法提高約3.79%，較TwitterRank算法提高約1.89%。因此本文算法獲取的數(shù)據(jù)質(zhì)量更高，更能滿足輿情分析的需要。

5 結(jié) 語

本文針對(duì)輿情分析的要求提出一種基于用戶影響力的數(shù)據(jù)提取算法。通過詳細(xì)分析用戶間的雙向交互最終實(shí)現(xiàn)微博數(shù)據(jù)的有效獲取。通過設(shè)計(jì)實(shí)驗(yàn)驗(yàn)證了本文算法可以減少用戶網(wǎng)絡(luò)中弱連接點(diǎn)的丟失，保證抓取目標(biāo)數(shù)據(jù)的完整性和準(zhǔn)確性。通過與其他算法的性能對(duì)比，驗(yàn)證了本文算法可以有效提取高質(zhì)量的微博數(shù)據(jù)，為進(jìn)一步進(jìn)行輿情分析提供了良好的條件。但在算法執(zhí)行時(shí)間上應(yīng)考慮到并行化，這將是后續(xù)研究的方向。

[1] 丁兆云,賈焰,周斌.微博數(shù)據(jù)挖掘研究綜述[J].計(jì)算機(jī)研究與發(fā)展,2014,51(4):691-706.

[2] Kwak H,Lee C,Park H,et al.What is Twitter,a Social Network or a News Media?[C]//Proceedings of the 19th International Conference on World Wide Web.New York:ACM,2010:591-600.

[3] 高凱,王九碩,馬紅霞,等.微博信息采集及群體行為分析[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(10):2413-2416.

[4] 陳舜華,王曉彤,郝志峰,等.基于微博API的分布式抓取技術(shù)[J].電信科學(xué),2013,29(8):146-150,155.

[5] 廉捷,周欣,曹偉,等.新浪微博數(shù)據(jù)挖掘方案[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,51(10):1300-1305.

[6] 盧體廣,劉新,劉任任.微博數(shù)據(jù)通用抓取算法[J].計(jì)算機(jī)工程,2014,40(5):12-16,20.

[7] 馬俊,周剛,許斌,等.基于個(gè)人屬性特征的微博用戶影響力分析[J].計(jì)算機(jī)應(yīng)用研究,2013,30(8):2483-2487.

[8] Aizawa A.An information-theoretic perspective of tf-idf measures[J].Information Processing & Management,2003,39(1):45-65.

[9] Weng J,Lim E P,Jiang J,et al.TwitterRank:Finding Topic-sensitive Influential Twitterers[C]//Proceedings of the Third ACM International Conference on Web Search and Data Mining.ACM,2010:261-270.

[10] Phan X H,Nguyen L M,Horiguchi S.Learning to Classify Short and Sparse Text & Web with Hidden Topics from Large-scale Data Collections[C]//Proceedings of the 17th International Conference on World Wide Web.ACM,2008:91-100.

[11] 毛佳昕,劉奕群,張敏,等.基于用戶行為的微博用戶社會(huì)影響力分析[J].計(jì)算機(jī)學(xué)報(bào),2014,37(4):791-800.

[12] Liu Y.Influence Maximization in MicroBlog Based on a New User Influence Ranking Method[J].Journal of Information and Computational Science,2015,12(9):3729-3737.

[13] 張昊,劉功申,蘇波.一種微博用戶影響力的計(jì)算方法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(3):41-44.

[14] 平宇,向陽,張波,等.基于MapReduce的并行PageRank算法實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2014,40(2):31-34,38.

[15] 陳浩,王軼彤.基于閾值的社交網(wǎng)絡(luò)影響力最大化算法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(10):2181-2188.

MICROBLOG DATA EXTRACTION ALGORITHM BASED ON USER INFLUENCE

Tian Feifei Shen Jiquan

(CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

As one of the main sources of basic data in public opinion analysis,the microblog is a key problem in data acquisition.For this issue,a data extraction algorithm based on user influence is proposed in order to meet the needs of public opinion system for data.First,the algorithm uses the simulation login technology to obtain the user relationship and builds the user network,and then calculates the user influence with the independent design user influence calculation method in order to establish the influence of microblog features to maximize the ability of the model and dig out the mostknodes.Finally,it uses the conventional crawler technology to climb the corresponding microblog data.Experiments show that this algorithm is able to improve the quality of the data effectively and provide better data support for public opinion analysis.

Public opinion Microblog DATA acquision User influence Range maximize

2015-09-09。國家自然科學(xué)基金面上項(xiàng)目(61175066)。田霏霏，碩士生，主研領(lǐng)域：輿情分析，數(shù)據(jù)挖掘。沈記全，教授。

TP39

A

10.3969/j.issn.1000-386x.2017.01.010