基于多关系与属性的主题层次影响力评估算法

刘久云,黄廷磊,夏 威,华绿绿

(桂林电子科技大学计算机科学与工程学院,广西桂林 541004)

基于多关系与属性的主题层次影响力评估算法

刘久云,黄廷磊,夏 威,华绿绿

(桂林电子科技大学计算机科学与工程学院,广西桂林 541004)

为准确分析和度量微博用户在主题层次的影响力,提出一种综合考虑用户多关系与个人属性的影响力评估算法。该算法以主题为单位,对用户交互行为进行分析,构建了包含转发关系、评论关系、复制关系和提及关系的多关系网络,并给出转移概率计算模型;从用户活跃度、用户权威度、博文质量、粉丝质量4个角度考虑,构建了基于主题的用户个人属性影响力指标体系,并使用层次分析法给出各指标的权重;基于PageRank算法思想,提出了融合用户关系与属性特征的影响力计算方法。通过新浪微博数据集的对比实验,证明了算法的准确性和有效性。

主题影响力;多关系网络;个人属性;PageRank;微博

近年来,微博因其即时性、灵活性、集成性和草根性等特征,成为网络舆论的主要来源地和重要集散地。研究发现,微博中存在小部分具有较高影响力的用户,其发布的言论观点往往能影响大批粉丝和舆论走向,对信息传播、话题形成、舆论引导起着关键作用[]。

微博舆情的主题极为宽泛,话题涉及政治、经济、文化等各个领域。同时,微博用户覆盖社会各个阶层及领域,每个人在不同主题下的影响力均不相同。用户有其擅长的领域,从而能够成为这个领域的影响力用户,在这个领域内能得到更多用户的认可[2]。因此,在大量的微博信息中识别每个主题空间下的影响力个体[3],对于准确把握社会舆情动态进而科学引导舆论导向具有重要的现实意义。

微博影响力作为微博研究的一个热点,吸引了众多学者的目光,但针对主题层次的影响力个体挖掘探讨相对较少。文献[4]基于改进的PageRank提出Topic-sensitive PageRank算法,它优于PageRank的地方是其随机跳转概率具有主题选择性,但未考虑用户之间交互概率的差异性。文献[5]针对Twitter数据集提出了话题层次的影响力度量方法Twitter Rank,它综合考虑了话题相识性和网络结构,但忽略了提及、评论和转发等影响因素。文献[6]为识别每个话题的影响力用户,考虑了Twitter用户的发帖数、被转发数和被提及数等多个属性信息,但未考虑用户间的多种关系网络。文献[7]综合考虑了转发关系、回复关系、复制关系和阅读关系4种网络关系,在一定程度上提高了度量准确度,但未考虑活跃度、博文质量等用户属性特征。

现有方法均未对个体影响力相关的多关系网络和个体属性进行有效结合,不能全面地度量微博用户在主题级别的影响力。为此,利用PageRank算法思想,提出一种关系与属性的主题层次用户影响力评估(comprehensive influence rank,简称CIRank)算法。

1 多关系网络概率计算模型

微博信息通过关注网络进行传播,用户发布的任何信息都出现在其粉丝的主页上,粉丝随时从其关注者那里获取随机的新信息。用户受关注者的影响,随机产生阅读、收藏、复制、转发、评论和提及等行为。阅读和收藏行为只是自我吸收的过程,并不会促进消息的对外传播,无法对其他用户产生影响力。复制和转发行为会使微博内容被更多的人分享和传播,评论和提及行为则会吸引更多的人参与话题。后4种行为对信息传播范围和速度产生积极的影响,从而增强用户的影响力。基于文献[7]的多关系网络分析思想,引入促进影响力传播的提及行为,改进分析阅读行为的不足,构建主题空间下的包含转发、评论、复制和提及4种网络关系的多关系网络,并给出不同网络间跳转概率的更合理的计算方法。

1.1 问题定义

用户ui受到其关注者uj的影响,以一定的概率随机产生4种明显的交互行为:1)ui转发uj的博文; 2)ui评论uj的博文;3)ui复制uj的博文;4)ui在其博文中提及uj。据此,用户之间的关注网络可分解为转发、评论、复制和提及4种影响关系网络。

将主题t空间下的微博用户与他们之间的多网络关系抽象为一个有向加权图

