謝國豪+羅浩+吳志剛+張樹壯

摘要：針對如何在高校論壇中識別出高影響力用戶的問題，提出了一種結(jié)合時間因子的論壇用戶影響力計算方法。在PageRank算法的基礎(chǔ)上，通過分析論壇用戶回帖行為隨時間變化的規(guī)律引入用戶影響力的衰減系數(shù)，并根據(jù)用戶間的交互情況，通過用戶間的交互次數(shù)和用戶主題參與度來優(yōu)化用戶影響力的分配形式。實驗結(jié)果表明：在相同時間段內(nèi)，改進后的算法相對于PageRank算法能夠識別出具有更強中心性特性和更高用戶覆蓋率的高影響力用戶。在連續(xù)時間段上，通過引入衰減系數(shù)能夠發(fā)掘當(dāng)前真正具有影響力的用戶并保持穩(wěn)定的用戶覆蓋率。

關(guān)鍵詞： 影響力； 時間因子； 衰減系數(shù)； 主題參與度； 中心性特性； 覆蓋率

中圖分類號：TP393

文獻標(biāo)碼：A

文章編號：2095-2163（2017）05-0013-04

XIE Guohao， LUO Hao， WU Zhigang， ZHANG Shuzhuang

（Institute of Network Technology， Beijing University of Posts and Telecommunications， Beijing 100876， China）

Abstract：

In order to identify high-impact users in the campus forums， an algorithm combined with time factor is proposed. Based on PageRank algorithm， the attenuation coefficient of user′s influence is introduced by analyzing the change law of user′s reply behavior， and the propotion of user′s influence assigned to others is determined by the number of interactions between users and user′s subject participation. Experimental results indicate that the improved algorithm can identify the influential users with higher centrality and user coverage ratio than PageRank algorithm in the same time period. In the continuous period of time， by introducing the attenuation coefficient， the real high-impact users can be identified and stable user coverage ratio can be maintained.

Keywords： influence； time factor； attenuation coefficient； subject participation； centrality； coverage ratio

基金項目： 家重點研發(fā)計劃資助項目（2016YFB0801200）。

收稿日期： 2017-08-27

0引言

隨著移動互聯(lián)網(wǎng)的發(fā)展和普及，在線社交網(wǎng)絡(luò)已經(jīng)深刻地影響了人們的生活方式。高校網(wǎng)絡(luò)論壇作為在線社交網(wǎng)絡(luò)的重要組成部分，憑借其以高校為背景的區(qū)域性特征以及當(dāng)今大學(xué)生思想交流活動頻繁的特性，吸引了大量師生參與到論壇交流中?？紤]到高校論壇的參與對象以及自由開放的討論空間，識別出高校網(wǎng)絡(luò)論壇中具有高影響力的用戶對于信息的傳播和引導(dǎo)具有重要的意義。

PageRank作為經(jīng)典的頁面排名算法是基于網(wǎng)頁及其鏈接構(gòu)成的全局拓撲結(jié)構(gòu)，依據(jù)網(wǎng)頁間的鏈接關(guān)系和隨機游走思想對網(wǎng)頁進行重要度計算和排序[1]。社交網(wǎng)絡(luò)與網(wǎng)頁鏈接網(wǎng)絡(luò)具有相似的拓撲結(jié)構(gòu)，用戶在社交網(wǎng)絡(luò)中活動產(chǎn)生交互關(guān)系，這種關(guān)系會隨著用戶活動而不斷累積，若直接利用PageRank算法對用戶影響力進行計算，顯然在社交網(wǎng)絡(luò)中存在時間較長的用戶有更大的可能擁有較多的鏈入關(guān)系從而獲得更高的影響力值，即使用戶之后不再產(chǎn)生任何行為，這種全局關(guān)系仍然會使用戶在影響力計算中取得較大的值而非呈現(xiàn)減弱的趨勢。同時在PageRank算法中，網(wǎng)絡(luò)拓撲中的節(jié)點平等對待其它所有節(jié)點，以平均分配的方式分配其權(quán)值從而導(dǎo)致忽略了節(jié)點之間的差異性對最后計算結(jié)果的影響。

針對以上問題，本文提出了一種結(jié)合時間因子的用戶影響力計算方法，通過收集到的高校論壇數(shù)據(jù)對算法進行了實驗和對比，驗證了改進后的算法能夠更加準確識別出具有高影響力的用戶群。

1相關(guān)工作

