面向微博话题的用户影响力分析算法

刘威;张明新;安德智

【摘 要】微博用户影响力分析作为社交网络分析的重要组成部分,一直受到研究人员的关注.针对现有研究工作分析用户行为时间性的不足和忽略用户与参与话题之间关联性等问题,提出了一种面向微博话题的用户影响力分析算法——基于话题和传播能力的用户排序(TSRank)算法.首先,基于微博话题分析用户转发行为时间性,进一步构建用户转发和用户博文转发两种话题转发关系网络,预测用户话题信息传播能力;然后,分析用户个人历史微博和背景话题微博文本内容,挖掘用户与背景话题之间的关联性;最后,综合考虑用户话题信息传播能力以及用户与背景话题间关联性计算微博用户影响力.爬取新浪微博真实话题数据进行实验,实验结果表明,话题关联度更高用户的话题转发量明显大于关联度很低的用户,引入用户转发行为时间性相比无转发时间性,TSRank算法的捕获率(CR)提高了18.7％,进一步与典型影响力分析算法WBRank、TwitterRank和PageRank相比,TSRank算法在准确率和召回率上分别提高了5.9％、8.7％、13.1％和6.7％、9.1％、14.2％,验证了TSRank算法的有效性.该研究成果对社交网络的社会属性、话题传播等理论研究以及好友推荐、舆情监控等应用研究具有支撑作用. 【期刊名称】《计算机应用》 【年(卷),期】2019(039)001 【总页数】7页(P213-219)

【关键词】社交网络;用户影响力;转发关系;微博话题;信息传播能力 【作 者】刘威;张明新;安德智

【作者单位】苏州大学计算机科学与技术学院,江苏苏州215006;常熟理工学院计算机科学与工程学院,江苏常熟215500;甘肃学院网络空间安全学院,兰州730070

【正文语种】中 文

【中图分类】TP391;TP181 0 引言

社交网络平台是以互动交友、用户之间共同兴趣爱好为基础，以实名或非实名方式在网络平台构建的一种社会关系网络服务。社交网络平台现已取得迅速发展[1]，全球最大社交网站Facebook发布2018年第一季度财报显示，截止2018年3月31日，Facebook的月活跃用户达22亿，比去年同期增长3.8%；新浪微博发布2018年第一季度财报显示，微博月活跃用户共4.11亿，比去年同期增长20%。微博作为新型公共话题传播平台，已有庞大的用户群体，用户量也保持较好增长，如此庞大的用户群体中存在有较高声望和影响力的用户，他们的言论和观点会影响大多数用户的观点，社交网络的无标度性质也决定了社交网络中少部分人掌握着大部分话语权[2]，这部分有话语权的影响力用户非常值得关注。微博用户影响力可以通过微博话题的互动表现出来，表现为话题参与用户的行为和观点受其他用户的影响发生改变的现象[3]。分析微博话题的用户影响力对社交网络的研究具有重要意义：1)有影响力用户是推动话题持续传播和扩大话题传播范围的关键因素[4]，研究微博用户影响力可以发现微博话题信息的传播规律；2)微博话题在传播过程中存在着错综复杂的社会属性，研究微博用户影响力有助于了解社交网络的社会属性；3)微博用户质量参差不齐，用户需要推荐高质量和有影响力的用户，以获取有价值和感兴趣的信息，识别有影响力用户有助于推荐微博中有共同兴趣的高质量好友，

因此，计算微博用户的影响力并找出影响力排名靠前的用户，对话题信息传播[5]、微博好友推荐[6]、网络舆情监督[7]等具有重要意义。

微博用户影响力得到了研究人员的持续关注，目前研究工作侧重于偏离用户关系网络分析用户行为时间，忽略行为时间对传播广度和互动关系强度的影响；侧重于从用户之间兴趣话题的角度分析，忽略用户对话题的兴趣关注和微博短文本等特征对话题识别的影响。

