PageRank模型的改进及微博用户影响力挖掘算法

毛国君 谢松燕 胡殿军

(中央财经大学信息学院 北京 100081)

PageRank模型的改进及微博用户影响力挖掘算法

毛国君 谢松燕 胡殿军

(中央财经大学信息学院 北京 100081)

随着Web技术的发展，微博逐渐成为当下最流行的社交平台之一。微博中用户影响力计算是相关研究中的焦点问题。通过对PageRank模型的改进，提出一种新的用户影响力挖掘算法PR4WB(PageRank for MicroBlogs)，解决了传统的PageRank算法由于页面权威值的等分传递带来的潜在误差过大的问题。PR4WB算法在考虑微博中用户关系的同时，利用社会网络概念将自身的活跃度、博文质量及可信性加以关联，形成动态的评价模型。基于Twitter数据的实验表明，PR4WB算法能更加准确、客观地反映出用户的实际影响力。

用户影响力 社会网络 微博 推特 PageRank算法

0 引 言

随着大数据时代的到来以及Web2.0技术的应用，在线社会网络得到了快速的发展。微博作为一种重要的社交平台，已经在社会、政治、生活等方面成为不可忽略的舆情传播载体。国内使用最多的微博平台是新浪微博，而国际上使用较为广泛的微博服务则是Twitter。据统计，截至2014年7月，Twitter的活跃注册用户数已超过6亿，而且每日平均新增用户数为135 000，平均每日发表微博数为5 800万。因此，微博是一个用户数目多、博文帖子多的一个现代社交媒介。然而，微博中的用户是不对等的，博文也有轻重之分，所以微博中用户影响力的计算除了简单地考虑用户的链接关系外，也应该综合地利用用户的活跃程度、博文数量及质量和用户的可信度等因素。

已经出现的基于PageRank模型的微博用户影响力计算和排名方法更多地是考虑用户的链接数目，对于用户的博文质量及可信程度关注较少，因此很难客观地评价用户的影响力。特别是，由于缺乏对用户动态表现(如活跃度)、可信度(如是否认证)等的评估，使得计算结果距离实际用户的影响力相差较大。本文将分析传统的PageRank算法在解决微博用户影响力挖掘中可能出现的问题，在此基础上通过嵌入用户活跃度、博文质量及可信度等因素的评估结果，改进传统的PageRank模型，形成适合于微博中用户影响力挖掘的动态评价算法。

1 相关研究及PageRank模型的发展

PageRank模型[1]是由Google公司的两位创始人拉里·佩琪和谢尔盖·布林共同提出的。该模型的最初动因是实现网络上的网页排名，因此该技术被广泛应用到网络的搜索引擎设计中。由于PageRank模型本质上是对有向图的节点等级的计算技术，所以它也能应用到其他的领域。特别地，PageRank算法近年已经被应用到微博的用户影响力排名中。

Tunkelang[2]等利用Twitter用户节点之间的关注(Follow)关系，构造了一张基于链接关系的有向图，并且利用PageRank模型实现了Twitter用户的影响力排序。Weng[3]等也成功地从Twitter中构建了一个好友关系图，并且利用PageRank算法思想提出了一个被称为TwitterRank的算法。之后，Weng[4]等也将用户兴趣加入到评价体系中，改进了TwitterRank算法，可以更好地实现在某一特定话题讨论中的用户影响力分析。

事实上，微博影响力研究已经成为一个重要的交叉研究课题。有3个重要的研究视点被关注：(1) 将微博用户及其交互行为在社会网络的分析框架下进行分析[5-6]；(2) 利用信息传播理论研究微博中的网络传播动力学行为规律，发现传播中的关键用户及其行为[7]；(3) 从数据挖掘观点，进行数据的关联性分析，发现微博中数据隐含的规律性知识[8-9]。这些研究都有一个核心技术支撑，即有向图分析。微博中的用户通过用户间的交互行为可以构成特定的有向图结构；微博中的用户就是有向图的节点、并且微博中的社会关系或者博文传播可以形成有向图的弧；微博中的数据可以在有向图的逻辑结构下实施数据挖掘技术。从这个意义上说，PageRank模型能够将以上3种视点从技术层面上加以统一。

原始的PageRank模型是针对网站中的网页的重要性评估提出来的，通过计算每个页面的权威值来实现页面的等级划分。简单地说，一个页面的权威值就是所有指向该页面的各个页面平均分配给该页面的权威值之和[1]。很显然，基于这样模型的PageRank算法是一个逐层进行节点权威值计算的过程。谷歌公司在实际应用中发现了原始PageRank算法的致命缺点：假如一个页面节点没有出度，特别是入度又很大，就可能造成节点的权威值“滞留”，进而使传递受阻。解决这个问题的基本方法就是引入随机冲浪模型，这也成为目前使用的最广泛的PageRank模型[10]。基于随机冲浪的PageRank模型的页面权威值计算如下：