社會網(wǎng)絡(luò)作為一門交叉性學(xué)科，已經(jīng)被SIGKDD、WWW等多個重要的國際會議列為研究議題[2-3]，且形成了一個專門的研究方向——社會網(wǎng)絡(luò)分析（Social Network Analysis，SNA）。社會影響力排序作為社會網(wǎng)絡(luò)研究的子領(lǐng)域吸引了大量學(xué)者參與研究，不同學(xué)者從不同的角度對用戶影響力進行研究。如Zhang等人通過對網(wǎng)絡(luò)BBS構(gòu)建回復(fù)網(wǎng)絡(luò)，分析節(jié)點中心性來發(fā)現(xiàn)處于網(wǎng)絡(luò)中心位置的用戶[4]。Meeyoung Cha等人從粉絲數(shù)、轉(zhuǎn)發(fā)數(shù)、引用數(shù)這3個指標(biāo)來評定Twitter上的用戶影響力[5]。Weng等人利用社交網(wǎng)絡(luò)中用戶之間的關(guān)注關(guān)系來構(gòu)建轉(zhuǎn)發(fā)網(wǎng)絡(luò)，提出了TwitterRank算法[6]。Zhai等人通過對論壇中用戶發(fā)表內(nèi)容進行所屬興趣域的劃分來識別用戶的影響力[7]，Matsumura等人提出了IDM模型，考慮論壇帖子中關(guān)鍵詞在對話鏈中的傳遞來反映影響力[8]，Hu等人針對Twitter提出了TAP算法，根據(jù)轉(zhuǎn)發(fā)內(nèi)容與給定主題間的相似度計算用戶在給定主題下的影響力權(quán)重[9]。endprint

本文從時間維度對社交網(wǎng)絡(luò)中的用戶影響力衰減規(guī)律進行分析，并在影響力計算公式中引入衰減系數(shù)，同時通過改進PageRank算法中節(jié)點權(quán)值的分配方式來對PageRank進行優(yōu)化，以此分析用戶的影響力。

2結(jié)合時間因子的影響力計算

2.1數(shù)據(jù)集說明

本文以北郵人論壇的數(shù)據(jù)作為算法改進和實驗的基礎(chǔ)。數(shù)據(jù)主要由用戶信息和主題帖信息構(gòu)成，其中用戶信息包括參與過發(fā)帖或者回帖的用戶數(shù)目。主題帖信息包括正文和后續(xù)的跟帖內(nèi)容，以及正文和跟帖的發(fā)布時間和作者信息，同時整理出了用戶之間的交互關(guān)系。

本文收集到的數(shù)據(jù)集包含了自2004年11月份至2017年3月份的全部相關(guān)數(shù)據(jù)。具體的數(shù)據(jù)集描述如表1所示。

3實驗結(jié)果與分析

3.1評價指標(biāo)

社會網(wǎng)絡(luò)分析中普遍認為全局網(wǎng)絡(luò)中具有高影響力的節(jié)點具有高中心性，并提出以中心性測度（Centrality measures）作為判斷網(wǎng)絡(luò)中節(jié)點重要性的指標(biāo)來對節(jié)點重要性進行量化 [13]。緊密中心性（Closeness Centrality）[14]作為中心性的度量方法之一，當(dāng)節(jié)點具有更高的緊密中心性時表示該節(jié)點處于中心位置[4]并且具有更高傳遞影響的能力，刻畫了節(jié)點的全局重要性[15]。

本文以節(jié)點緊密度的大小排序作為基準排序，通過計算不同算法識別的影響力Top N用戶集合相對于基準排序的召回率來對算法進行評價。同時鑒于高影響力人物往往能夠影響更多的用戶，參考文獻[7，16]引入覆蓋率指標(biāo)（Coverage Ratio）。

3.2實驗結(jié)果分析

3.2.1單個時間段內(nèi)的結(jié)果對比

以節(jié)點緊密度為指標(biāo)，對相同時間段內(nèi)的用戶進行排序并作為基準，考察不同算法在相同時間段內(nèi)識別出的用戶集合相對基準排序的召回率，召回率越高則說明結(jié)果越接近基準排序。得到2種算法的召回率結(jié)果如圖2所示，從圖2中可知，在取相同比例Top N的用戶進行對比的前提下，TUR算法相對基準算法具有較高召回率，說明其識別的用戶群體相對于PageRank算法所識別的用戶群體具有更高的中心性。

同時，考察2種算法識別出的Top N前50%的用戶的覆蓋率。結(jié)果如圖3所示，在相同比例的Top N用戶群體中，TUR算法識別的高影響力用戶相對于PageRank算法識別的高影響力用戶具有更高的覆蓋率，表明利用TUR算法識別的用戶群所具有的影響力能夠覆蓋更多用戶，影響范圍更廣。

3.2.2連續(xù)時間段上影響力變化

