基于行為權(quán)值的微博用戶影響力度量算法

黎明，文海英，楊杰，陳旭日

湖南科技學(xué)院計(jì)算機(jī)系，湖南永州 425199

◎數(shù)據(jù)庫、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)◎

基于行為權(quán)值的微博用戶影響力度量算法

黎明，文海英，楊杰，陳旭日

湖南科技學(xué)院計(jì)算機(jī)系，湖南永州 425199

用戶影響力度量是目前微博研究的基礎(chǔ)和熱點(diǎn)方向，為了提高微博傳播影響力度量的準(zhǔn)確性，提出一種基于行為權(quán)值的微博用戶影響力度量算法。對(duì)網(wǎng)絡(luò)用戶的轉(zhuǎn)發(fā)、評(píng)論和提及等行為進(jìn)行分析，將數(shù)據(jù)輸入到最小二乘支持向量機(jī)中進(jìn)行學(xué)習(xí)找到最合理的權(quán)值，并建立傳播影響力度量模型，采用具體數(shù)據(jù)對(duì)算法的性能進(jìn)行仿真測試。結(jié)果表明，相對(duì)于其他微博用戶影響力度量算法，該算法不僅提高了微博用戶影響力的度量準(zhǔn)確性，而且可以準(zhǔn)確刻畫各種用戶行為對(duì)網(wǎng)絡(luò)傳播力貢獻(xiàn)。

微博用戶；最小二乘支持向量機(jī)；傳播影響力；用戶行為；影響覆蓋率

1 引言

隨著Internet的迅速發(fā)展，微博作為一種新興的社交媒體，吸引人們的廣泛學(xué)者，微博不僅是個(gè)人自我表達(dá)、獲取信息的工具，還逐漸發(fā)展成為政府、企業(yè)、組織用于信息發(fā)布、公關(guān)營銷的手段[1-2]。用戶影響力度量是目前微博研究的基礎(chǔ)和熱點(diǎn)方向，其可以對(duì)輿情事件發(fā)酵、商家的產(chǎn)品推介等具有十分重要意義[3-4]。

當(dāng)前微博網(wǎng)絡(luò)用戶影響力度量方法主要有：（1）文獻(xiàn)[5]將好友數(shù)量作為影響力度量指標(biāo)，提出了一種基于UserRank的用戶影響力度量模型。（2）將用戶轉(zhuǎn)發(fā)、評(píng)論、提等行為作為影響力度量指標(biāo)，提出了基于用戶行為的度量模型[6]。（3）將PageRank和用戶行為進(jìn)行組合，提出了基于TURank的用戶影響力度量模型[7]；文獻(xiàn)[8]將用戶轉(zhuǎn)發(fā)行為作為度量指標(biāo)，提出一種基于WeiboRank的用戶影響力度量模型；文獻(xiàn)[9]綜合考慮了用戶發(fā)表微博活躍度和PageRank算法，提出了基于Behavior-Relationship Rank的用戶影響力度量模型。（4）文獻(xiàn)[10]提出了基于URL追蹤的用戶影響力度量模型，這些研究結(jié)果表明，將PageRank和用戶行為相結(jié)合，可以比較客觀、合理地對(duì)用戶影響力進(jìn)行度量，但是它們只考慮單一用戶行為、或者用戶之間的好友關(guān)系，但是在實(shí)際應(yīng)用中，一些好友關(guān)系對(duì)用戶影響力沒有什么影響，如僵尸粉絲，而用戶的轉(zhuǎn)發(fā)、評(píng)論和提及等行為對(duì)于微博傳播作用相對(duì)較大，因此需要對(duì)用戶行為進(jìn)行全面分析，才能夠建立客觀、準(zhǔn)確的用戶影響力度量模型[2，11]。

為了提高微博用戶影響力的度量準(zhǔn)確性，提出基于一種基于行為權(quán)值的微博用戶影響力度量算法。首先對(duì)網(wǎng)絡(luò)用戶的轉(zhuǎn)發(fā)、評(píng)論和提及等用戶行為進(jìn)行分析，然后采用最小二乘支持向量機(jī)（Least Squares Support Vector Machine，LSSVM）合理確定他人權(quán)值，建立傳播影響力度量模型，最后采用具體數(shù)據(jù)對(duì)模型性能進(jìn)行仿真測試。