1)用户行为的时间性。毛佳昕等[8]认为用户帖子的被转发频率是最能代表用户影响力大小的指标，利用用户发布微博的时间分布、微博时效性和转发偏好计算用户帖子的被转发频率，确定用户的影响力大小，该方法侧重分析用户发布微博时间分布对被转发频率的影响，忽略发布微博时间对转发传播广度和转发关系强度的影响，不能区分影响人群广度不同的有影响力用户和转发对影响力的贡献度。廖祥文等[9]将用户观点、活跃度、中心度等特征加入到张量模型中，假设用户间评论的延迟时间满足指数分布，得到评论时间特征约束矩阵并引入到张量模型分解过程中，以此计算用户影响力，该方法侧重分析在张量分解模型中引入评论延迟时间来度量用户影响力，忽略评论延迟时间在用户关系网络中对影响力传播范围广度的影响，不能很好识别最有影响力用户。Su等[10]将用户交互行为的整个时间区间划分成时间片，在主题模型中引入文本主题、各类交互关系以及交互相关联的时间片，提出了一种主题级影响力时间模型(Topic-level Influence over Time, TIT)，该模型侧重基于转发、评论等交互行为所属时间片来识别影响力有潜在增长趋势的用户，忽略转发、评论等交互行为本身发生时间对用户间交互关系强度的影响程度，不能有效地确定不同交互时间对用户影响力的影响程度。

2)用户的兴趣话题。周东浩等[11]使用潜在狄利克雷分布(Latent Dirichlet Allocation, LDA)主题模型分析用户的兴趣话题相似度，基于用户的传播概率、兴趣相似度和结构相似度构建随机游走模型，提出了一种用户传播能力排序算法，该

算法侧重分析用户之间在结构和兴趣话题上的相似度，忽略用户兴趣与参与话题之间的关联性，最终识别出的影响力用户并非真正关注话题并持续产生影响力的用户，微博也具有短文本和数据稀疏等特点，直接使用LDA主题模型识别用户潜在兴趣话题分布的效果不佳。祝升等[12]利用LDA主题模型计算用户在博文内容上的话题分布，构建话题关系网络，综合用户之间的话题相似度、平均转发延迟和转发量占比得出边权重，迭代计算出用户影响力，该方法侧重分析用户之间的话题相似性，LDA主题模型直接应用到微博短文本的效果不理想，识别用户兴趣话题的效果不佳，计算用户之间话题相似度不准确。Wu等[13]利用消息内容、标签、转发、回复和提及(@)构建主题行为网络，采用启发式搜索方法生成用户的主题行为影响树，通过最大化受影响用户数和最小化传播路径识别有影响力用户，该方法侧重用户之间主题行为影响树的构建，忽略微博短文本特点和用户对参与话题的兴趣来分析用户主题，影响对话题真正感兴趣而持续产生影响力的关键用户的识别。

综上所述，现有研究有以下不足：1)忽略用户转发行为时间对用户影响力传播广度和交互关系强度的影响；2)未结合微博短文本等特征分析用户话题；3)忽略用户对参与话题的兴趣关注。本文选择国内最大的新浪微博社交网站作为研究对象，基于微博话题分析用户影响力。针对第1)点不足，在用户转发关系网络和用户博文转发关系网络中分析转发时间性(时间差)对转发关系强度和微博用户影响力传播广度的影响来计算转发时间性对微博用户影响力的贡献度。针对第2)点和第3)点不足，基于用户与参与话题之间的关联性来计算用户对微博话题的兴趣关注度，通过微博关系扩展微博短文本改进LDA主题模型，分别识别用户和背景话题的微博文本内容的潜在话题分布，计算用户与背景话题之间的关联度。算法思路：首先，基于微博话题综合分析用户交互以及包含的时间信息构建用户转发和博文转发两种话题转发关系网络，分析转发行为时间性对转发影响力和用户自身质量的影响，并从用户转发影响力和用户自身质量两个方面计算用户信息传播能力；然后，通过微博关系

拓展微博短文本并改进LDA主题模型，通过改进LDA主题模型分析用户个人微博文本内容和微博话题文本内容的潜在话题分布，据此计算用户与背景话题之间的关联度；最后，综合分析用户话题信息传播能力和用户与背景话题之间的关联度，计算话题参与用户的影响力大小。通过爬取新浪微博真实话题数据进行实验，分别验证了引入用户转发行为时间性和用户与参与话题之间关联性的有效性。与典型影响力分析算法WBRank、TwitterRank和PageRank比较，本文提出的基于话题和传播能力的用户排序(Topic and Spread user Rank, TSRank)算法在准确率和召回率上分别提高了5.9%、8.7%、13.1%和6.7%、9.1%、14.2%，表明了TSRank算法的有效性。 1 微博用户影响力分析与度量