本文選取了2016年1月1日到12月31日為期一年的所有數(shù)據(jù)進行研究，在該時間段上分析了排名前5%的高影響力用戶的覆蓋率變化情況。結(jié)果如圖4所示。從圖4中可以看出，利用TUR算法識別的排名前5%的用戶覆蓋率，隨著時間的發(fā)展變化波動較小，趨勢線趨于平穩(wěn)，總體保持較穩(wěn)定的覆蓋率。而利用PageRank算法所識別的排名前5%的用戶覆蓋率，隨著時間的發(fā)展整體呈下降趨勢。究其原因，TUR算法在計算公式中引入了衰減系數(shù)，通過篩選當(dāng)前時間段內(nèi)活躍用戶并淘汰長期無作為的用戶，來保持高影響力用戶群的影響覆蓋率。而在PageRank算法計算中，一些不再參與論壇活動但曾經(jīng)活躍的用戶因為之前積累了大量的交互關(guān)系仍然獲得了較大的影響力值并占據(jù)較高的排名，這些用戶不再產(chǎn)生新的交互，其影響的用戶數(shù)量始終保持不變，隨著論壇中新用戶的不斷增多從而導(dǎo)致了覆蓋率下降。說明了衰減系數(shù)的引入有助于更好地識別活躍的高影響力用戶。

4結(jié)束語

本文提出一種結(jié)合時間因子的論壇用戶影響力計算算法Time-User Rank。在PageRank算法基礎(chǔ)上結(jié)合時間因子引入影響力的衰減系數(shù)，以及通過用戶間的交互權(quán)重和用戶的主題參與度，針對PageRank算法中對節(jié)點影響力均分分配的問題做出了相關(guān)優(yōu)化。通過實驗表明，在同一個時間段內(nèi)改進后的算法相對于PageRank算法能夠識別得到具有更高的中心性特性和用戶覆蓋率的高影響力用戶群體，并且在連續(xù)時間段上能夠通過影響力衰減系數(shù)有效地挖掘出活躍且具有高影響力的用戶，使整個高影響力用戶群始終保持穩(wěn)定的用戶覆蓋率。

參考文獻：

PAGE L， BRIN S， MOTWANI R，et al. The PageRank citation ranking： Bringing order to the web[J]. World Wide Web Internet And Web Information Systems， 1998， 54（1999）： 1-17.

[LL]

[2] TANG Jie， SUN Jimeng， WANG Chi， et al. Social influence analysis in large-scale networks[C]Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. Paris， France：ACM， 2009： 807-816.

[3] KWAK H， LEE C， PARK H， et al. What is Twitter， a social network or a news media？[C]The 19th international conference on World Wide Web. Raleigh， North Carolina， USA ：ACM， 2010： 591-600.

[4] ZHANG Ke， LI Hui， QIN Lijuan， et al. Closeness centrality on BBS reply network[C] International Conference on Information Technology， Computer Engineering and Management Sciences. Nanjing， Jiangsu， China：IEEE， 2011： 80-82.endprint

[5] CHA M， HADDADI H， BENEVENUTO F， et al. Measuring user influence in twitter： The million follower fallacy[C]Proceedings of the Fourth International Conference on Weblogs and Social Media， ICWSM 2010. Washington， DC， USA：DBLP， 2010： 10-17.

[6] WENG Jianshu， LIM E P， JIANG Jing， et al. TwitterRank： Finding topic-sensitive influential twitterers[J]. Proceedings of the third ACM international conference on Web search and data mining. New York， USA：ACM， 2010： 261-270.

[7] ZHAI Zhongwu， XU Hua， JIA Peifa. Identifying opinion leaders in BBS[C]WI-IAT '08 Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology . Washington， DC， USA ：IEEE， 2008： 398-401.

[8] MATSUMURA N. Topic diffusion in a community[M]OHSAWA Y， MCBURNEY P. Chance Discovery . Advanced Information Processing. Berlin/Heidelberg：Springer， 2003： 84-97.

[9] [JP3]HU Jian， FANG Yi， GODAVARTHY A. Topical authority propagation on microblogs[C][JP] Proceedings of the 22nd ACM international conference on Information & Knowledge Management. San Francisco， California， USA：ACM， 2013： 1901-1904.

[10]AGARWAL N， LIU Huan， TANG Lei， et al. Identifying the influential bloggers in a community[C] WSDM '08 Proceedings of the 2008 International Conference on Web Search and Data Mining. Palo Alto， California， USA：ACM， 2008： 207-218.

[11]GOTZ M， LESKOVEC J， MCGLOHON M， et al. Modeling blog dynamics[C] AAAI Conference on Weblogs and Social Media （ICWSM）. San Jose， California：AAAI， 2009： 26-33.

[12]BOLDI P， SANTINI M， VIGNA S. PageRank as a function of the damping factor[C]WWW '05 Proceedings of the 14th international conference on World Wide Web. Chiba， Japan：ACM， 2005： 557-566.

[13]NEWMAN M E J. Networks： An introduction[M]. Oxford： Oxford University Press， 2010.

[14]FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks， 1978， 1（3）： 215-239.

[15]TRAVERS J， MILGRAM S. The small world problem[J]. Phychology Today， 1967， 1：61-67.

[16]SONG Xiaodan， CHI Yun， HINO K， et al. Identifying opinion leaders in the blogosphere[C]Proceedings of the sixteenth ACM Conference on information and knowledge management.Lisbon， Portugal ：ACM， 2007：971-974endprint