其中:k=1,2,3,4分别为转发、评论、复制和提及关系;Vtk为第k种关系网络中的用户集合;Etk为相应网络中的所有关系边集;Wtk( Etk)为关系边Etk的权重。

1.2 多关系网络中的转移概率计算模型

由于用户擅长的领域不同,同一主题空间下,不同用户受到影响后,表现的交互行为习惯也不同,如部分用户习惯转发,部分用户习惯评论,即不同用户由于受关注者的影响而停留在4种关系网络的概率不同。同时,用户在4种影响网络内部以一定转移概率沿着网络随机游走。

给定一个主题t,令用户vti处于第k种关系网络的概率用Qtk(vti)表示,且有∑Qtk(vti)=1,则主题t k=1空间下的多关系影响网络中用户间的转移概率矩阵定义为Ptk。

1.2.1 转发网络

定义1 转发概率矩阵Pt1的每个元素Pt1(vti, vtj),即用户vti随机转发vtj微博的概率计算公式为:

其中:wt1(vti,vt)为主题t空间下转发网络中用户vtij转发用户vtj微博的次数;∑wt1(vti,vt)为主题t vt∈(vt)iout空间下转发网络中用户vti转发其所有关注者的总次数。

1.2.2 评论网络定义2 评论概率矩阵Pt2的每个元素Pt2(vti, vtj),即用户vti随机评论vtj微博的概率计算公式为:

其中:wt2(vti,vtj)为主题t空间下评论网络中用户vti评论用户vtj微博的次数;∑wt2(vti,vt)为主题t vt∈(vt)iout空间下评论网络中用户vti评论其所有关注者的总次数。

1.2.3 复制网络定义3 复制概率矩阵Pt3的每个元素Pt3(vti,vtj),即用户vti随机复制vtj微博的概率计算公式为:

其中:wt3(vti,vt)为主题t空间下复制网络中用户vtij与vtj复制关系的权重;∑wt3(vti,vt)为主题t空vt∈(vt)iout间下复制网络中用户vti与其所有关注者复制关系的权重。

由于不存在明确的“复制关系”,采用文献[7]的方法进行推断。首先,判断2篇博文ctm、ctn的时间间隔Δtrange是否满足Δtrange=0～1.08×105;若满足,则判断博文的相似度S(ctm,ctn)是否高于0.8,相似度计算使用KL距离(kullback-leibler divergence)方法;若2个条件均满足,则认为博文ctm复制了博文ctn。式(3)的wt3(vti,vtj)计算方法为:

其中:Uti,j为主题t空间下用户vti与vtj存在复制关系的博文二元组集合。f(Δt)为其概率密度函数:

1.2.4 提及网络

定义4 提及概率矩阵Pt4的每个元素Pt4(vti, vtj),即用户vti在微博中随机提及vtj的概率计算公式为:v∈(v)iout

其中:wt4(vti,vtj)为主题t空间下提及网络中用户vti提及用户vtj的次数;∑wt4(vti,vt)为主题t空间

vt∈(vt)

iout下提及网络中用户vti提及其所有关注者的总次数。

1.3计算不同网络间的跳转概率

由于同一主题空间下不同用户的交互行为习惯不同,算法基于实测数据统计结果,计算用户在4种关系网络的停留概率。

定义5 主题t空间下用户vti停留在转发网络的概率定义为:iout

其中:∑wt1(vti,vt)为主题t空间下用户vti转发vt∈(vt)iout 4其所有关注者的总次数;∑∑wtk(vti,vt)为主k=1vt∈(vt)iout题t空间下用户vti转发、评论、复制和提及所有关注者的总次数。定义6 主题t空间下用户vti停留在评论网络的概率定义为:v∈(v)iout

其中:∑wt2(vti,vt)为主题t空间下用户vti评论vt∈(vt)iout其所有关注者的总次数。

定义7 主题t空间下用户vti停留在复制网络的概率定义为:

其中:∑wt2(vti,vt)为主题t空间下用户vti复制vt∈(vt)iout其所有关注者的总次数。

定义8 主题t空间下用户vti停留在提及网络的概率定义为:

其中:∑wt2(vti,vt)为主题t空间下用户vti提及vt∈(vt)iout其所有关注者的总次数。

2 用户个人属性影响评估模型

