基于PageRank和最短路径的用户影响力评估

张俊豪

（铁道警察学院公安技术系 河南 郑州 450003）

1 引言

微博作为我国主流的社交网络之一[1]，每一次社会舆论的酝酿、传播、爆发都与其有着直接的关系，其中，微博中那些重要的微博用户对舆论的引导、走向起着至关重要的作用。通过衡量微博用户影响力可以挖掘出影响舆论发展的重要用户、预测舆论的发展方向、确定微博网络的核心框架以及为其他的研究奠定理论接触等[2]。目前对用户影响力的研究已经取得了很大突破，根据算法种类可将前期研究分为4类：①基于PageRank的用户影响力评估模型。主要有王彪的peoplerank算法[3]、陈少钦的实时用户影响力算法等[4]。②基于微博行为的用户影响力评估模型。主要有肖宇的基于用户行为特性的评估模型[5]、齐超的三大网络评估模型[6]、朱郭峰的主题行为评估模型[7]、Ye等人的行为对比评估模型等[8]。③基于路径的用户影响力评估模型。主要有郭浩等人的基于直接影响力和级联影响力的用户影响力评估模型[9]、陈灿的K-覆盖度评估模型[10]。④其他用户影响力评估模型。主要是利用博弈论、传染病模型等进行用户影响力评估。

以上的评估模型各有优缺点，但都未能从用户所处微博中的关键位置出发去衡量用户影响力。本文综合运用图论、微博网络特性、社会学等知识，提出一种基于PageRank和最短路径的用户影响力算法（User Influence Assessment Based on PageRank and Shortest Path，UIA-PSP）。

2 PageRank算法原理

PageRank算法通过网页之间的链接关系得到网页权值，算法主要有以下两个核心思想[11]：

（1）一个网页的链入链接越多，该网页就越重要。

（2）一个高权威网页链接至另一个网页，那么被链接的网页也非常重要。

PageRank算法的计算过程如图1所示。

图1 网页结构图

假设，在图1中，存在着4个网页的拓补结构，其中网页D在指向网页A的同时又指向了其他两个网页。其中网页A的PR值如公式 （1）所示：

若用有向图G (V,E)表示万维网的话，那么V代表网页集，E代表超链接集。其中网页i的权威值可用公式（2）所示：

公式（2）中，P(i)代表网页i的权威值，O(j)表示网页j的链出链接总数，（i,j）代表网页j指向网页i的链接。根据万维网中存在着悬垂叶等特征，Google最终将PageRank的计算公式确定为公式（3）所示：

公式（3）中，P代表网页的权威向量，d代表阻尼系数，e代表单位矩阵，B是网页的链接关系得到的转移矩阵。

3 基于PageRank和最短路径的用户影响力评估算法

万维网由大量的网页和链接组成，微博由大量的用户和关注关系组成，都可以用有向图表示，所以，用户影响力的评估可以借鉴PageRank算法。微博和万维网的拓扑结构有所相似，也有所不同，网页之间除了链接关系，其他的关系几乎不存在，微博用户之间除了关注关系，还存在着转发微博、提及、评论等诸多行为关系，所以，在衡量微博用户影响力的同时，应考虑微博用户行为这一核心要素。

3.1 微博网络加权图的构成

用有向图G (V,E)表示微博网络，V代表用户集，E代表关注关系集。关注关系涉及到评论X、转发、提及等多种用户行为，所以关注关系有着强弱之分，如图2所示。

图2 用户关注网络

图2中的微博用户关注网络中，若用户C同时关注了用户E和用户D，但是用户C对用户D的微博很少转发、评论或者收藏，而对用户E的微博却是频繁的转发、评论等。本文在借鉴PageRank衡量用户影响力时，会根据关注关系的强弱将C的影响力权值多分给用户E，而少分给用户D。

微博用户之间的行为主要有评论、转发、提及。这3种行为对于关注关系的强弱又有着不同程度的影响，从对微博消息传播力度的角度考虑，转发对关系的强度影响最大，提及其次，评论最小。本文采用加权融合的方法量化用户之间的关注关系，并用关注度表示，如图3所示。

图3 用户之间的关注度

根据图3可知，用户之间关注度的大小可由公式（4）表示：

在公式（4）中，A(u,v)代表用户u和v之间的关注度，R代表用户u转发v的微博数，M代表用户u评论v微博的总次数，@代表u提及v的总次数，用户的关注度具有方向性。α，β，γ表示相应因素的权值。由于微博用户实际中的评论、转发和提及都不是在一个数量级，若直接进行加权计算，会面临着大数吃小数的问题，所以要对每种行为数值进行归一化处理。本文采用离差标准化对这些行为数据进行线性变换，如公式（5）所示：