(1)

其中：PR(x)代表页面x的权威值；d(∈[0,1])为阻尼系数，暗示页面的随机跳转概率为1-d；B(x)表示指向页面x的网页的集合；N(x)表示页面x链出的网页集合。

式(1)给出的模型需要转变成可计算的算法来完成。各种版本的PageRank算法都是通过多次迭代计算实现的，其中最流行的迭代方式是通过所谓的转移概率矩阵技术来实施的[8]。简单地说，一个转移概率矩阵表示为M=(mi,j)，其中mi,j是页面j跳转到页面i的概率。目前使用的PageRank算法大多都是采用等分概率的方法来进行传递的。例如：图1给出了一个4个节点的有向图，对应着4个不同的页面及其链接关系。通过传统的PageRank算法可以获得对应的转移概率矩阵M：

图1 一个页面链接对应有向图

这样，设n是页面节点的数目，R=(r1,r2, …,rn)T表示页面节点的权威值向量，则可以通过多次迭代执行下面的式(2)来逐步逼近式(1)的效果：

Ri+1=(1-d)·I+d·M·Ri

(2)

其中：I为全1向量，即(1,1,…,1)T；Ri(i=1,2,…)是第i次迭代得到的权威值向量；迭代的终止条件可以通过迭代次数或者最近两次的迭代结果的比较来实现。

基于传统的PageRank模型，本文的技术解决方案简单归纳为：首先，利用社会网络概念和分析工具构建微博数据的逻辑分析结构(有向图)；然后，考虑博文传播导致的用户行为的影响力要素，形成节点级的综合的行为评测模型；最后，改进传统的PageRank算法的模式演化过程，形成微博用户影响力的动态挖掘算法。

2 PageRank模型的改进及微博用户影响力挖掘

传统的PageRank模型和算法的思想可以用在微博用户影响力评估中，但是要想获得更准确的评估结果，一个关键的问题需要解决：假如采用传统的PageRank模型来完成平均权威值传递的话，那么实际上是在承认所有的用户是绝对对等的，这和微博中实际用户的情况相差甚远。

虽然微博中的用户关系并不复杂，但是作为一种特殊的社交媒体有其特殊性。例如，最常用社会网络工具是通过用户的“关注(follow)”行为来构建有向图的[8]。然而，微博作为一个公共的开放平台，其用户的权威性或者说重要性差别是很大的。一个大V用户的关注数目远远多于一个普通用户；一个认证用户其传播信息的可信度要明显高于非认证用户；一个致力于推销自己产品的维店用户，即使是博文再多，可能对于大多数用户而言都是当作噪音数据来看待的。因此，如何更准确地确定和实施微博中用户的权威值的传递策略是必须要面对的问题。我们的策略是通过对用户活跃度、博文质量及可信度的评估，按着重要程度形成节点权威值的不对等传递，以真实地反映微博用户的影响力。

用户的活跃度被认为是衡量用户影响力的重要因素之一[10]。典型的微博用户活跃度通过用户在微博平台发表博文的多少来评价，通常使用式(3)[11-12]来计算：

Activity(i)=ni/N

(3)

其中：Activity(i)代表用户i的活跃度；ni是用户i发表的博文数目；N为全部用户发表的微博总数。

依据式(3)，用户活跃度可以很好地反映用户发表博文的数量。然而，除了尊重博文发表越多的用户可能影响力越大这一事实外，至少两个因素需要在评价一个用户的影响力时也要加以考虑：(i)用户发文的质量；(ii)用户的可信度。

用户的质量表示用户发表博文质量的高低，博文质量值越高，就越多人转发。当高质量的博文数发表的多时，说明该用户在这个话题圈内拥有的话语权越高，即权威值越高。有研究把高质量博文定义为转发量超过一定量的博文，用户的质量值即该用户所发的高质量博文的占比。遵循这样的原则，我们把转发量超过300的博文定义为高质量博文，且最简单的评估用户质量值的方式可以用式(4)给出：

Quality(i)=mi/ni

(4)

其中：Quality(i)代表用户i的质量值；mi是用户i发表的高质量博文数目；ni为该用户发表的微博总数。

用户的可信度可以通过是否被微博平台认证来衡量，同时认证用户的好友粉丝数也是影响其可信度的重要因素。根据用户好友粉丝数的多少可以衡量该用户在发微博时能够影响到多少人，好友粉丝数越多就能让越多的人看到微博消息，也就表示该用户的影响力越大。最简单地方法可以通过式(5)完成：

(5)

其中：B(i)和C(i)分别代表用户i的链入和链出节点数目，即用户i的好友粉丝数。