用户的个人属性特征,如活跃度、博文质量、名人身份等,也在一定程度上决定其微博影响力大小。由于用户擅长的领域不同,其在不同主题空间下的表现也不同,如经济专家在经济相关主题下的博文数量、原创比和质量通常都比较高,相应的博文被转发、评论次数也多,则其在主题下对其他用户产生的影响力也比较大;相反,其在娱乐、体育等相关主题下的影响力则要弱很多。因此,算法引入个人属性特征对影响力的作用,构建了主题空间下的用户个人属性影响指标体系,并使用层次分析法获得各指标的权重。

2.1 影响指标体系构建

用户个人属性较多,包括发布、提及等行为属性和关注数、是否认证等状态属性,这是个人属性影响因素测量复杂的一个重要原因。由于用户有一定的擅长领域,每个用户在不同主题空间下的个体属性特征也不同。算法以推动信息传播为出发点,以主题为单位,从用户活跃度、微博质量、用户权威度和粉丝质量4方面考虑,分析大多数重要的影响指标。

1)用户活跃度。活跃用户经常发布新微博或转发一些高质量的博文,从而更能引起关注;原创微博通常包含了用户对新信息独到的思想和见解,容易吸引用户参与讨论。所以,用户越活跃,其对粉丝产生的影响力可能越大。用户活跃度考虑平均发布微博数、平均转发微博数及微博原创比。

主题t空间下,用户vts平均每天发布的微博数为:

其中:d(vts)为用户vts的微博使用天数;ct1(vts)为用户vts在主题t空间下发布的博文总数。主题t空间下,用户vts平均每天转发的微博数为:

其中:ct2(vts)为用户vts在主题t空间下转发的博文总数。主题t空间下,用户vts的微博原创比为:

2)微博质量。用户微博被转发的平均次数越多,表示博文价值越大,通过转发的博文会以级联的方式继续传播下去,对更多的用户产生影响;用户通常会评论认同有独特视角的微博来表达自己的见解,平均微博被评论率越大,表示用户的博文越容易引起互动;两者分别代表了博文影响的广度和深度。微博质量考虑用户微博被转发及被评论的平均次数。

主题t空间下,用户vts的微博被转发的平均次数为:ct(vt)1s

其中:∑ct4k为用户vts在主题t空间下的所有博文k=1被转发的总次数。主题t空间下,用户vts的微博被评论的平均次数为:ct(vt)1s

其中:∑ct5k为用户vts在主题t空间下的所有博文k=1被评论的总次数。3)用户权威度。微博中带有“V”的VIP实名认证用户通常为领域专家、名人和媒介精英人士,信任度很高,而名人效应在信息传播中的影响力是普通用户不能比拟的;用户在主题空间下的被提及率反映了用户在主题内的影响力和被关注度,用户被提及率越高,表示在主题内的影响力越大。用户权威度考虑是否认证和被提及率。主题t空间下,用户vts的被提及率为:

其中:ct6(vts)为用户vts在主题t空间下的被提及次数,∑ct6(vt)为主题t空间下提及的总人次数。若vt∈Vt用户vts为认证用户,则认证指标At7(vts)值为1,否则为0。

4)粉丝质量。优质粉丝越多,则用户博文的潜在二次传播范围越广,其博文产生的影响力就越大。用户的粉丝质量体现为VIP实名粉丝比率。

主题t空间下,用户vts的粉丝认证比率为:

其中:NtV,followers(vts)为用户vts在主题t空间下的多关系网络中的实名认证粉丝数;Ntfollowers(vts)为用户vts在主题t空间下的多关系网络中的所有粉丝数。

2.2 基于个人属性特征的影响力计算

定义用户vts在主题t空间下的个人属性特征影响力为:

其中:Atj(vts)为用户vts在主题t空间下的第j个影响指标值;ωj为第j个影响指标的权重。

算法采用层次分析法[8]确定不同指标在反映用户个人属性特征影响力的权重。层次分析法可使不同指标的差异得到量化,综合考虑时更能准确反映实际的影响情况。根据个人属性特征影响指标体系,将各影响指标的权重表示为ω={ω1,ω2,ω3,ω4,ω5,ω6, ω7,ω8},并将各影响指标归一化,然后用层次分析法确定各指标权重,并验证一致性。

3 融合多关系与个人属性的影响力评估模型

令主题t空间下用户vts的综合影响力为FtCIR(vts),根据PageRank思想,综合考虑用户在4种网络中的跳转概率和个人属性特征影响因素, FtCIR(vts)的计算公式为: FtCIR(vts)=d×