2 微博影響力的度量指標(biāo)分析

在微博傳播過程中，主要通過用戶交互行為描述微博影響力強(qiáng)弱，用戶的發(fā)布、分享等行為也有一定的影響作用，同時(shí)，他人的微博轉(zhuǎn)發(fā)、評(píng)論等行為也對(duì)信息傳播起著推動(dòng)作用。如果一條微博信息被轉(zhuǎn)發(fā)越多，那么其影響力更強(qiáng)，這樣，一條微博信息發(fā)出后，轉(zhuǎn)發(fā)、評(píng)論和提及等行為形成一個(gè)影響人群范圍，因此這些行為可以作為用戶影響力的度量標(biāo)準(zhǔn)，具體如圖1所示。

圖1 微博的信息傳播方式

對(duì)于不同用戶行為，它們?cè)谡麄€(gè)網(wǎng)絡(luò)人群中所占比例不同，為此可采用覆蓋率F描述為用戶的傳播能力，用戶ui覆蓋率定義如下：

式中，N為網(wǎng)絡(luò)中所有節(jié)點(diǎn)數(shù)；Rc、Cc、Mc分別表示用戶轉(zhuǎn)發(fā)、評(píng)論、提及所覆蓋的人群數(shù)。

3 PageRank算法及存在的不足

在當(dāng)前Internet中，PageRank是一種基于網(wǎng)絡(luò)圖的網(wǎng)頁排名算法，其基本思想是將網(wǎng)頁之間的鏈接看作是一種投票行為，重要網(wǎng)頁的選票要比一般網(wǎng)頁的價(jià)值高，一個(gè)網(wǎng)頁選票越多，就表示其越重要，設(shè)Pi為一頁面，O(Pi)和I(Pi)分別為其鏈出、鏈入的鏈接個(gè)數(shù)，d為阻尼系數(shù)，d的取值一般為0.15，那么Pi的PR值計(jì)算方式為[12]：

在微博信息傳播過程中，將每個(gè)用戶類可以看作一個(gè)網(wǎng)頁，將用戶粉絲和用戶關(guān)注對(duì)象分別看作鏈入和鏈出的網(wǎng)頁，這樣，就可以采用PageRank算法對(duì)用戶影響力進(jìn)行分析，然而PageRank算法存在以下不足：

（1）粉絲數(shù)和用戶影響力之間的關(guān)系難以準(zhǔn)確描述用戶影響力，特別是粉絲中包含有大量的對(duì)戶影響力起著反作用的僵尸粉絲時(shí)，準(zhǔn)確性比較低，因此不能將這部分粉絲作為用戶的鏈入網(wǎng)頁，因此，本文采用用戶活躍度這個(gè)指標(biāo)對(duì)用戶粉絲進(jìn)行篩選。假設(shè)在微博數(shù)據(jù)時(shí)間段T內(nèi)，微博用戶ui發(fā)表的原創(chuàng)、轉(zhuǎn)發(fā)、評(píng)論微博數(shù)為Sum(ui)，則用戶ui的活躍度uia定義為：

如果一個(gè)用戶的活躍度低于事先設(shè)定的閾值，那用該用戶就要剔除掉，則將用戶ui剩下粉絲的集合記為Fo(ui)。

（2）由于用戶個(gè)人原因，添加了一些關(guān)注對(duì)象，但是其沒有對(duì)關(guān)注對(duì)象的微博信息進(jìn)行過轉(zhuǎn)發(fā)、評(píng)論或提及等行為，表明該用戶對(duì)該條微博信息傳播沒有任何貢獻(xiàn)，那么該對(duì)象應(yīng)該被篩選掉。設(shè)微博用戶ui轉(zhuǎn)發(fā)、評(píng)論記錄以及提及中包含的關(guān)注對(duì)象集合記分別為UiR、UiC、UiM，那么用戶最終的關(guān)注對(duì)象集合Fe(vj)為：