微博用户影响力可以通过微博话题的互动表现出来，对其他用户的行为和观点等产生影响，因此，本文基于微博话题分析用户影响力。话题参与用户的影响力主要表现为微博用户信息的传播广度和影响强度，即用户的话题信息在话题传播过程中，影响人群越广，影响用户强度越大，用户的影响力越大。微博用户影响力分析算法的整体思路如图1所示。 1.1 问题定义

以微博话题传播重要途径转发行为，构建话题用户转发关系网络和用户话题博文转发关系网络，在两种关系网络中分析转发时间性都能体现话题用户影响力的传播广度，其中，在用户转发关系网络中计算用户转发影响力，量化用户信息传播的影响人群广度；在用户博文转发网络中计算用户自身质量，量化用户信息传播的影响用户强度。

图1 用户影响力分析算法设计整体框架Fig. 1 Algorithm design overall framework of user influence analysis

将用户转发关系网络抽象为一个有向加权图，表示为：

G1=(V1,E1,W1) (1)

其中：V1为参与话题全部用户；E1为用户间转发关系的有向边集合；W1为有向边的转发权重，该权重通过转发行为时间性和用户活跃度刻画。 将用户博文转发关系网络抽象为一个有向加权图，表示为： G2=(V2,E,W2) (2)

其中：V2是用户和博文两种类型节点集合，即V2=(VB∪VU)，

VB={b1,b2,…,bm}代表博文集合，VU={u1,u2,…,un}代表用户节点集合；E=EU → B∪EB → U是两类边集合，是用户到博文节点一组边(用户转发博文)，是博文到用户节点一组边(博文所属用户)；W2为用户转发关系网络中边的权重，分为两类：用户节点到博文节点的边权重和博文节点到用户节点的边权重。 1.2 权重指标定义

G1和G2有向边上的权重反映了转发关系对微博用户影响力的贡献度，是准确计算出微博用户影响力的关键。通过分析用户转发行为时间性(时间差)来量化G1和G2有向边上的权重。 1.2.1 转发行为时间性

用户u在话题内可能发布多条有关话题的博文，另一用户v可能转发用户u多条博文，因此用ri代表用户v与用户u第i条博文的转发关系，则有： (3)

微博话题热度一般会在短时间推进过程中逐渐降低，用户博文被转发的时间差越大，对该博文的传播广度和被转发关系强度的影响越小，这意味着更早时间的转发更有利于被转发信息的传播，对被转发用户影响力的贡献度更高，因此，使用指数衰减

函数来模拟用户转发行为时间性对微博用户影响力的贡献度，这也符合Gotez等[14]基于微博分析提出消息影响力衰减服从幂律分布的结论。wr(v,u)表示用户v对用户u信息传播能力贡献度，即用户u对用户v的转发权重，表示如下： )/(∑ri(v,u)) (4)

其中：e为自然常数(e>0)；O1(u)表示用户u发布话题博文集合，为用户u发布第i条博文时刻(单位为h，表示距离博文发布当天凌晨的时间)，ti为用户v转发用户u第i条博文时刻(单位为h，表示距离被转发博文发布当天凌晨的时间)，为用户v转发用户u第i条博文的时间差(时间差越小，对被转发用户u的影响力贡献度越大)；λ为控制衰减速率的参数，设置λ=11 h。对于固定值λ(λ>0)，当时，当时，

1.2.2 用户活跃度

用户活跃度体现用户促进话题传播的积极程度，在G1中结合转发时间性和用户活跃度来计算转发影响力，可以更加准确地体现用户信息传播能力的影响人群广度。用户u的活跃度表示为a(u)，通过用户u在一段时间内的发文频率和转发频率来量化用户u在话题内促进信息传播的活跃度，则： a(u)=npost(u)/T+nrepost(u)/T (5)

其中：npost(u)是用户在时间段T内发布博文数量，nrepost(u)是用户在时间段T内的转发数量，T是时间段长度。 1.3 度量指标定义

