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

基于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 Pag