4 本文的微博傳播影響力度量算法

為了解決傳統(tǒng)PageRank算法存存的缺陷，提高微博傳播影響力的度量準(zhǔn)確性，提出一種基于行為權(quán)值分配的微博用戶影響力度量算法，其可以表示為：

式中，F(xiàn)o(ui)為用戶ui最終粉絲集合；ui、vj為微博用戶；Bw(ui，vj)是分配給用戶ui的比例因子，PR(ui)為用戶ui的PR值。

通過用戶的轉(zhuǎn)發(fā)、評(píng)論、網(wǎng)絡(luò)行為可以構(gòu)造3個(gè)有向權(quán)值的網(wǎng)絡(luò)。設(shè)節(jié)點(diǎn)為V，邊為E，邊權(quán)為R，那么轉(zhuǎn)發(fā)網(wǎng)絡(luò)就可以表示為：GR(V，E，R)，權(quán)值Rji表示vj對(duì)ui的轉(zhuǎn)發(fā)貢獻(xiàn)，在微博數(shù)據(jù)獲取時(shí)間內(nèi)，ui發(fā)布的微博總數(shù)為n，tjk表示vj對(duì)ui的第k條微博的轉(zhuǎn)發(fā)情況，其計(jì)算公式為：

相應(yīng)的Rji計(jì)算為：

用戶vj轉(zhuǎn)發(fā)網(wǎng)絡(luò)的工作過程如圖2所示，在圖中，實(shí)心圓圈為vj的Fe(vj)，兩個(gè)節(jié)點(diǎn)之間如果不存在邊連接，那么表示vj對(duì)另一個(gè)節(jié)點(diǎn)沒有轉(zhuǎn)發(fā)行為。

圖2 微博的轉(zhuǎn)發(fā)過程

對(duì)于評(píng)論和提及網(wǎng)絡(luò)來說，它們與轉(zhuǎn)發(fā)過程十分相似，設(shè)Cji、Mji分別表示評(píng)論和提及權(quán)值。構(gòu)建了3個(gè)不同的有向權(quán)值網(wǎng)絡(luò)后，將它們進(jìn)行合并，最后得到一個(gè)反映微博用戶影響力的網(wǎng)絡(luò)，具體如圖3所示。

圖3 三個(gè)單一網(wǎng)絡(luò)合并過程

在網(wǎng)絡(luò)合并過程中，由于轉(zhuǎn)發(fā)、評(píng)論和提及等用戶行為對(duì)微博傳播影響力的貢獻(xiàn)是不一樣的，因此需要給它們賦予不同權(quán)值，設(shè)權(quán)值為W(ui，vj)，則有：

式中，用α、β、γ分別表示轉(zhuǎn)發(fā)、評(píng)論、提及的貢獻(xiàn)程度。

綜合上述可知，在微博用戶影響力度量模型中，α、β、γ的確定至關(guān)重要，在實(shí)際情況中，一條微博信息的轉(zhuǎn)發(fā)、評(píng)論和提及行為具有很大的偶然性，α、β、γ之間不是一種典型的線性關(guān)系，因此本文采用支持向量機(jī)確定α、β、γ的大小。對(duì)第j條微博信息，轉(zhuǎn)發(fā)、評(píng)論、提取影響人次分別為Rnij、Cnij、Mnij，那么對(duì)于n條微博信息，共獲得n個(gè)樣本，將Rnij、Cnij、Mnij作為樣本的輸入向量，α、β、γ作為輸出，通過LSSVM學(xué)習(xí)建立微博傳播影響力度量模型。LSSVM的回歸方程為：

通過引入拉格朗日乘子求解該具有等式約束的二次規(guī)劃的問題，即有：

對(duì)公式（9）進(jìn)行優(yōu)化，即令w，b，ek，αk的偏導(dǎo)數(shù)均等于0[13]。

因此，式（9）的分解可以通過解式（12）和（13）獲得，LSSVM回歸函數(shù)為：

采用RBF徑向基函數(shù)作為核函數(shù)，其定義如下：

5 仿真實(shí)驗(yàn)