话题参与用户通过发布话题信息的传播对被转发用户产生影响，其影响的人数越多，在用户转发关系网络中从其他用户引入的链接数越多，表明其影响人群越广；同时，用户转发行为由用户自身的价值驱动，话题内用户质量越高，对其他用户的影响程

度越大，体现了用户的信息传播能力的影响强度，所以从用户转发影响力和用户自身质量两个角度计算用户信息传播能力，分别体现微博用户影响力的影响传播广度和影响用户强度。 1.3.1 用户转发影响力

话题用户转发网络与网页链接结构十分相似，用户u被用户v转发相当于网页v存在一个链接指向网页u，用户v将自己的影响力贡献给用户u，网页v将自己的重要性贡献给网页u，但由于用户v的转发时间间隔和自身活跃度都不同，对用户u的影响力贡献度也是不同的，所以，在用户转发关系网络中，话题参与用户u的转发影响力表示为R(u)，引入wr(v,u)来体现转发时间间隔对用户转发关系强度和用户影响人群广度的影响，借鉴经典网页排序算法PageRank的思想计算R(u)，微博用户转发影响力的计算公式如下： (6)

其中：O2(u)为用户u的转发用户集合；R(v)为用户v的转发影响力；out(v)为用户v指向其他用户的转发；c为阻尼系数，通常设置为经验值0.85。 1.3.2 用户自身质量

在用户博文转发关系网络中，用户u发布博文b(b∈VB)的质量记为Blogb(u)，用户到博文节点的转发关系边权重设置为wr(v,u)，体现转发时间差对博文传播广度和博文转发关系强度的影响，借鉴PageRank思想计算Blogb (u)，计算如下： Blogb(u)=(1-c)+c* (7)

其中：O3(b)是博文b的转发用户集合，Q(v)是用户v的自身质量，out(v)是用户v指向其他用户的转发。

在微博话题传播过程中，因为用户自身质量主要通过用户发布博文的质量体现，所

以，使用用户u所有博文的质量表示用户u自身质量Q(u)。在用户博文转发关系网络中，设置博文节点b到用户节点u的边权重为wb(u)，体现博文质量b对用户自身质量计算的重要程度。用户u的自身质量计算公式如下： (8)

其中：O4(u)是用户u的所有博文集合;wb(u)=Nb/Nc，Nb为用户u的博文b的总转发数，Nc为用户u所有博文总转发数。 1.4 用户信息传播能力计算

在话题传播过程中，转发影响力体现被转发用户信息传播能力在话题内的信息传播广度，用户自身质量体现用户信息传播能力影响用户的强度，因此本文将这两个度量指标通过线性融合计算用户在话题内的信息传播能力大小，表示为Spread(u)，计算如下：

Spread(u)=α1×R(u)+α2×Q(u) (9)

其中：α1是用户转发影响力所占比重，α2是用户自身质量所占比重。设置α1=α2=0.5，表示用户的转发影响力和用户自身质量对用户信息传播能力同等重要。

2 面向话题的用户影响力算法 2.1 用户与参与话题间的关联性

面向微博话题的用户影响力研究大多假设用户影响力不受微博之外的因素影响，但微博社交网络用户具有社会属性，其影响力受多种因素影响。用户兴趣与热点话题之间的关联性代表该用户是否会持续关注该话题，频繁参与话题互动并产生持续影响力。本文在实验部分验证了用户与背景话题之间关联性对用户转发微博话题相关博文数量的影响，表明话题关联度较高的用户相比较话题关联度较低的用户，会更

频繁地参与话题互动并产生持续影响力，为此通过分析微博话题相关所有博文集合和用户对应时段内的个人历史博文集合，计算用户与微博话题之间的关联度。 针对LDA主题模型不适用于微博短文本，结合微博短文本特征改进LDA主题模型。将微博话题内的每一个博文以及其他用户评论它的内容和原始发布者对这些评论的回复聚合成多个单个博文集合，然后聚合微博话题内的所有单个博文集合形成微博话题文档集合。基于此方法拓展博文短文本的原因是，用户发布博文以及用户之间的评论回复通常是围绕博文主题进行的。同样采用此方法拓展用户在同一时间段内的历史博文内容得到用户文档集合，然后使用中文微博关系主题模型(Micro-blog Relation Latent Dirichlet Allocation， MR-LDA)方法[15]改进LDA主题模型,该方法结合了博文之间的提及(@)、转发、评论和点赞关系。

