基于PageRank的微博排名MapReduce算法研究_舒琰

收稿日期：2012－05－24；修回日期：2012－08－27

基金项目：国家自然科学基金资助项目（70771077）；国家“863”高技

术发展计划项目（2008AA04Z106）；上海市科技创新计划（11DZ15

01703，（陈家镇）11DZ1210600）；上海市信息化发展专项资金项目

（200901015）；上海市科委项目（08DZ1122300）

作者简介：舒

琰（1987－），男，硕士研究生，研究方向为数据挖掘、数据仓库；向

阳，教授，博士生导师，从事智能决策支持系统、人工智能等研究；张琪，董事长，硕士，从事信息管理科学研究。基于PageRank 的微博排名MapReduce

算法研究

舒琰1，向阳1，张骐2，张熊熊3，张君瑛4，

（1．同济大学电子与信息工程学院，上海201804；

2．神华和利时信息技术有限公司，北京100011；

3．上海证券交易所，上海200120；

4．上海市陈家镇建设发展有限公司，上海202162）

摘要：随着社交网络的发展，对于其数据的挖掘与分析已经成为一个热门领域。在微博中，用户排名通常是单纯根据粉

丝人数进行排列，

而这种方法并不公正。针对这一问题，结合网页PageRank 算法，提出了新的排名算法，以用户为节点，用户关系为有向边，

建立概率转移矩阵，计算微博用户PageRank 值。该算法能有效减少垃圾用户对微博排名的影响，来提高排名的公平性与准确性。实验测试在云环境下进行，结果显示了新的排名结果，与现有的微博粉丝排名相比，更加公平，具有一定的实用价值。

关键词：微博；PageRank ；MapReduce

中图分类号：TP301．6文献标识码：A 文章编号1673－629X （2013）02－0073－04

doi ：10．3969/j．jssn．1673－2013．02．020

Research on MapReduce Algorithm of Micro Blog Ranking

Based on PageRank

SHU Yan 1，XIANG Yang 1，ZHANG Qi 2，ZHANG Xiong －xiong 3，ZHANG Jun －ying 4

（1．College of Electronics and Information Engineering ，Tongji University ，Shanghai 201804，China ；

2．Beijing HollySys Co．Ltd．，Beijing 100011，China ；

3．Shanghai Stock Exchange ，Shanghai 200120，China ；

4．Shanghai ChenJiaZhen Construction Development Co．，Ltd．，Shanghai 202162，China ）

Abstract ：With the development of social network service ，mining and analyzing data from SNS is becoming an active area of science．In

micro blog ，

the user ranking is based on the number of fans ，but it is not very fair．In this paper ，propose a new ranking algorithm based on web PageRank ，in which use the data from Sina Weibo to yield a graph with nodes and edges．Then build a transition probability ma-trix to compute every user ’s PageRank．This algorithm can make the user ranking more fair and more closely to reflect the reality．The experiments are conducted in cloud ，which present a new ranking result and the algorithm has some practical value ，comparing with the follower ranking．

Key words ：Micro blog ；PageRank ；MapReduce

0引言社交网络（SNS ，

Social Network Service ）即社交网络服务，是在网络联系越来越紧密的演进中出现的。

它为人们在网络上建立一种新的沟通模式，或者说是

平台，在此基础上，与其他人分享信息，应用互动［1］。传统社交网络从虚拟聊天室、论坛，发展到如今的博客、微博，经历了一系列的演进。传统的社交网络像是一个公共场所，以内容、话题为基础，可以迅速聚集人气，但是黏性较低，而且作为一个社区，传统社交网络以匿名为主，用户之间的关系比较模糊，而现在进入Web 2．0时代的社交网络以人际关系为基础，多对多的关系形成一条条人际链，例如Facebook 、Twitter 等第23卷第2期2013年2月计算机技术与发展COMPUTER TECHNOLOGY AND DEVELOPMENT Vol．23No．2Feb．2013

平台已经不单单是服务提供商划出社交圈，而是由用户以自己为中心，自发地通过关系链组成社交维度空间。特别是类似Facebook、人人网、同学网这种更注重真实信息的社交网络，以认证系统为手段，致力于打造虚拟空间中的社会网络体系［1］。