其中:k=1,2,3,4分别为主题t空间下的转发网络、评论网络、复制网络和提及网络;FtPAI( vts)为用户vts的个人属性特征影响力;∑Ft( vt)为主题tPAIj(vt,vt)∈Etijk空间下的第k种影响网络中,与用户vti存在第k种关系的所有关注者的个人属性特征影响力之和;Nt为主题t空间下的所有用户数;d为阻尼因子,取经验值0.85。

由PageRank算法可知,式(19)是收敛的,经过有限次迭代,计算结果将趋于稳定,从而得出最终的个体影响力排名。由式(19)可知,用户在主题空间下的影响力不仅由粉丝的影响力决定,用户自己在主题空间下的个人属性信息也起很大的作用,从而排除了垃圾粉丝的干扰。

4 实验分析

4.1 实验方案

4.1.1 数据准备

从新浪微博平台获取实验数据,收集了新浪微博2014年的50个热点话题,然后分别选取了社会、体育、电影、科技和财经领域参与人数最多的2个主题,采用分属于5个不同领域的10个主题作为测试集。选定主题后,获取主题下参与用户的所有微博信息和个人属性特征信息,包括转发、评论等行为属性和是否认证、转发数、评论数等状态属性。

数据经处理后,首先运用层次分析法,计算得到用户个人属性特征影响力的各影响指标的权重,ω= {0.226,0.028,0.011,0.228,0.023,0.228,0.095, 0.161},通过了一致性检验。

4.1.2 多种影响力分析算法对比验证

为验证算法CIRank的准确性和有效性,将CIR-ank与多种相关算法进行对比验证。主要考虑了以下5种算法:

1)综合考虑用户多关系网络与个人属性特征的用户影响力分析算法CIRank。

2)仅考虑多关系网络的影响力挖掘算法Multirelation Rank,计算公式为:

3)文献[7]提出的基于多关系网络的微博话题层次的影响力分析算法MultiRank。

4)文献[5]提出的综合考虑了话题相识性和网络结构的主题级别的影响力个体挖掘算法Twitter Rank。

5)根据粉丝数目衡量微博用户的影响力的Follower Rank算法,Twitter和许多第三方服务均采用此算法对影响力进行排序。

4.1.3 评价指标

社交网络上的用户影响力分析的评测无统一的衡量标准,因此,采用文献[7]的交叉验证方法得到参考标准结果值,分别验证每种算法的准确率、召回率和F值,以此来对比算法的性能。

交叉验证法为取多种(N种)算法都认为正确的结果作为参考的正确结果,研究发现N值为3时,效果最佳。令5种对比算法得到的前K名高影响力个体集合,分别表示为U1、U2、U3、U4和U5,则参考标准影响力个体集合U为5个结果集三三相交后取并集的结果集。

准确率为预测正确的影响力个体数与预测出的影响力个体总数的比值,衡量算法的查准率;召回率为预测正确的影响力个体数与参考标准影响力个体总数的比值,衡量算法的查全率;F值则为准确率和召回率的调和平均值,反映算法的整体性能。

4.2 实验结果及分析

4.2.1 算法准确率、召回率验证

分别采用CIRank算法与4种对比算法获得所有主题下的个体影响力排名,针对每个主题,取每种算法排序结果中的前20、50、100、150、200、300名高影响力个体,使用交叉验证方法分别计算算法的6项准确率、召回率,然后计算得出各算法在每个主题下的平均准确率和召回率,结果如图1、2所示。

图1 各算法在每个主题下的平均准确率Fig.1 The average precision rate of each algorithm under each topic

图2 各算法在每个主题下的平均召回率Fig.2 The average recall rate of each algorithm under each topic

从图1、2可看出,在所有主题下,提出的影响力个体挖掘算法CIRank均可达到90%以上的准确率和召回率,在所有算法中表现最佳,证明了该算法的有效性;同时,仅考虑多关系网络的影响力挖掘算法Multi-relation Rank相对MultiRank算法而言,其准确率和召回率均有明显提升,证明算法对多关系网络概率模型的改进,即将阅读网络替换为提及网络及根据每个用户在各主题下的实际交互行为习惯计算不同网络间的停留概率,对挖掘结果起到很大改善作用。图1、2的实验结果表明,综合考虑多关系网络和个人属性特征的CIRank算法的平均准确率和召回率相对于Multi-relation Rank算法,有非常显著的提升,说明用户在每个主题下的个人属性特征起到很大的作用。