5.1 數(shù)據(jù)來源

為了測試本文微博度量算法的有效性和優(yōu)越性，在CPU Intel酷睿2雙核E8600，4 GB RAM，window s XP的計(jì)算機(jī)上，采用SQL Server2005和Matlab 2012編程，選擇新浪微博“時(shí)事評(píng)論”的微群進(jìn)行仿真實(shí)驗(yàn)。新浪微博數(shù)據(jù)主要包含了三類信息：（1）用戶信息：用戶ID、粉絲數(shù)、微博數(shù)；（2）微博信息：微博數(shù)、轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)、提及數(shù)；（3）關(guān)系信息：轉(zhuǎn)發(fā)列表、評(píng)論列表、提及列表。數(shù)據(jù)采集與預(yù)處理流程圖如圖4所示。

圖4 數(shù)據(jù)處理流程

對(duì)采集的數(shù)據(jù)進(jìn)行處理，將構(gòu)造轉(zhuǎn)發(fā)、評(píng)論、提及三個(gè)網(wǎng)絡(luò)，三個(gè)網(wǎng)絡(luò)的特征見表1。

表1 3個(gè)網(wǎng)絡(luò)的數(shù)據(jù)

5.2 對(duì)比算法

采用3個(gè)單獨(dú)立網(wǎng)絡(luò)和常用微博用戶影響力度量算法（TURank）進(jìn)行對(duì)比分析，它們具體為：單一評(píng)論度量算法（Followers）；單一轉(zhuǎn)發(fā)度量算法（Retweets）；單一被提及度量算法（Attenders）；TURank算法：通過構(gòu)造基于鏈接分析的用戶-內(nèi)容（User-Tweet Graph）來計(jì)算得分進(jìn)行用戶排名[14]。TURank算法的實(shí)現(xiàn)流程如圖5所示。

圖5 TURank算法的工作流程

5.3 結(jié)果與分析

采用上述幾個(gè)算法對(duì)用戶影響力進(jìn)行度量，然后根據(jù)度量結(jié)果進(jìn)行排序，選擇影響力前十名的用戶影響人次覆蓋率進(jìn)行對(duì)比，各算法的結(jié)果如圖6所示。從圖6可以得到如下結(jié)論：

（1）相對(duì)于TURank算法，本文算法的度量準(zhǔn)確性更高，與真實(shí)用戶影響人次變化曲線十分接近。

（2）相對(duì)于單一特征的微博用戶影響力度量模型，本文算法的度量準(zhǔn)確性大幅度提高。

對(duì)比結(jié)果表明本文算法綜合考慮用戶的轉(zhuǎn)發(fā)、評(píng)論、網(wǎng)絡(luò)行為，可以比較全面地描述微博用戶影響力變化趨勢，同時(shí)通過LSSVM確定權(quán)值，可以準(zhǔn)確地描述用戶的轉(zhuǎn)發(fā)、評(píng)論、網(wǎng)絡(luò)行為對(duì)度量結(jié)果的貢獻(xiàn)，能夠更加準(zhǔn)確客觀地反映用戶影響力排名，而單一特征或者其他算法難以建立準(zhǔn)確描述用戶影響力的度量模型，度量準(zhǔn)確性低，沒有什么實(shí)用價(jià)值。

6 結(jié)束語

微博作為一個(gè)近年來興起的在線社會(huì)網(wǎng)絡(luò)，既具有媒體傳播特性，又具有社交網(wǎng)絡(luò)特性，引起了人們廣泛的關(guān)注，為了更加準(zhǔn)確度量微博用戶的傳播影響力，提出了一種基于行為權(quán)值分配的微博用戶影響力度量算法，并通過仿真對(duì)比實(shí)驗(yàn)測試其性能。結(jié)果表明，本文算法可以準(zhǔn)確描述各種用戶行為對(duì)網(wǎng)絡(luò)傳播力影響，提高了微博用戶影響力的度量準(zhǔn)確性，具有廣泛的應(yīng)用前景。

圖6 不同算法的性能對(duì)比

