基于PageRank算法的网络关键节点查找

杨蓉蓉++王勤颖++刘凤鸣

摘要：本文基于新浪微博平台，以天猫双十一狂欢夜为主题收集数据，根据用户之间的转发关系构建社交网络，然后利用PageRank算法找出网络中的关键节点。

关键词：PageRank；层次分析法；关键节点

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）04-0226-02

1 概述

2016年11月10日晚20：30，2016双十一天猫晚会落户于深圳大运中心体育馆举行，由浙江卫视承办，张靓颖、蔡依林、Rain、TFBPYS等大咖纷纷加入。综艺内容、明星游戏、移动购物三位一体，用全新体验为亿万观众上演了一场边看边剁手的互动娱乐盛宴。

数据显示长达4小时的双11直播晚会，收视率高达23%。根据阿里方面透露，双11晚会硬广收入利润将以红包的形式回馈消费者。此外，阿里巴巴集团旗下大文娱版块，包括合一集团（优酷土豆）、天猫魔盒、虾米音乐、UC浏览器、天猫客户端等平台，都将组成2016双11晚会的联动直播矩阵[1]。

微博用户“天猫双11狂欢夜”是天猫双11全球狂欢夜晚会的官方微博，该博在11月10日晚发布大量微博直播晚会现场，包括晚会明星阵容和节目抽奖等。许多新浪微博用户对官微发布的微博进行转发，同时众多微博大V用户和普通用户展开话题讨论。

本文收集2016年11月10日至11日与“天猫双11狂欢夜”话题相关的微博数据，根据用户之间的转发关系构建社交网络，使用Gephi软件绘制网络结构图，然后使用PageRank算法计算每个节点的PR值，从而找出其中的关键节点。

2 国内外研究现状

PageRank算法最早是由Sergey Brin 和 Larry Page 在《The Anatomy of a Large-Scale Hypertextual Web Search Engine》一文中提出的[2]，它借鉴引文分析的思想，建立在随即冲浪者模型之上，对网页进行评价，为每个网页赋予一个衡量其重要性的PR值，并最后应用于检索结果的排序。

PageRank的基本思想主要来自文献引文分析，一篇学术论文的重要性及质量可以通过其他学术论文对其进行引用的数量来衡量，被引用得越多，重要性越高。PageRank应用传统的文献引文分析思想，提出一个假设，认为网页的重要性和质量可以通过其他网页对其链接的数量来衡量。

PageRank算法通过网页之间的链接来评价网页的重要性，能够在一定程度上避免和减少人为因素对排序结果的影响。该算法采用离线计算方式，与查询无关，因此响应速度较高。PageRank采用均分策略，一个网页的引用越多，被引用网页所获得的PR值就越少[3]。因此，算法可以有效避免为了提高搜索排名而故意使用链接的行为。

PageRank算法在Google搜索引擎获得成功运用，足以证明该算法的高效性和有效性，但是算法也存在一些缺点，会导致主题漂移问题[4]，而且偏重旧网页，旧的页面等级会比新网页要高，但事实上很多新网页的重要性是远高于旧网页的，同时也忽视了用户的个性化问题，所以算法仍有很大的改进余地。

算法的改进可以归纳为两类[5]，一类是基于算法理论的改进，转化为求解矩阵特征向量的问题，比如Power算法、GMRES算法和Power Amoldi算法等；另一类是针对互联网实际应用的特点而进行的改进，比如针对解决主题漂移问题提出的Topic Sensitive PageRank算法，针对时间问题戚春华等人提出了具有时间反馈的PageRank改进算法。

3 PageRank算法

对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：（1）数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。（2）质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。

根据以上两个假设，一个页面的PageRank是由其他页面的PageRank计算得到的，如果给每个页面一个随机的PageRank值（非0），通过迭代计算来不断地更新每个页面节点的PageRank值，直到PageRank值稳定为止，我们就得到所有节点的PageRank值。PageRank的计算公式为：

[PRi=1-dN+dpjPRjLpj]

其中，PRi是网页i的PageRank值，PRj是网页j的PageRank值，pj表示研究的网页，N为页面总数，L（pj）是pj网页链出页面的数量，d为阻尼系数，表示用户随机跳转到一个页面的概率，通常取0.85，能够避免PR值沉淀现象。

4 PageRank算法应用

数据内容包括微博内容、创建时间、微博来源、微博地址、用户昵称、粉丝数、性别、地域、认证类型、是否转发、原微博内容、原微博来源、原微博创建时间和原微博用户昵称共14项。由于我们获取的数据中没有关注、点赞和收藏的数据，所以无法对UserRank算法进行仿真实验，因此，我们选择根据用户之间的转发关系，构建用户社交网络。用户1发布一条微博，用户2转发该微博，那么就有一条由用户2指向用户1的有向边，基于该原则根据每条数据构建节点和有向边，从而形成转发网络。然后，依据该网络结构，以0.85阻尼系数运行PageRank算法，根据每个节点的PR值找出其中的关键节点。

由于双十一狂欢夜晚会时间为10日晚八点半，所以对我们获取的关于“天猫双十一狂欢夜”的所有数据进行数据清理，只留下2016年11月10日和11日的微博数据，然后从中筛选出发布人为普通用户以及微博认证类型为名人认证、媒体认证和企业认证的数据。有些用户尽管发布了一条微博，但是并没有其他用户对该微博进行转发，基于转发关系构建网络时，该用户会成为离群点，所以删除该类数据。对于一个用户发布的不同微博，不同的转发用户对每条微博的转发都考虑在内，如果用户2对用户1发布对两条微博都进行了转发，那么只有一条由用户2指向用户1对有向边。根据上述条件，对数据进行清理之后最后有效数据共计1302条。基于这1302条数据，逐条查找，在Gephi中构建节点和有向边，形成网络如图1所示。其中，蓝色节点为普通用户，红色节点为名人认证用户，黄色节点为企业认证用户，绿色节点为媒体认证用户。

为了直观观察，采用Fruchterman Reingold布局模式改变网络视图如图2所示。在Gephi软件中基于该网络运行PageRank算法，计算每个节点的PR值。

5 结论

在Gephi中构建的网络共有268个节点259条边，每个节点的PR值按照降序排列，前15个节点的PR值如图3所示。取PR值为前5%的用户作为关键用户，共计13名用户。那么在“天猫双十一狂欢夜”话题中，关键用户为天猫双11狂欢夜晚会官微、娱乐潮流情报、抢红包狂欢、天猫、鱿鱼子、KatyPerry、优酷、香港爆料王、Astro12-girls、苏宁易购、老高电商圈子、微博电视和7公主的日常。

圖3 PR值最高的15个节点的PR值

参考文献：

[1] 2016双十一天猫晚会11月10日晚20：30直播 浙江卫视承办

http：//www.tianqi.com/news/160607.html

[2] 黄德才，戚华春.PageRank算法研究[J].计算机工程，2006（2）：145-162.

[3] 吴淑燕，徐涛.PageRank算法的原理简介[J].图书情报工作，2003（2）：55-60.