在公式（5）中 Yi是归一后的用户转发值（评论值，提及值），Xi是归一前的用户转发微博数值（评论值，提及值），mini是用户i在转发（评论，提及）所有微博对象中，转发值（评论值，提及值）最小的那个，同理maxi代表其最大的用户转发值（评论值，提及值）。在经过归一化处理之后，用户之间的关注度可由公式（6）表示：

在公式（6）中A(U,V)‘代表经过归一化处理之后的用户关注度，R’代表经过归一化处理之后的转发数，M’代表经过归一化处理之后的评论数，@’代表经过归一化处理之后的提及数。在微博关注网络图中，加上用户之间的关注度，可得到微博网络加权图。

3.2 权值分配计算

通过两个用户之间的关注度可以衡量用户传播消息的局部能力，却不能从全局的角度衡量用户传播消息的能力。本文根据用户在微博网络中所处的关键位置，从全局的角度衡量用户传播消息的能力。

时效性是研究微博舆情的一个主要观测点，在微博网络中，用户能否以最快的方式将消息传播出去是衡量用户影响力的关键因素。在微博网络加权图的基础之上，通过用户处于其他用户到自己粉丝的最短路径上的频率衡量用户的全局影响力，如图4。

图4 微博网络加权图

在图4中，箭头表示消息的走向，箭头上的数值表示关系权值。为了计算的方便，将用户之间的关注度进行取逆运算得到用户之间的关系权值，即关系权值越小，关系越强。

图4中，若A想要获取D的微博消息，根据Floyd算法可知，消息最快的传播路径应是D-＞B-＞A，而不是D-＞C-＞A，尽管A对C的关注关系很强，但是B对D的关注关系更强，消息的走向不仅依赖于A的关注关系，也依赖于B的关注关系。同样，根据Floyd算法可知B、D、E、F、G用户的微博消息若想以最快的方式流向A，都经过B，说明B对A的影响力比C对A的影响力更强。

通过以上分析可知，一个用户处于其他用户之间最短路径上的频率越大，该用户对微博消息的传播作用力更强。例如在图4中，所有节点到节点A的最短路径中，通过B的有5次，通过C的有1次，那么A则将自己的影响力均分为6份，5份给B，1份给C。

3.3 算法核心

根据文中3.1和3.2的描述，在PageRank算法的基础上，本文的算法核心基本上有以下3点：①粉丝数决定用户影响力。②关注度决定用户影响力。③位置决定用户影响力。

本文UIA-PSP算法的核心可用公式（7）表示：

在公式（7）中，参照PageRank的公式，可知UIA-PSP（v）为v的用户影响力，e为单位矩阵，F为根据用户的关注关系和Floyd得到的转移矩阵，即F（u,v）代表粉丝u贡献给用户v的比例值。其中F（u,v）可通过公式（8）确定：

在公式（8）中，t(i,v,u)表示微博网络中其他任意节点i经过用户V达到用户u的最短路径数目，t(i,u)表示微博网络中其他任意节点i到用户u的最短路径数目。

因此，UIA-PSP算法的核心结构可如图5所示。

综上所述，UIA-PSP算法的核心可用如下伪代码所示：

本算法中，根据Google给出参数建议，将阻尼因子d取值为0.85，ε取值为0.00001。根据层次分析法（AHP）可确定UIA-PSP算法中的参数为：α= 0.65A，β=0.0638，γ=0.2746[12]。

4 实验及结果分析

本文的实验数据是在数据堂提供的原始信息之上，利用微博爬虫得到用户之间的行为信息，主要的信息包含2012年1月1日至2016年1月1日的关注关系、转发数目、评论数目、提及数目。最终得到的实验数据包含114名用户，703条关注关系。部分实验数据如图6所示。

图6 实验的部分数据

为了进行实验的对比分析，本文采用PageRank算法和基于用户的粉丝数衡量用户影响力的算法（User Influence Assessment Based on the number of User’ Fans，UIA-UF）作为UIA-PSP算法的两种对比算法，进行综合的分析比较。

采用UIA-PSP对用户影响力进行排序，排序结果如图7所示。

图7 UIA-PSP排序结果

采用PageRank对用户影响力进行排序，排序结果如图8所示。

采用UIA-UF对用户影响力进行排序，排序结果如图9所示。

本文采用P@N作为实验分析指标，衡量UIAPSP算法的准确性，P@N的计算公式，如公式（9）所示：

在公式（9）中，AN∩BN代表算法A（B）得到的前N名用户影响力的交集量，本文N的取值分别为10、20、30、40、50、60、70、80。

图8 PageRank排序结果

图9 UIA-UF排序结果