识别微博话题文档集合和用户文档集合主题数K，使用改进LDA主题模型识别微博话题文档集合的主题概率分布Vtopic和用户文档集合的主题概率分布Vu，向量表示如下： (10) (11)

其中：和分别是用户u的文档集合和微博话题文档集合产生主题i的概率，且 相对熵，又称KL(Kullback-Leibler)散度，是描述两个概率分布之间差异的一种方法，符合本文计算用户与背景话题之间关联度的特点，所以本文使用KL散度计算Vtopic和Vu向量之间的距离，值越大，说明越不相似，计算公式如下： (12)

由于KL散度不具有对称性，与用户和背景话题之间关联度的对称性不相符。为了

使得公式符合对称性，便于描述用户与背景话题关联度和KL值对应关系，将公式进行转换。定义用户u与背景话题之间关联度S(u,topic)，公式如下： (13)

其中：S(u,topic)为用户与背景话题之间关联度，S(u,topic)的值越大，用户历史微博内容与背景话题内容的概率分布差别越小，用户与背景话题之间的关联度越高。 2.2 面向微博话题的用户影响力计算

用户信息传播能力代表用户对话题信息传播能力的大小，用户与背景话题之间的关联度代表用户与背景话题之间的黏性，是用户对话题传播持续产生的影响力，所以，基于用户信息传播能力和用户与参与话题之间的关联度直接计算话题参与用户的影响力大小，计算如下：

TSRank(u)=Spread(u)×S(u,topic) (14)

其中：Spread(u)表示用户u在话题内的信息传播能力大小;S(u,topic)表示用户u与背景话题之间关联度大小。

话题参与用户的影响力分析算法TSRank如下。 算法1 用户影响力计算。

输入：用户转发关系网络G1=(V1,E1,W1)，用户博文转发关系网络G2=(V2,E)，用户博文等数据集，迭代次数阈值N，微博主题数K。 输出：用户影响力值。 c ← 0.85

//设置经验值为0.85 for u∈VU do //VU为用户集合

Q(u) ← 1

//初始化用户u自身质量Q(u) R(u) ← 1

//初始化用户转发影响力R(u) end for

Max_iteration ← N iteration ← 0 //初始化迭代次数

while iteration//更新所有博文质量，VB为所有博文集合 更新Blogb(u) //用户u的博文b质量 end for for u∈VU do

//更新每个用户的转发影响力、自身质量 更新a(u)，R(u) and Q(u)

//更新用户活跃度、转发影响力和用户自身质量 end for

iteration=iteration+1 end while for u∈VU do

//计算每个用户的影响力值 Spread(u)=α1×R(u)+α2×Q(u)

S(u,topic)=2/[DKL(Vu‖Vtopic)+DKL(Vtopic‖Vu)] TSRank(u)=Spread(u)*S(u,topic) print TSRank(u)

//输出：用户u的影响力值 end for

3 实验结果及分析

为了验证该算法的普适性和有效性，实验部分首先选取了新浪官方公布的微博热点话题“徐玉玉案”，该话题事件范围为2017年6月2日—2017年7月21日，又增加了该话题时间内的“2017NBA总决赛”“李文星事件”“顺丰菜鸟‘数据断交门’”“四川‘格斗孤儿’”“中国式相亲鄙视链”5个话题，共计6个话题，使实验数据包括教育、体育、社会、科技、民生等多领域的一般性话题和热点话题，同时，选取2017年6月21日—6月22日两天时间内新浪微博上的所有话题数据，进行实验验证，使实验验证具有普适性。通过网络爬虫获取以上相关数据，同时爬取话题参与用户在对应时间内的历史消息微博数据。对得到数据进行预处理后，数据集统计情况如表1所示。由于爬取的微博话题的用户数据量较大，借助Spark平台实现本文算法(TSRank),使用Matlab仿真实验结果，通过多次实验的最优结果，设置控制衰减速率的参数λ=11 h。

表1 实验数据集Tab. 1 Experimental dataset参数值参数值用户总数8571提及(@)总数506817微博总数13743点赞总数1062795转发总数871539好友总数3271583评论总数853284 3.1 有效性测试