以新浪微博为例，新浪微博是新浪网推出的一个提供微型博客服务的类Twitter网站，从2009年8月14日开始内测，据新浪2012年第一季度财报显示，新浪微博注册用户为3．24亿，日活跃用户约3000万。随着社交网络用户的越来越多，在社交网络中的信息传播也越来越快。社交网络媒介已经慢慢成为了一种不容忽视的大众传播媒介，这种传播方式主要还是建立在人际传播的基础上，好友之间的关系已经从原本传统社交网络中的虚拟关系渐渐转变成更为真实，更为可信的通道［2］。

传统的微博用户排行中，一般只是单纯的进行粉丝数量的比较，而没有考虑到关注这些用户的粉丝质量，同样的粉丝数量，但是粉丝的质量不同，其表现出来的用户质量也不同，跟互联网中的网页相似，文中基于网页PageRank算法，为微博创建了新的用户排列体系，在一定程度上避免由很多低质量粉丝关注的用户也能成为热门用户的情况。

1相关工作

1998年，当时还在斯坦福大学上学的拉里·佩奇和谢尔盖·布林发明了PageRank算法［3］，是一种根据网页之间相互的超链接计算，来确定页面等级的技术，是Google搜索引擎的基本算法之一［4］。Google把从A页面到B页面的链接解释为A页面给B页面投票，Google根据投票来源（甚至来源的来源，即链接到A 页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。

其算法公式如下：

PR（A）=（1－d）+d?∑n

i=1PR（T

i

）

C（T

i

）

PR（A）表示A页面的PageRank值，PR（T

i

）表示

T i 页面的PageRank值，并且T

i

链接到A页面，C（T

i

）

表示T

i

页面向外链接总数，d表示跳转到其他页面的概率，介于0 1之间，n为互联网上网页总数。

从此PageRank最基本公式中可以看出，提高Pag-eRank值的方法主要有三点：

（1）反向链接数：反向链接数越多，该页面的Pag-eRank值自然越大；

（2）反向链接数是否来自于PageRank值高的页面：链接源页面本身的PageRank值越高，就越容易提高链接的页面的PageRank值；

（3）反向链接源页面的链接数：链接源页面的链接数越少，则说明链接的页面被选中的几率越高，计算得出的PageRank值也越大［5］。

在微博中，用户关注另外的用户，说明该用户对被关注的用户有较高的兴趣，与网页PageRank算法相似［5］，微博PageRank算法也是通过其他用户对某用户的关注来衡量这些用户与被关注用户的关系度。在网页PageRank算法中，互联网中的网页被视作一个个顶点，而它们相互之间的链接被视作一条条有向边，在微博PageRank算法中，用户作为顶点，相互之间的关注关系作为有向边。而影响微博PageRank值的主要是关注该用户的粉丝数量，关注该用户的用户本身的PageRank值以及关注该用户的粉丝总数。需要遍历各个用户的关注者与粉丝，通过计算微博用户的Pag-eRank值来判断用户之间的关系度［6］。

2微博PageRank计算模型

此模型主要分两步，数据获取以及数据处理。首先需要通过微博提供的API采集用户数据，形成计算所需要的计算矩阵，然后应用模拟PageRank算法计算微博PageRank值［7］。图1为流程图

。

图1流程图

2．1微博数据获取

微博开放平台为开发者提供了丰富的微博API［8］，数据获取阶段主要就是调用这些API。在调用微博API之前先要初始化两个用来存放用户ID的队列P和Q，队列P用来存放需要遍历的用户ID，队列Q用来存放已经遍历过的用户ID，当队列P为空时，就进入到数据处理阶段，非空时，就循环对队列P中用户ID进行遍历获取用户数据。

在此阶段中，主要需要用到有关用户关注、粉丝的API。当队列P非空时，队头用户ID出列，通过friend-

·

47

·计算机技术与发展第23卷

ships /friends ，friendships /followers 获取用户的关注列表和粉丝列表中用户ID ，通过比较队列Q ，若有不在队列Q 中的用户ID ，

则将其插入到队列P 中，将用户与关注用户和粉丝的关系存储到关系表S （用户1，用户2，关系）中，1表示用户1关注用户2，0表示用户2关注用户1。2．2

微博数据处理

在进行微博PageRank 值之前，首先要初始化一个矩阵A ，将关系表S 中的信息添加到矩阵中，a ij 表示i 与j 的关系，

1表示i 关注j ，0则表示不关注。根据微博的数据，需要对PageRank 算法重新定义。

