谢国豪+罗浩+吴志刚+张树壮

摘要：针对如何在高校论坛中识别出高影响力用户的问题，提出了一种结合时间因子的论坛用户影响力计算方法。在PageRank算法的基础上，通过分析论坛用户回帖行为随时间变化的规律引入用户影响力的衰减系数，并根据用户间的交互情况，通过用户间的交互次数和用户主题参与度来优化用户影响力的分配形式。实验结果表明：在相同时间段内，改进后的算法相对于PageRank算法能够识别出具有更强中心性特性和更高用户覆盖率的高影响力用户。在连续时间段上，通过引入衰减系数能够发掘当前真正具有影响力的用户并保持稳定的用户覆盖率。

关键词： 影响力； 时间因子； 衰减系数； 主题参与度； 中心性特性； 覆盖率

中图分类号：TP393

文献标码：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

基金项目： 家重点研发计划资助项目（2016YFB0801200）。

收稿日期： 2017-08-27

0引言

隨着移动互联网的发展和普及，在线社交网络已经深刻地影响了人们的生活方式。高校网络论坛作为在线社交网络的重要组成部分，凭借其以高校为背景的区域性特征以及当今大学生思想交流活动频繁的特性，吸引了大量师生参与到论坛交流中。考虑到高校论坛的参与对象以及自由开放的讨论空间，识别出高校网络论坛中具有高影响力的用户对于信息的传播和引导具有重要的意义。

PageRank作为经典的页面排名算法是基于网页及其链接构成的全局拓扑结构，依据网页间的链接关系和随机游走思想对网页进行重要度计算和排序[1]。社交网络与网页链接网络具有相似的拓扑结构，用户在社交网络中活动产生交互关系，这种关系会随着用户活动而不断累积，若直接利用PageRank算法对用户影响力进行计算，显然在社交网络中存在时间较长的用户有更大的可能拥有较多的链入关系从而获得更高的影响力值，即使用户之后不再产生任何行为，这种全局关系仍然会使用户在影响力计算中取得较大的值而非呈现减弱的趋势。同时在PageRank算法中，网络拓扑中的节点平等对待其它所有节点，以平均分配的方式分配其权值从而导致忽略了节点之间的差异性对最后计算结果的影响。

针对以上问题，本文提出了一种结合时间因子的用户影响力计算方法，通过收集到的高校论坛数据对算法进行了实验和对比，验证了改进后的算法能够更加准确识别出具有高影响力的用户群。

1相关工作

社会网络作为一门交叉性学科，已经被SIGKDD、WWW等多个重要的国际会议列为研究议题[2-3]，且形成了一个专门的研究方向——社会网络分析（Social Network Analysis，SNA）。社会影响力排序作为社会网络研究的子领域吸引了大量学者参与研究，不同学者从不同的角度对用户影响力进行研究。如Zhang等人通过对网络BBS构建回复网络，分析节点中心性来发现处于网络中心位置的用户[4]。Meeyoung Cha等人从粉丝数、转发数、引用数这3个指标来评定Twitter上的用户影响力[5]。Weng等人利用社交网络中用户之间的关注关系来构建转发网络，提出了TwitterRank算法[6]。Zhai等人通过对论坛中用户发表内容进行所属兴趣域的划分来识别用户的影响力[7]，Matsumura等人提出了IDM模型，考虑论坛帖子中关键词在对话链中的传递来反映影响力[8]，Hu等人针对Twitter提出了TAP算法，根据转发内容与给定主题间的相似度计算用户在给定主题下的影响力权重[9]。endprint

本文从时间维度对社交网络中的用户影响力衰减规律进行分析，并在影响力计算公式中引入衰减系数，同时通过改进PageRank算法中节点权值的分配方式来对PageRank进行优化，以此分析用户的影响力。

2结合时间因子的影响力计算

2.1数据集说明

本文以北邮人论坛的数据作为算法改进和实验的基础。数据主要由用户信息和主题帖信息构成，其中用户信息包括参与过发帖或者回帖的用户数目。主题帖信息包括正文和后续的跟帖内容，以及正文和跟帖的发布时间和作者信息，同时整理出了用户之间的交互关系。

本文收集到的数据集包含了自2004年11月份至2017年3月份的全部相关数据。具体的数据集描述如表1所示。

3实验结果与分析

3.1评价指标

社会网络分析中普遍认为全局网络中具有高影响力的节点具有高中心性，并提出以中心性测度（Centrality measures）作为判断网络中节点重要性的指标来对节点重要性进行量化 [13]。紧密中心性（Closeness Centrality）[14]作为中心性的度量方法之一，当节点具有更高的紧密中心性时表示该节点处于中心位置[4]并且具有更高传递影响的能力，刻画了节点的全局重要性[15]。

本文以节点紧密度的大小排序作为基准排序，通过计算不同算法识别的影响力Top N用户集合相对于基准排序的召回率来对算法进行评价。同时鉴于高影响力人物往往能够影响更多的用户，参考文献[7，16]引入覆盖率指标（Coverage Ratio）。

3.2实验结果分析

3.2.1单个时间段内的结果对比

以节点紧密度为指标，对相同时间段内的用户进行排序并作为基准，考察不同算法在相同时间段内识别出的用户集合相对基准排序的召回率，召回率越高则说明结果越接近基准排序。得到2种算法的召回率结果如图2所示，从图2中可知，在取相同比例Top N的用户进行对比的前提下，TUR算法相对基准算法具有较高召回率，说明其识别的用户群体相对于PageRank算法所识别的用户群体具有更高的中心性。

同时，考察2种算法识别出的Top N前50%的用户的覆盖率。结果如图3所示，在相同比例的Top N用户群体中，TUR算法识别的高影响力用户相对于PageRank算法识别的高影响力用户具有更高的覆盖率，表明利用TUR算法识别的用户群所具有的影响力能够覆盖更多用户，影响范围更广。

3.2.2连续时间段上影响力变化

本文选取了2016年1月1日到12月31日为期一年的所有数据进行研究，在该时间段上分析了排名前5%的高影响力用户的覆盖率变化情况。结果如图4所示。从图4中可以看出，利用TUR算法识别的排名前5%的用户覆盖率，随着时间的发展变化波动较小，趋势线趋于平稳，总体保持较稳定的覆盖率。而利用PageRank算法所识别的排名前5%的用户覆盖率，随着时间的发展整体呈下降趋势。究其原因，TUR算法在计算公式中引入了衰减系数，通过筛选当前时间段内活跃用户并淘汰长期无作为的用户，来保持高影响力用户群的影响覆盖率。而在PageRank算法计算中，一些不再参与论坛活动但曾经活跃的用户因为之前积累了大量的交互关系仍然获得了较大的影响力值并占据较高的排名，这些用户不再产生新的交互，其影响的用户数量始终保持不变，随着论坛中新用户的不断增多从而导致了覆盖率下降。说明了衰减系数的引入有助于更好地识别活跃的高影响力用户。

4结束语

本文提出一种结合时间因子的论坛用户影响力计算算法Time-User Rank。在PageRank算法基礎上结合时间因子引入影响力的衰减系数，以及通过用户间的交互权重和用户的主题参与度，针对PageRank算法中对节点影响力均分分配的问题做出了相关优化。通过实验表明，在同一个时间段内改进后的算法相对于PageRank算法能够识别得到具有更高的中心性特性和用户覆盖率的高影响力用户群体，并且在连续时间段上能够通过影响力衰减系数有效地挖掘出活跃且具有高影响力的用户，使整个高影响力用户群始终保持稳定的用户覆盖率。

参考文献：

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