若将以UIA-UF为基线模型，以PageRank和UIAPSP为对比模型，那么对比模型所得结果在P@N指标下的表现如表1所示。

表1 以UIA-UF为基线算法的P@N值测试结果

若以PageRank为基线模型，以UIA-UF和本文的UIA-PSP算法为对比模型，那么对比模型所得结果在P@N指标下的表现如表2所示。

表2 以PageRank为基线算法的P@N值测试结果

从表1和表2中，通过UIA-PSP得到用户影响力排名结果的准确率与N值成正比例。在表1中，以UIA-UF为基线模型时，PageRank得到结果的准确率高于UIA-PSP，并且幅度从0～50%不等，这说明UIA-PSP相比PageRank对用户影响力的排名进行了调整。在表2中，以PageRank为基线算法时，UIA-PSP得到结果的准确率总体上高于UIA-UF，并且幅度从0-30%不等。这可以得出两个结论：①PageRank与UIA-UF更为相似。②UIA-PSP与两个算法对比都各有不同。

在UIA-PSP中，粉丝最多的27号用户仅排名23位，在PageRank中排名28位，这说明了在UIA-PSP算法中，粉丝仅是衡量用户影响力的一个因素，但不是决定性因素。在PageRank算法中排名第一的57号用户，在UIA-PSP算法中排名第56位，因为57号用户拥有大量的粉丝，而且其中有3个粉丝的用户影响力很大，所以PageRank得到的57号用户影响力就很大；在UIA-PSP中，其他用户之间的最短路径中经过57号用户的数量很少，所以排名有所下滑。类似的用户还有21、86号用户。在UIAPSP得到的用户影响力排名结果中，22号用户排名第一，因为通过22号用户的最短路径多达312条，也是因为22号用户的部分粉丝影响力很大，所以22号用户获得了较多的用户影响力贡献值。类似的用户还有11、81号用户等。这可得出第3个结论：UIA-PSP算法能够通过用户处传播消息的能力衡量用户的影响力。

通过实验可知，UIA-PSP算法根据用户关注度衡量用户的局部影响力，又根据用户处于其他用户之间的最短路径上的频率衡量用户的全局影响力。在公安工作中，可将此算法作为参考，进行舆情的实时管控。例如在微博网络中，可通过用户的关注度找出那些粉丝真正关注的用户，也可通过用户处于其他用户之间的最短路径上的频率找出推动微博消息快速传播的用户。在出现微博舆情时，可实现对重点人员和幕后推动舆情发展人员的实时监控，而不是对那些仅仅拥有众多粉丝数的“大V”进行盲目的监控。另外通过本算法，可提取出微博舆情传播的主体框架，对舆情的下一步发展以及舆情的导控做出科学的判断。

5 小结

本文在PageRank和最短路径的基础上提出了UIA-PSP算法，既根据用户行为考虑到了用户的局部影响力，又根据用户在微博中的位置考虑了用户的全局影响力。实验结果证明了UIA-PSP具有较高的说服力。

参考文献：

[1] 张坤.国内微博的传播形态与发展研究[D].南昌:江西师范大学,2012:6-15.

[2] Maksim Tsvetovat,Alexander Kouznetsov.社会网络分析方法与实践[M].王薇,王成军,王颖,等译.北京:机械工业出版社,2013:13-45.

[3] 王彪.社交网络中的用户影响力分析[D].哈尔滨:哈尔滨工业大学,2012:4-19.

[4] 陈少钦.基于PageRank的社交网络用户实时影响力研究[D].上海:上海交通大学,2013:12-33.

[5] 肖宇.校园网络信息传播特性与用户影响力研究[D].武汉:华中科技大学,2012:8-55.

[6] 齐超,陈鸿昶,于洪涛.基于用户行为综合分析的微博用户影响力评价方法[J]. 计算机应用研究,2014(7):2004-2007.

[7] 朱郭峰,杨彦,周竹荣,等.基于领域的微博用户影响力计算方法[J].西南大学学报(自然科学版)2014(3):145-151.

[8] Ye S,Wu S F.Measuring Message Propagation and Social Influence on Twitter.com[J]．International Journal of Communication Networks & Distributed Systems,2010(1):216-231.

[9] 郭浩,陆玉良,王宇,等.基于信息传播的微博用户影响力度量[J].山东大学学报(理学版),2012(5):78-83.

[10] 陈灿.微博用户的影响力分析[D].济南:山东大学,2013:16-33.

[11] 刘兵.Web数据挖掘[M].北京:清华大学出版社,2009:66-99.

[12] 郭金玉,张忠彬,孙庆云.层次分析法的研究与应用[J].中国安全科学学报,2008(5):148-153.