首先验证用户与参与话题之间关联度和转发行为时间性的有效性。以话题“2017NBA总决赛”为例，通过计算用户与背景话题之间的关联度对用户进行分类，将关联度较高和较低的用户分为话题相关用户和话题不相关用户，分析用户与

背景话题间关联度对转发行为的影响。统计所有用户(all users)、话题相关用户(topics related users)和话题不相关用户(other users)所转发的与热点话题相关微博的数量变化，其中，时间周期为2天，结果如图2所示。

图2 微博话题下三种用户的转发量统计Fig. 2 Statistics of forwarding amount of three type of users for Weibo topic

从图2中可知，在话题传播周期内，微博话题相关博文数的增长对各类用户的转发量都有所影响，话题相关用户的转发量上升幅度明显高于话题不相关用户，同时话题相关用户转发趋势与话题整体转发趋势比较接近，而话题不相关用户转发量的趋势与之并不明显接近。表明话题相关用户话题参与度更高，更易促进话题传播，话题相关用户会对话题传播持续产生影响力。验证了引入用户与背景话题之间的关联度有助于识别微博话题传播过程中有持续影响力用户，能在一定程度上屏蔽仅靠刷微博数来提升微博话题热度的水军用户。

验证引入转发行为时间性的有效性，使用捕获率(Catch Ratio, CR)作为评测指标，CR为通过Top-k用户检测到的信息与网络中实际存在的信息的比值。验证结果使用六个话题以及两日内的所有话题数据集的平均捕获率，如图3所示。从图中可以看出，转发时间性对CR指标的影响较大，随着Top- 10、Top- 20、Top- 30、Top- 50、Top- 80和Top- 100的变化，引入转发时间性的CR值明显优于不考虑转发时间性的情况。

图3 引入转发时间性的CR指标对比Fig. 3 CR indicator comparison of introduction of forwarding time 3.2 实验对比测试

通过实验对比，测试TSRank算法识别有影响力用户的准确性，选取WBRank算法[16]、TwitterRank算法[6]和PageRank算法三种算法作为对比，其原因是：WBRank算法是较新算法，同样基于新浪微博平台和考虑用户行为进行分析；

TwitterRank算法也是基于话题和网络结构的经典算法；PageRank是经典排序算法，且本文有借鉴其算法思想。图4给出Top- 10、Top- 20、Top- 30、Top- 50、Top- 80和Top- 100下四种算法对CR指标影响的实验结果。从图4中可以看出，随着选取有影响力用户数量的增多，TSRank方法的CR指标均优于其他三种算法，说明TSRank算法识别微博话题内有影响力用户的效果更佳。 图4 四种算法的CR指标对比Fig. 4 Comparison of CR indicators for four algorithms

3.3 算法准确率和召回率验证

为了更进一步验证本文方法的有效性，分别验证挖掘影响力个体的准确率和召回率。由于微博话题中的实际影响力用户难以人为确定，所以通过上述3种算法和TSRank算法的交叉验证来确定真实影响力用户的排名。

交叉验证方法[17]是将多种算法(N种)认为的正确结果作为最终正确结果。例如给定4种算法A、B、C和D，各算法得出的正确结果分别为IA、IB、IC和ID，设置N=2，即2种算法认为的正确结果作为最终的参考结果，称其为参考标准集合I2，则定义I2为：

I2=(IA∩IB)∪(IA∩IC)∪(IA∩ID)∪(IB∩IC)∪ (IB∩ID)∩(IC∩ID) (15)

准确率P(Precision)体现挖掘话题内影响力用户的真实性，算法A挖掘影响力用户的准确率定义如式(16)所示： (16)

召回率R(Recall)体现微博话题内影响力用户的挖掘充分程度，即算法A挖掘影响力用户的召回率定义如式(17)所示：

(17)

实验根据4种算法，在N=2,3,4时，对比了六个话题以及两日所有话题的平均准确率在Top- 10、Top- 20、Top- 30、Top- 50、Top- 80和Top- 100下的实验结果，如图5所示。

