謝國(guó)豪+羅浩+吳志剛+張樹(shù)壯

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

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

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)碼：A

文章編號(hào)：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

基金項(xiàng)目： 家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2016YFB0801200）。

收稿日期： 2017-08-27

0引言

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

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

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

1相關(guān)工作

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

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

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

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

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

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

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

3.1評(píng)價(jià)指標(biāo)

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

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

3.2實(shí)驗(yàn)結(jié)果分析

3.2.1單個(gè)時(shí)間段內(nèi)的結(jié)果對(duì)比

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

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

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

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

4結(jié)束語(yǔ)

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

參考文獻(xià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