[1]Kwak H，Lee Changhyun，Park H，et al.What is Twitter，a social network or a new s media[C]//Proceedings of the 19th International Conference on World Wide Web. New York：ACM Press，2010：591-600.

[2]Weng Jianshu，Lim Eepeng，Jiang Jing，et al.Twitter rank：finding topic-sensitive influential Twitter[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data mining.New York：ACM Press，2010：261-270.

[3]Ye Shaozhi，Wu Felix.Measuring message propagation and social influence on Twitter.com[C]//SocInfo’10，2010：216-231.

[4]Lee Changhyun，Kwak H，Park H，et al.Finding influential based on temporal order of information adoption in Twitter[C]//Proceedings of the 19th International Conference on World Wide Web.New York：ACM Press，2010：1137-1138.

[5]馬雯雯，魏文晗，鄧一貴，等.基于隱含語義分析的微博話題發(fā)現(xiàn)方法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（1）：96-100.

[6]李軍，陳震，黃霽崴.微博影響力度量研究[J].信息網(wǎng)絡(luò)安全，2012，27（3）：10-13.

[7]袁毅.微博客信息傳播結(jié)構(gòu)、路徑及其影響因素分析[J].圖書情報(bào)工作，2011，55（12）：26-30.

[8]鐘帥.基于粒子群算法的微博用戶影響力研究[D].武漢：華中科技大學(xué)，2012.

[9]楊長春，俞克非，葉施仁，等.一種新的中文微博社區(qū)博主影響力的度量方法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（25）：229-233.

[10]吳陳鶴，杜友田，蘇暢.有限節(jié)點(diǎn)驅(qū)動(dòng)的微博社會(huì)網(wǎng)絡(luò)話題推薦方法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（15）：141-146.

[11]苑衛(wèi)國，劉云，程軍軍，等.微博雙向“關(guān)注”網(wǎng)絡(luò)節(jié)點(diǎn)中心性及傳播影響力的分析[J].物理學(xué)報(bào)，2013，62（3）：38901-38910.

[12]郭浩，陸余良，王宇，等.基于信息傳播的微博用戶影響力度量[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2012，47（5）：78-83.

[13]田海梅，黃楠.基于ACO-LSSVM的網(wǎng)絡(luò)流量預(yù)測[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（1）：91-95.

[14]Yuto Yamaguchi.TURank：Twitter user ranking based on user-tweet graph analysis[C]//W ISE，2010：243-246.

LI M ing,WEN Haiying,YANG Jie,CHEN Xuri

Department of Computer Science,Science and Technology Institute of Hunan,Yongzhou,Hunan 425199,China

Information diffusion and influence modeling are hot topics in micro-blog research, in order to improve measure precision of micro-blog spreading influence, a novel measuring algorithm of micro-blog spreading influence is proposed in this paper. The retweet, comment, mention are analyzed, and then the data are input to least squares support vector machine to obtain weight values, and establish spreading influence measure model, the simulation experiment is carried out to test the model performance. The simulation results show that, compared with other measure algorithms, the proposed algorithm not only improves the measure precision accuracy of micro-log spreading influence, but also can be more accurately portray various user behavior on spreading influence.

micro-blog users; least squares support vector machine; spreading influence; user behavior; effect coverage rate

LI M ing,W EN Haiying,YANG Jie,et al.Measuring user in fluence of m icro-b log based on behavior weigh t.Computer Engineering and Applications,2014,50（17）：130-133.

A

TP391

10.3778/j.issn.1002-8331.1402-0110

湖南省自然科學(xué)基金（No.11JJ6065）；湖南省科技廳項(xiàng)目（No.2012FJ3051）；湖南省教育廳項(xiàng)目（No.12C0681）。

黎明（1974—），講師，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全、系統(tǒng)架構(gòu)；文海英（1972—），副教授，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚?、知識(shí)發(fā)現(xiàn)與知識(shí)工程、軟件工程；楊杰（1976—），副教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全、人工智能及數(shù)據(jù)挖掘；陳旭日（1971—），副教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、分布式系統(tǒng)。

2014-02-17

2014-05-13

1002-8331（2014）17-0130-04