实验结果表明，参考标准数量N在不同取值情况下，TSRank算法的准确率均优于其他三种算法，但实验效果有所不同。因为参考标准数量N设置过小(N=2)时，参考标准集合IN元素数目偏多，各算法与IN交集元素较一致，导致准确率相差不大；参考标准数量N设置过大(N=4)，参考标准集合IN元素数目偏少，同样使得各算法与IN交集元素较一致，导致准确率相差也不大。当N=3时，四种算法的准确率效果最理想，能体现出各算法的准确性优劣，此时，TSRank相比WBRank、TwitterRank和PageRank，在不同Top-k和三个话题下的平均准确率分别提高了5.9%、8.7%和13.1%，表明TSRank算法能更准确地识别出有影响力用户。

实验同样对比了在参考标准数量N=2,3,4的不同设置下，6个话题以及两日所有话题的平均召回率在不同Top-k影响力用户下的实验结果，如图6所示。 图5 四种算法的准确率对比Fig. 5 Precision comparison of four algorithms 图6 四种算法的召回率对比Fig. 6 Recall comparison of four algorithms 从图6可知，参考标准数量N在不同取值情况下，TSRank算法的召回率均优于其他三种算法，但实验效果同样不同，因为N设置过小(N=2)时，各算法与IN元素的交集元素同样多，召回率相差不大；N设置过大(N=4)时，各算法与IN元素的交集元素同样少，召回率相差也不大。参考标准数量N=3时，实验效果最佳，此时，TSRank相比WBRank、TwitterRank和PageRank，在不同Top-k和三个话题下的平均召回率分别提高了6.7%、9.1%和14.2%，表明TSRank算法能

更充分地识别出有影响力用户。 3.4 算法效率和复杂度分析

为了测试TSRank算法的执行效率，本文将数据集按照用户节点数逐渐递增，划分为5个规模不同的数据块，分别将其标识为数据块1、2、3、4、5，对应的用户节点数为76 837、110 381、158 353、229 361、281 539，对比了4种算法在6个话题以及两日内所有话题数据上的平均执行时间(min)，实验结果如图7所示。

图7 四种算法的执行时间对比Fig. 7 Comparison of execution time for four algorithms

实验结果表明，本文提出的TSRank算法的执行时间更少，算法效率明显优于同其他三种算法；同时，4种算法的执行时间随着数据集规模的增大而呈线性增长，但TSRank算法的增幅较小。

TSRank算法与PageRank算法相比，算法复杂度有所增加，需要计算用户转发影响力和用户自身质量，但它们的计算简单，且转发影响力、用户自身质量以及用户与话题间关联度是并行的，因此算法复杂度增幅较小，相比WBRank算法和TwitterRank算法，TSRank算法复杂度也没有过高，三者都考虑了用户网络结构和用户行为，其中，WBRank和本文算法都是基于PageRank迭代收敛，TwitterRank和本文算法都考虑了话题因素。对于算法的优化策略，可以从技术角度出发，增大并行节点数或将中间输出结果同用户关系相结合作为下一次迭代输入，提高执行效率，同时可以借助Spark GraphX技术提高对大规模图计算的效率。 4 结语

利用社交网络中微博话题和参与用户数据，本文给出了话题参与用户的话题信息传播能力和用户对微博话题兴趣关注的度量机制，提出了一种面向微博话题的用户影响力分析算法，通过真实新浪微博数据验证和与其他同类经典算法对比，测试了本

文算法的可行性、高效性和准确性。本文提出的算法，可以用于解决大规模微博话题用户中的关键用户识别问题，对社交网络中解决信息传播和舆情监控等问题具有支撑作用。

本文仅在用户行为时间性和用户与微博话题间关联度基础上提出挖掘微博话题内有影响力用户算法，进一步的工作可以基于话题传播网络，将微博用户影响力与微博情感结合考虑，挖掘话题传播过程中高影响力用户的情感极性，更有效地监控舆情。 参考文献(References)

【相关文献】

[1] 赵姝,刘晓曼,段震,等.社交关系挖掘研究综述[J].计算机学报,2017,40(3):535-555.(ZHAO S, LIU X M, DUAN Z, et al. Review of social relationship mining research [J]. Chinese Journal of Computers, 2017, 40(3):535-555.)

[2] 韩忠明,陈炎,刘雯,等.社会网络节点影响力分析研究[J].软件学报,2017,28(1):84-104.(HAN Z M, CHEN Y, LIU W, et al. Analysis of influence of social network nodes [J]. Journal of Software, 2017, 28(1): 84-104.)