4.2.2 算法F值验证

为从整体上验证CIRank算法的性能,综合考虑准确率和召回率,分别针对排序结果中的前20、50、100、150、200、300名高影响力个体计算各算法的F值,然后计算各算法在每个主题下的平均F值,实验结果如图3所示。

图3 各算法在每个主题下的平均F值Fig.3 The average F value of each algorithm under each topic

从图3可看出,在所有主题下,CIRank算法相比其他算法整体性能都是最优的,Multi-relation Rank算法由于对多关系网络概率模型的改进,其整体性能比MultiRank要高一些,Twitter Rank算法和Follower Rank算法的整体性能相对较差,而Follower-Rank由于仅根据粉丝数量进行排名,性能最差。

5 结束语

以主题为单位,分析了转发、评论、复制和提及4种受影响交互行为,构建了用户多关系网络,并给出了基于多关系网络的概率计算模型。同时,引进个人属性特征对影响力的作用,分析了用户活跃度、微博质量、用户权威度和粉丝质量4个方面的相关影响因素,构建了主题空间下的个人属性特征影响指标体系。“僵尸粉”和“水军”的博文原创性、粉丝质量和权威度等通常都很低,因此,引入个人属性影响体系在一定程度上排除了“僵尸粉”和“水军”对影响力个体挖掘结果的影响。多种对比算法的交叉验证实验结果表明,提出的综合考虑用户多关系网络与个人属性特征的影响力挖掘算法CIRank优于其他相关算法。构建的个人属性特征影响指标体系采用层次分析法确定各影响指标的权重,一定程度上会受到人为因素的干扰,研究更准确的影响指标权重计算方法将是下一个研究方向。同时,探究多关系网络和个人属性特征影响力的更加有效的结合方式将是下一步的工作重点。

[1] 肖宇,许炜,商召玺.微博用户区域影响力识别算法及分析[J].计算机科学,2012,39(9):38-42.

[2] 尹衍腾,李学明,蔡孟松.基于用户关系与属性的微博意见领袖挖掘方法[J].计算机工程,2013,39(4):184-189.

[3] Rogers E M.Diffusion of Innovations[M].New York: The Free Press,1962:102-120.

[4] Haveliwala T H.Topic-sensitive PageRank[C]//Proceedings of the 11th International Conference on World Wide Web.New York:ACM Press,2002:517-526.

[5] Weng Jianshu,Lim E P,Jiang Jing,et al.Twitterrank: finding topic-sensitive influential twitters[C]//Proceedings of the Third ACM International Conference on Web Search and Data Mining.ACM,2010:261-270.

[6] Pal A,Counts S.Identifying topical authorities in microblogs[C]//Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, 2011:45-54.

[7] Ding Zhaoyun,Jia Yan,Zhou Bin,et al.Mining topical influencers based on the multi-relational network in micro-blogging sites[J].China Communications,2013,10 (1):93-104.

[8] 王莲芬,许树柏.层次分析法引论[M].北京:中国人民大学出版社,1990:42-56.

编辑:梁王欢

Topical influence evaluation algorithm based on multi-relationship and personal attributes

Liu Jiuyun,Huang Tinglei,Xia Wei,Hua Lülü
(School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

To accurately analyze and measure the topical influence of micro-blog users,a new influence evaluation algorithm based on multi-relationship and personal attributes is presented.Taking topic as unit,the multi-relational influence network including repost,comment,copy and mention relations is constructed by analyzing user interaction behavior,and the transition probability calculation model is given.In consideration of user activity,user authority,micro-blog quality and follower quality,an index system of user’s personal attributes influence based on the topic is constructed,and the weight of each indicator is given by using the method of analytic hierarchy process(AHP).Finally,a calculation method of influence based on PageRank is designed by fusing user relations and attributes.A large number of experiments according to real data sets show that the proposed method is accurate and effective.

topical influence;multi-relational network;personal attribute;PageRank;micro-blog

TP393

:A

:1673-808X(2015)04-0329-07

2015-03-26

国家863计划(2012AA011005)

黄廷磊(1971―),男,安徽肥东人,教授,博士,研究方向为数据挖掘、无线Mesh网络等。E-mail:tlhuang@guet.edu.cn

刘久云,黄廷磊,夏威,等.基于多关系与属性的主题层次影响力评估算法[J].桂林电子科技大学学报,2015,35(4):329-335.