u 表示微博用户，I u 表示跟随用户u 的粉丝集合，O u 表示用户u 跟随的用户集合，则微博PageRank 值可以表示为：

R （u ）=

∑

v ∈I u

R （v ）

O v

从这个公式中，可以得到，一个用户u 的PageRank

值等于该用户所有粉丝的PageRank 值除以各自跟随者数量的结果之和。如图2所示。

图2

PageRank 计算

图2中用户2的O 2为2，R （2）为40，用户3的O 3为3，R （3）为30，如果只有用户2和用户3跟随

用户1，则用户1的R （1）就为40/2+30/3=30。虽然用户的PageRank 值还是可以由大量的粉丝的关注而提高，但是由不同质量的粉丝所带来的影响也是不同的。

设PageRank 矩阵A ，A 的成分a ij 可以表示为a ij =

1if 用户i 跟随j 0

if

用户i 没有跟随j

{

如果用户总数为N ，则这个矩阵就是一个N ?N 的方阵。但是重视的是用户被哪些用户所关注，而不是着重用户关注哪些用户，并且存在某些悬垂用户，悬垂用户（dangling user ）指的是那些可能有很多人关注，但是本身却不是任何人的粉丝的用户。由于计算每个用户的PageRank 值是通过求一个概率转移矩阵的唯一静态概率分布，这就需要该矩阵不可约且为非周期的，另一个前提条件就是每个用户至少有一个跟随对象，不能出现某一行全为0的情况。

而悬垂用户的表现恰恰就是其所在行全为0值，主要有两种方法来解决这个问题：

a ）将这些悬垂用户从计算系统中移除，因为这些用户没有跟随对象，所以并不会影响整体PageRank 的计算，

只需要在PageRank 值计算出来以后，再将这些用户重新纳入进来即可，事实证明，那些被移除关系的用户的转移概率只会受到轻微的影响。

b ）对这些悬垂用户的跟随对象稍作处理，就是为他们增加一个跟随所有其他用户的跟随关系，也即用跟随任何其他用户的概率1/N （N 表示所有用户）替换原本的0值。

采取方法a ），将这些悬垂用户从A 中暂时移除。为了保证随机转移矩阵的不可约和非周期性，采用类似上述b ）的方法，为每一个用户增加跟随所有其他用户的关系的方法，并由一个随机因子α控制［9］

，得到一

个改进的PageRank 模型

［9］

：

R （u ）=α∑

v ∈I u

R （v ）

O v

+1－α记A =A T

，A 为随机转移矩阵，每个列向量之和为

1，各个行向量表示了各个用户之间的跟随概率。静态概率分布意味着，用户PageRank 的计算就是求A 特征值为1的主特征向量，其计算模型为：

P =（（1－α）

E

N

+αA ）P 其中P 为所求的静态概率分布，也即每个页面的PageRank 值，E 是ee T （e 是全为1的列向量），即E 为

一个全为1的N ?N 方阵，

跟随任何一个用户的概率是1/N 。

缩放等式得

P =（1－α）e +αAP

而这可以采用幂迭代方法计算，如下：

P 0←S k ←1loop ：

P k ←（1－α）e +αA k －1k ←k +1while ：

||P k －P k －1||＜εreturn ：

P k

其中S 为初始设定的PageRank 值，默认为每个页面的PageRank 为1/N ，ε为可以接受的准确程度。最后将悬垂用户纳入到最后的结果中［10］

。

本实验的计算运行在Hadoop 云计算集群中［10］

，

其Mapper 函数的伪码：

input ＜UserN ，FollowN＞－＞UserA ，UserB ，UserC ．．．//链

·

57·第2期舒琰等：基于PageRank 的微博排名MapReduce 算法研究

接关系

begin

Nn：=the number of outfollows for UserN；

for each outfollow UserK

output UserK－＞＜UserN，RankN/Nn＞

//同时输出链接关系，用于迭代

output UserN－＞UserA，UserB，UserC…

end

Mapper的输出如下（已经排序，所以UserK的数据排在一起，最后一列则是跟随关系对）：

UserK－＞＜UserN1，RankN1/Nn1＞

UserK－＞＜UserN2，RankN2/Nn2＞

…

UserK－＞＜UserAk，UserBk，UserCk＞

Reduce函数的伪码：

input mapper＇s output//如上面的说明

begin

RankK：=0；

for each infollow UserNi

乘幂法迭代的过程

output＜UserK，RankK＞－＞＜UserAk，UserBk，User-Ck．．．＞

end

3实验分析

文中测试环境如表1所示：

表1实验环境

四台计算机组成计算集群

CPU Pentium（R）Dual－Core E52002．50GHz

内存DDR32G

硬盘500G

文中所用的微博数据爬虫的抓取速度大概是12000条/分钟（四个账户），其起始账户为起点，通过好友关系来抓取，抓取信息包括用户ID，昵称，所在地，注册时间，性别，关注用户数，粉丝数，微博总数等。

最终数据为10005943个用户，费时18天（为防止账户被封，所以抓取一段时间后会停止一段时间）。

由于需要用户之间的关系，同时在数据库另外一张表中为每个用户列出其粉丝列表，建立PageRank矩阵A，同时需要设定一个初始PageRank向量来定义每个用户的PageRank，为方便计算，每个值定义为1/N，N为数据用户总数，即为10005943。因为实验数据量较大，文中的PageRank值的计算是在由四台服务器组成的Hadoop云平台中计算，用MapReduce方式进行，每台服务器两个Map，总共8个Map［11］。实验结果如表2所示，左为新浪官方排名，右为本算法得到的排名。

由于微博爬虫只是抓取一部分微博用户信息，相对整个微博用户群体来说，比例较小，但是从中也可以分析出一部分信息。文中采用PageRank算法在计算PageR-ank值时，计算集群总共8个Map迭代一次的时间大概是320秒，迭代42次得到最后的结果，总耗时225分钟左右。在本算法中，虽然初始PageRank相等，但是微博用户对娱乐明星的关注程度大大超过其他领域的用户，在最后结果中呈现出来的情况就是依旧以娱乐明星为主。而在Top10的排名中，已经有了排名的变化，说明他们的粉丝用户数量可能有差距，但是最后的PageRank值由于粉丝的质量而得到较高的分值。

表2实验结果

排名新浪微博排名本算法排名

1姚晨姚晨

2小S头条新闻

3杨幂蔡康永

4谢娜王力宏

5王力宏陈坤

6赵薇方大同

7蔡康永NBA

8何炅方文山

9李冰冰电影工厂

10陈坤李冰冰

4结束语

文中针对微博单纯通过对比粉丝人数的排名，提出了一种新的根据粉丝重要性的排名算法。首先通过抓取大量的用户数据，建立PageRank矩阵，结合传统网页PageRank的计算方法来计算微博用户的PageR-ank值，通过云计算集群，MapReduce计算方式来加速计算PageRank值，得到的结果比现有的排名更具公平性。而实验结果也说明根据PageRank值的比较，微博排名会发生变化。然而，由于单纯计算PageRank 值［12］，并无法区分微博用户在各自领域的排名，也就是无法体现出用户的主题相关性，并且只是单纯地考虑了用户之间的关注布尔型，而没有将用户关系进行量化，这些都是以后研究的主要工作内容。

参考文献：

［1］余剑来．社交网络化的发展方向［J］．世界科学，2011（1）：59－60．

［2］毛国君，王实．数据挖掘原理与算法［M］．第2版．北京：清华大学出版社，2007．

［3］焦金涛．基于PageRank的Web挖掘改进算法［J］．计算机工程，2009（15）：284－286．

［4］Page L，Brin S，Motwani R，et al．The PageRank citation rank－

（下转第81页）

·

67

·计算机技术与发展第23卷

＜constant name="struts．objectFactory．spring．autoWire"value ="name"/＞

＜constant name="struts．enable．SlashesInActionNames"value ="true"/＞

＜constant name="struts．serve．static．browserCache"value=" false"/＞

＜constant name="struts．configuration．files"value="struts－student．xml，struts－teachet．xml"/＞

＜constant name="struts．mapper．class"value="org．apache．struts2．dispatcher．mapper．DefaultActionMapper"/＞

＜constant name="struts．freemarker．manager．classname"val-ue="org．apache．struts2．views．freemarker．FreemarkerManager"/＞

4结束语

Struts2是强大的Java Web开源框架，是基于PO-JO的Action的MVC Web框架。Struts2的优点主要体现在［12］：基于MVC架构，框架结构清晰，开发流程一目了然，开发人员可以很好地掌控开发的过程；使用OGNL进行参数传递，可以方便地获取Request、Attrib-ute、Application、Session、Parameters中的数据；强大的拦截器，Struts2的拦截器是一个Action级别的AOP，许多特性都是通过拦截器来实现；易于测试，Struts2的Action都是简单的POJO，可以方便地编写测试用例；易于扩展的插件机制，只需要将所需要的Jar包放到WEB－INF/lib文件夹中，在struts．xml中作一些简单的设置就可以实现扩展；模块化，可以通过将配置信息拆分成多个文件、把自包含的应用模块创建为插件、将与特定应用无关的新功能组织成插件等方法来将应用程序模块化；全局结果与声明式异常，为应用程序添加全局的Result，和在配置文件中对异常进行处理。所有这些优点的体现，依赖于强大的配置文件。

文中的研究内容，降低了对软件开发人员的技术要求，提高了软件开发劳动生产率，改变了传统的软件开发模式［13］。是Struts2的核心技术，有利于团队成员并行工作，对从事Struts2框架的开发人员具有很高的参考价值。

参考文献：

［1］宋士安，邹俊伟，刘丽华．基于Struts+Spring+Hibernate缺陷管理系统实现［J］．计算机技术与发展，2012，22（2）：146

－148．

［2］李纲．Struts2权威指南［M］．北京：电子工业出版社，2008．

［3］Liu Y J，Kang J C，Lu W F．Overview of Model－driven Ar-chitecture［J］．Computer Science，2006，33（3）：226－228．［4］吕凯．基于MVC设计模式的Struts框架的应用研究［J］．沈阳工程学院学报（自然科学版），2010，6（4）：366－

368．

［5］Brown D，Davis C M．Struts2in Action［M］．America：Man-ning Publications Co，2008．

［6］郑若颖．一种对Struts配置文件加载过程的改进方法［J］．大众科技，2007，9（9）：89－90．

［7］白广元．Java Web整合开发完全自学手册［M］．北京：机械工业出版社，2009．

［8］张毅．基于Struts框架的J2EE WEB应用研究与实现［D］．成都：西南交通大学，2006．

［9］Roughley I．Practical Apache Struts2Web2．0Projects［M］．［s．l．］：Springer，2007．

［10］欧阳宏基，马广平，葛萌．基于Struts框架的Web应用研究与实现［J］．计算机与数字工程，2010，38（3）：197－200．［11］迟却懂．struts．properties配置文件［EB/OL］．2011－06－08．http：//czqjay4818．blog．163．com/blog/static/618408820093

943021934/．

［12］阿锋．struts2优点［EB/OL］．2011－06－08．http：//czq-jay4818．blog．163．com/blog/static/618408820093943021

934/．

［13］Ren Y C．Research and Application on Automatic Generation Technology of JavaScript Input Validation［J］．Advances in In-

telligent and Soft Computing，2012，148（1）：595－600．

檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪

（上接第76页）

ing：Bringing order to the web［M］．Palo Alto，California：Stan-

ford University Press，1998．

［5］李稚楹，杨武，谢治军．PageRank算法研究综述［J］．计算机科学，2011（S1）：185－188．

［6］李凯，赫枫龄，左万利．PageRank－Pro－一种改进的网页排序算法［J］．吉林大学学报（理学版），2003（2）：175－

179．

［7］Brin S，Page L．The anatomy of a large scale hypertextual web search engine［C］//Proceedings of the Seventh International

World Wide Web Conference．Brisbane：ACM Press，1998：

107－117．

［8］Ling Zhang，Zheng Qin．The Improved Pagerank in Web Cr－

awler［C］//The1st International Conference on Information

Science and Engineering ICISE．Piscataway，N．J．：IEEE

Press，2009：1889－1891．

［9］邵晶晶，李波，刘汉平．PageRank的改进算法－调整阻尼因子［J］．应用数学，2008（S1）：57－61．

［10］高宝军．Web结构挖掘中PageRank算法优化研究［D］．兰州：兰州大学，2011．

［11］李远方，邓世昆，闻玉彪，等．Hadoop－MapReduce下的Pag-eRank矩阵分块算法［J］．计算机技术与发展，2011，21

（8）：6－9．

［12］Fu H H，Dennis K J L，Tsai H T．Damping factor in Googlepage ranking［J］．Applied Stochastic Models Business

and Industry，2006，22（5－6）：431－444．

·

18

·

第2期刘艳春等：Struts2框架核心配置文件的研究与应用

本文来源：https://www.bwwdw.com/article/71qq.html