接下来的问题就是如何将用户活跃度、博文质量及用户可信度整合成一个综合评价模型，并把它用于PageRank模型的权威值传递过程中。依据式(3)-式(5)，可以使用式(6)形成一个综合评价参数w(i)：

w(i)=Activity(i)+Quality(i)+Confidence(i)

(6)

于是，w(i)可以用来修正PageRank模型，形成加权转移概率矩阵M=(mi,j)，mi,j表示节点j传递给节点i的权威值，可以通过式(7)来计算：

(7)

对于图1所示的社会网络，假如我们已经获得各个节点的评价参数：w(A)=0.10、w(B)=0.15、w(C)=0.20、w(D)=0.15，则对应的加权转移概率矩阵M为：

使用加权概率转移矩阵，利用PageRank算法思想，我们可以设计一个综合考虑用户活跃度、用户质量及可信度的微博社会网络挖掘算法，称为PR4WB算法。该算法以传统的PageRank算法为技术构架，将影响微博用户影响力的关键因素整合进来。算法1给出了PR4WB的伪代码描述：

算法1 微博用户影响力向量生成算法PR4WB

输入：微博用户社会网络图G；阻尼系数d；迭代终止条件ε；

输出：用户节点的影响力向量R。

过程描述：

2) Fori∈GDo

3) 计算Activity(i),Quality(i),Confidence(i)；

4)w(i) =Activity(i)+Quality(i) +Confidence(i)；

5)Enddo

6)Fori∈GDo

7)Forj∈GDo

9)M=(mi,j)；

10)R0= (1, 1, …, 1)T；I=R0;

11)Repeat

12)R=(1-d) *I+d*M*R0；

13)R0=R；

14)Until‖R-R0‖≤ε；

15) 输出R作为最终的影响力向量。

算法1中的步骤1根据传统的PageRank算法来计算概率转移矩阵；步骤2-步骤5计算用户的活跃度、博文质量和可信度(见式(3)-式(5))；步骤6-步骤9生成加权概率转移矩阵；步骤10-步骤15完成所有节点的影响力计算。

3 实验与分析

实验数据来自于Twitter平台。我们采用Twitter提供的API接口获取了近5年的数据，选取了其中3 049位微博用户，利用Gephi社会网络生成工具形成了包含7万多条(关注)弧的有向图。当然，3 049个用户只是全部Twitter用户中的一小部分，但是这些用户的关系网络是相对完整的，可以用来检验本文算法的有效性和效率。

表1和表2分别给出了利用传统的PageRank算法和本文的PR4WB算法找出的前十名微博用户及其对应的情况。

表1 传统的PageRank算法找出的前十名用户信息表

续表1

表2 PR4WB算法找出的前十名用户信息表

对照表1和表2，对相同的数据，传统的PageRank算法和本文的PR4WB算法找到的影响力最高的前10名用户存在差异。当然，我们不能主观地断定哪个更好，但是表1的一些问题是可以通过分析被发现的。例如：(1) PageRank算法排名第1位用户为非认证用户，而且这段时间发表的博文数据也不多，所以算不上是一个很活跃的用户。通过我们进一步跟踪传统PageRank算法的权威值计算过程发现，这主要是由于该用户的关注者大多具有很高的权威值、进而使他的权威值累计起来很高。(2) 表1中排名第4位的也是一个非认证用户，它的关注数也不算多，但是他的排名也很高。究其原因，是Fenng一位IT界的知名人物，其关注者的影响力很高、而且他很少关注其他的人。

相比较而言，我们根据PR4WB算法要求进行了用户的活跃度、博文质量及可信度的评估，并且使用它们改进了PageRank成PR4WB算法，得到了表2的结果。计算出的影响力排名前十位用户均为认证用户，而且所发的博文数、关注数及好友数都相对较高。另外，我们利用微博的转发功能来评估博文质量，我们发现好友粉丝数多的认证用户的质量值都较高，这是因为认证用户一般都在发布消息时具有一定的权威性，并且其众多的好友粉丝会对其所发出的博文进行转发评论，相较于一般用户，认证用户的影响力更大。实验结果中PR4WB算法得到的前十名用户大多数为新闻媒体的官方微博，这些从一个侧面上可以说明，PR4WB算法所得到的排名与现实生活中的实际用户的影响力更接近。

此外，通过跟踪传统的PageRank算法和本文的PR4WB算法的运行时间，我们测试了两个算法随用户数目增加时对应的执行时间的变化情况。两个算法是在同样的数据集和实验环境下进行的。实验是在四核 CPU、4 GB内存、Windows 7操作环境下的计算机实施的。同时，为了说明随数据容量增加执行时间的增长规律，我们从已经获取的Twitter平台的3 049位用户对应的社会网络图中分别截取了500，1 000，1 500，2 000和2 500个用户对应的网络子图，分别实施PageRank和 PR4WB算法。图2给出了对应的实验结果。