[3] 吴信东,李毅,李磊.在线社交网络影响力分析[J].计算机学报,2014,37(4):735-752.(WU X D, LI Y, LI L. Analysis of influence of online social networking [J]. Chinese Journal of Computers, 2014,37(4):735-752.)

[4] LUARN P, YANG J C, CHIU Y P. The network effect on information dissemination on social network sites [J]. Computers in Human Behavior, 2014, 37(37):1-8.

[5] CHEN Z, TAYLOR K. Modeling the spread of influence for independent cascade diffusion process in social networks[C]// Proceedings of the 2017 International Conference on Distributed Computing Systems Workshops. Piscataway, NJ: IEEE, 2017:151-156.

[6] WENG J, LIM E P, JIANG J, et al. TwitterRank: finding topic-sensitive influential ers [C]// ACM 2010: Proceedings of the 2010 ACM International Conference on Web Search and Data Mining. New York: ACM, 2010:261-270.

[7] LI Z, LI M, JI W. Modelling the public opinion transmission on social networks under opinion leaders [C]// AEECE 2017: Proceedings of the 2017 3rd International Conference on Advances in Energy, Environment and Chemical Engineering. Bristol: IOP Publishing,

2017:012215.

[8] 毛佳昕,刘奕群,张敏,等.基于用户行为的微博用户社会影响力分析[J].计算机学

报,2014,37(4):791-800.(MAO J X, LIU Y Q, ZHANG M, et al. Analysis of social influence of Weibo users based on user behavior [J]. Chinese Journal of Computers, 2014,37(4):791-800.)

[9] 廖祥文,张凌鹰,魏晶晶,等.融合时间特征的社交媒介用户影响力分析[J].山东大学学报(理学

版),2018,53(3):1-12.(LIAO X W, ZHANG L Y, WEI J J, et al. An analysis of social media users’ influence on the integration of time characteristics [J]. Journal of Shandong University (Natural Science), 2018, 53(3):1-12.)

[10] SU S, WANG Y, ZHANG Z, et al. Identifying and tracking topic-level influencers in the microblog streams [J]. Machine Learning, 2017, 107(3): 551-578.

[11] 周东浩,韩文报.DiffRank:一种新型社会网络信息传播检测算法[J].计算机学报,2014,37(4):884-3.(ZHOU D H, HAN W B. DiffRank: a new social network information propagation detection algorithm [J]. Chinese Journal of Computers, 2014,37(4): 884-3.)

[12] 祝升,周斌,朱湘.综合用户相似性与话题时效性的影响力用户发现算法[J].山东大学学报(理学版),2016,51(9):113-120.(ZHU S, ZHOU B, ZHU X. User discovery algorithm based on comprehensive user similarity and topic time effectiveness[J]. Journal of Shandong University (Natural Science), 2016, 51(9):113-120.)

[13] WU J, SHA Y, LI R, et al. Identification of influential users based on topic-behavior influence tree in social networks[C]// Proceedings of the 6th Conference on Nature Language Processing and Chinese Computing. Dalian: [s.n.], 2017: 477-4. [14] GOTEZ M, LESKOVEC J, MCGLOHOM M, et al. Modeling blog dynamics[C]// Proceedings of the 2009 International Conference on Weblogs and Social Media. Menlo Park, CA: AAAI Press, 2009: 26-33.

[15] LIN W, PANG X, WAN B, et al. MR-LDA: an efficient topic model for classification of short text in big social data [J]. International Journal of Grid and High Performance Computing, 2016, 8(4): 100-113.

[16] HU M, HANG G, ZHOU J, et al. A method for measuring social influence of micro-blog based on user operations[C]// Proceedings of the 2017 International Conference information Technology and Applications. Sydney: ICITA, 2017: 82-87.

[17] 丁兆云,周斌,贾焰,等.微博中基于多关系网络的话题层次影响力分析[J].计算机研究与发展,2013,50(10):2155-2175.(DING Z Y, ZHOU B, JIA Y, et al. Analysis of topic influence on multi-relational networks in Weibo[J]. Journal of Computer Research and Development, 2013, 50(10):2155-2175.)