图2 PR4WB算法与PageRank算法所耗时间对比

图2表明：在同样的数据容量下，PR4WB算法的执行时间略高于PageRank算法。这是因为相比传统的PageRank算法，PR4WB算法需要额外计算用户活跃度等动态评估指标，所以自然要高些。然而，两个算法在相同数据容量下，差距并不大；而且，随着数据容量(用户数)的增加，两者的时间攀升趋势相当，都小于线性增长速率。因此，虽然PR4WB算法是以时间为代价来获取比PageRank算法更好的挖掘结果的，但是其时间代价并不高，是一个性价比很高的算法。

4 结 语

通过对微博中用户影响力分析中需要考虑的关键因素分析，提出了一种更适合挖掘微博数据的加权PageRank算法，即PR4WB算法。PR4WB算法对于PageRank算法存在的平分权威值这一问题进行了修正，使得排序结果更客观、准确。通过计算微博用户的活跃度、博文质量及可行度，获得节点的权重，利用权重修正传统的PageRank模型的概率转移矩阵。这样，用户的影响力排序不仅考虑了社会网络中个体之间的链接关系，同时将用户活跃度等动态因素参与影响力的排序中，使得微博用户的影响力评估更全面。实验结果表明，相比于传统的PageRank算法，PR4WB算法用较小的时间代价换取了更准确的评估效果。

[1] Page L,Brin S,Motwani R,et al.The PageRank citation ranking: bringing order to the web:SIDL-WP-1999-0120[R].Technical Report of Stanford University,1999.

[2] 县小平.一种改进的PageRank算法[J].太原师范学院学报(自然科学版),2011,10(1):92-94.

[3] Weng J,Lim E P,Jiang J,et al.TwitterRank:finding topic-sensitive influential twitterers[C]//Proceedings of the Third ACM International Conference on Web Search and Data mining.New York,NY,USA:ACM Press,2010:261-270.

[4] Weng J,Yao Y,Leonardi E,et al.Event detection in Twitter:HPL-2011-98[R].Technical Report of HP Laboratories,2011.

[5] 尹红军.大规模社交网络中局部兴趣社区发现研究[D].合肥:中国科学技术大学,2014.

[6] Kempe D,Kleinberg J,Tardos é.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,DC,USA,2003:137-146.

[7] 熊小兵.微博网络传播行为中的关键问题研究[D].郑州:解放军信息工程大学,2013.

[8] 丁兆云,贾焰,周斌.微博数据挖掘研究综述[J].计算机研究与发展,2014,51(4):691-706.

[9] Noordhuis P,Heijkoop M,Lazovik A.Mining Twitter in the cloud:a case study[C]//Proceedings of the 2010 IEEE 3rd International Conference on Cloud Computing (CLOUD),2010:107-114.

[10] 陆研,毛健骏,屠方楠.网络信息老化规律研究——新浪新闻与新浪微博实证研究[J].高等函授学报(哲学社会科学版),2011,24(12):52-55.

[11]JavaA,KolariP,FininT,etal.Modelingthespreadofinfluenceontheblogosphere[C]//Proceedingsofthe15thInternationalWorldWideWebConference(WWW06),Edinburgh,UK,2006:1-7.

[12]ChaM,HaddaiH,BenevenutoF,etal.MeasuringuserinfluenceinTwitter:themillionfollowerfallacy[C]//ProceedingsoftheFourthInternationalAAAIConferenceonWeblogsandSocialMedia,Washington,DC,USA,2010:10-17.

IMPROVEMENT OF PAGERANK MODEL AND MINING ALGORITHM OF MICROBLOG USER INFLUENCE

Mao Guojun Xie Songyan Hu Dianjun

(SchoolofInformation,CentralUniversityofFinanceandEconomics,Beijing100081,China)

With the development of Web technology, microblog has become one of the most popular social platforms. The calculation of user influence in microblog is the focus of related research. Through the improvement of the PageRank model, a new user influences mining algorithm PR4WB (PageRank for Microblog) is proposed to solve the problem that the traditional PageRank algorithm has too much potential error due to the transfer of page authority value. PR4WB algorithm takes into account the user relationship in microblog while using the concept of social network to link its activity, blog quality and credibility to form a dynamic evaluation model. Experiments based on Twitter data show that, PR4WB algorithm can more accurately and objectively reflect the user’s actual influence.

User influence Social network Microblog Twitter PageRank algorithm

2016-04-02。国家自然科学基金项目(61273293)。毛国君，教授，主研领域：数据挖掘。谢松燕，硕士生。胡殿军，硕士生。

TP391.1

A

10.3969/j.issn.1000-386x.2017.05.005