The-PageRank-Citation-Ranking-Bringing-Order-to-th

PageRank引用排名：使网页更有序January29,1998摘要：一个网页的重要性是一个内在主观的事情，这取决于读者的兴趣，知识和态度。但仍然有许多是可客观地说一下网页的相对重要性。本文介绍了评级的网页客观和机械的PageRank方法，有效地判断人的兴趣和注意力推荐给他们。我们已经发现了一些对PageRank的应用除了搜索，其中包括流量估计和用户导航。另外，我们可以生成个性化PageRank的，可以从一个特定的角度创建Web的视图。总的来说，我们的实验与PageRank的建议的网络图的结构是用于各种信息检索任务非常有用的。1介绍和动机万维网信息检索带来了许多新的挑战。它是非常巨大的和异构。目前的估计，有超过1.5亿的网页在不到一年的时间增加了一倍。更重要的是，web页面非常多样，从“乔有今天的午餐是什么?“对信息检索期刊。除了这些主要的挑战，搜索引擎在网络上也必须面对没有经验的用户和页面设计来操纵搜索引擎排名的功能。然而，与“平”的文档集合，万维网超文本，提供了相当大的辅助信息的文本网页，如链接结构和链接文本。在本文中，我们利用网络的链接结构来产生一个全球“重要性”每个Web页面的排名。这个排名，称为PageRank，帮助搜索引擎和用户快速理解万维网的庞大的异构性的意义。1.1网页的多样性虽然已经有大量学术文献引证分析，有许多web页面和学术出版物之间的显著差异。与学术论文严谨了，网页免费扩散质量控制或出版成本。一个简单的程序，可以轻松地创建大量的页面，人为地抬高引用计数。因为Web环境包含利润寻求竞争企业，关注策略发展针对搜索引擎的算法。出于这个原因，任何评价策略项复制网页的特点是容易操作。此外，学术论文是定义良好的工作单元，大致类似的在质量和数量的引用，以及他们的目的一扩展知识的身体。网页不同规模更大比学术论文质量、使用、引用和长度。问一个不起眼的问题随机存档的消息公布一个IBM计算机非常不同于IBM主页。一篇研究关于手机使用的影响司机的注意力是非常不同的从一个广告为特定细胞提供者。用户经历的平均网页质量高于普通网页的质量。这是因为简单的创建和发布web页面的结果在一个大的一部分低质量网页，用户不喜欢阅读。有许多轴沿网页可能有所区别。在本文中，我们主要是处理——一个网页的整体相对重要性的近似值。1.2网页排名为了测量web页面的相对重要性，我们建议PageRank，方法计算基于web的图形的每个网页排名。PageRank的应用程序涉及搜索、浏览和流量估计。第2节给出的PageRank的数学描述，并提供了一些直观的理由。在第3节，我们将展示我们如何有效地计算PageRank的为多达5.18亿的超链接。为了测试的PageRank的搜索工具，我们建立了一个名为谷歌（第5小节）网络搜索引擎。我们还证明网页排名如何可以被用作一个浏览援助，在第7.3节。2一种排序为每一个页面在Web上2.1相关工作出现了大量的学术引文分析工作【Gar95】。Goffman【Gof71】日前刊登在科学界的信息流是如何的流行过程一个有趣的理论。最近有大量的活动如何利用大型超文本链接结构的系统，如web。Pitkow最近完成了他的博士论文“万维网生态特征”(Pit97，PPR96)与各种各样的基于链接分析。讨论聚类方法，考虑结构的联系[WVS+96]。Spertus[Spe97]讨论链接结构的信息，可以获得各种各样的应用程序。良好的可视化要求添加超文本结构，讨论了[MFH95，MF95]。最近，KleinbergK1e98)开发了一个有趣的模型网络的中心和有关部门（HubsandAuthorities），根据co-citation矩阵的特征向量计算网络。最后，有兴趣在网上从图书馆社区了解“质量”意味着什么【Til】。很明显试图标准的引文分析技术应用于网络的超文本引用结构。一个可以简单地认为每一个环节是像一个学术引用。所以，等主要页面将有成千上万的反向链接(或引用)指向它。这一事实，雅虎的主页有很多反向链接通常意味着它是相当重要的。事实上许多web搜索引擎使用的反向链接数作为一种倾向他们数据库支持高质量或更重要的页面。然而，简单的反向链接数量在网络上有很多问题。其中的一些问题与网络的特征有关，不存在于正常的学术文献数据库。2.2网络链接结构虽然估计各不相同，当前的图crawlableWeb边缘有大约1.5亿节点(页)和17亿边缘(链接)。每一页有一些数量的链接(outedges)和反向链接(inedges)(参见图1)。我们可以永远不知道我们是否有发现某个特定页面的所有反向链接，但如果我们已经下载了它，我们知道所有的链接。Web页面的反向链接的数量差异很大。例如，Netscape主页有62804个反向链接在我们当前的数据库相比，大多数页面有几个反向链接。一般来说，高度相关页面更“重要”页面链接。简单的引用计数被用来推测未来的赢家诺贝尔奖（San95〕。网页级别提供了一种更复杂的方法进行引用计数。网页排名的原因是有趣的是，在许多情况下，简单的引用计数并不符合我们的常识的概念的重要性。例如，如果一个网页链接雅虎主页，它可能只是一个链接但它是非常重要的。这个页面应该排名高于许多页面有联系，从不起眼的地方。网页排名是为了看看好一个近似“重要性”可以从链接结构。2.3传播的排名通过链接基于上面的讨论，我们给出下面的PageRank的直观的描述:一个页面排名很高，如果反向链接的排名很高的总和。这包括两种情况下，当一个页面有很多的反向链接，当一个页面有几个高排名的反向链接。2.4定义PageRank设u是一个网页。然后Fu是集合页的出度点，Bu是集合指向到u的网页。让Nu=|Nu|是从一个链接的数量和设C是一个影响因子，使所有网页的总排名是恒定的，我们首先定义一个简单的排名，R稍微简化版本的网页排名:这种形式化的一节中的直觉。需要注意的是一个页面的等级划分，其正向链路之间均匀地促进它们所指向的网页的行列。需要注意的是ç1，因为有一些没有正向链接和自己的体重从系统中丢失的页面（见2.7节）。该方程是递归的，但它可以通过启动与任何组行列和迭代计算直到其收敛计算。图2展示的秩从1双页面到另一个的繁殖。图3显示了一组页面一致的稳态解。换句话说，设A是一个方阵的行和列对应的网页。让AV，V=1/NV如果有从一个边缘：和AVW=0，如果没有。如果我们把r作为一个向量在网页，则有R=车。因此，R是A有着特征值c的特征向量。事实上，我们希望A的主要特征向量这可能是由重复应用A到任何非简并开始向量来计算。有一个小问题简化的排序功能。考虑两个网页，但没有其他页面。和假设有一些网页指向其中的一个。然后在迭代此循环将积累等级但是从来没有发布任何等级(因为没有outedges)。循环形式的陷阱，我们称为下称等级为了解决下沉等级的这个问题，我们引入一个来源:定义1让E(u)一些向量对应的网页排名的一个来源。一组网页是一个赋值，R'，到Web页中满足其中E（u）为载体的一些较对应的秩的源网页（见第6节）。请注意，如果E是所有正，C必须降低以平衡方程。因此，该技术相当于一个衰减因子。在矩阵表示法我们有R'=C（AR'+E）由于|，|R'||1=1，我们可以重写此为R'=C（A+E×1）R'，其中1是由所有的人矢量。因此，R'是（A+E×1）的特征向量。2.5随机冲浪模型上面的PageRank的定义在图上随机游动的另一个直观的依据。简化版本对应的随机游走于网络的图形上的站立概率分布。直观地说，这可以看作一个建模“随机冲浪者”。“随机冲浪”只是不断点击链接历届随机的行为。但是，如果一个真正的网络冲浪者不断进入的网页的一个小环，它是不可能的冲浪者将继续在无限循环。相反，冲浪者会跳转到其他页面。附加系数E可以被看作是模拟这种行为的方法：冲浪周期性“厌倦”，并通过E跳转到分布规律的随机任何页面。到目前为止，我们已经离开e作为一个用户定义的参数。在大多数的测试中，我们让E是均匀的所有网页与价值。然而，在第6节我们将展示E项的不同的值如何产生“定制化”的网页排名。2.6PageRank的计算PageRank的计算是相当简单的，如果我们忽略规模的问题。令S'是在网页上几乎任何载体（例如E）的PageRank然后可以计算如下：注意，对d因子增加收敛速度并维持||IR||1.An替代正常化是通过适当的因子乘以R上。在使用D可能对E的影响小的冲击2.7悬浮链接其中一个问题与此模型悬浮的的链接。悬浮链接只是链接指向任何网页，没有外向链接。它们会影响模型，因为它是不明确，他们的体重应该是分布式的，而且有大量的人。通常，这些晃来晃去的链接只是，我们尚未下载，因为很难获取整个web（在我们目前下载的2400万页，我们尚未下载，因此有着51000000URL）的页面。因为悬空链接不直接影响其他页面的排名，我们只是把它们从系统中删除，直到所有PageRanks计算。计算所有PageRanks之后，他们可以添加进来吧，不影响显著。注意到同一页面上的其他链接正常化就被移除的链接将略有变化，但这应该不会有很大的效果。3实现作为斯坦福的一部分WebBase项目(PB98)，我们已经构建了一个完整的爬行和索引系统当前库的2400万个网页。任何一个网络爬虫需要保持databaseofurl，这样就可以在网上发现所有的url。实现网页排名，网络爬虫只是需要建立索引的链接爬行。一个简单的任务，它是简单的，因为它涉及到大量。例如，我们当前的2400万页的索引数据库在天，我们需要处理每秒大约50个网页。因为平均大约有11个链接页面(取决于你算是一个链接)我们需要处理550每秒的链接。2400万页的同时，我们的数据库引用超过7500万独特的url必须比较每个链接。花费的时间使系统弹性面对许多深刻和复杂的web工件缺陷。存在无限大网站，页面，甚至url。大部分网页都不正确的HTML，使解析器设计困难。混乱的启发式方法是用来帮助爬行过程。例如，我们不与他们}目录/爬行url。当然，这是不可能得到的“整个网络”的正确的样品，因为它总是在不断变化。网站有时会下降，而有些人决定不让他们的网站被索引。尽管如此，我们认为我们有一个实际的合理表示公开的网络链接结构。2400万页面参照的同时，我们的数据库引用超过7500万独特的url必须比较每个链接。3.1实现PageRank我们把每个URL转换成一个独特的整数，并将每一个超链接存储在一个数据库使用整数id来识别页面。我们的实现的细节(PB98〕。一般来说，我们以以下的方式实现了网页排名。首先我们父ID排序链接结构。然后晃来晃去的链接从链接数据库中删除以上讨论的原因(几个迭代消除绝大多数晃来晃去的链接)。我们需要做一个初始赋值。这个任务可以通过策略之一。如果它将迭代直至收敛，一般初始值不会影响最终值，收敛速度。但我们可以加速收敛，选择一个好的初始赋值。我们相信，小心选择初始赋值和一个小的有限数量的迭代可能导致优秀的或改进的性能。内存分配给每个页面的权重。因为我们使用单精度浮点值4个字节，这相当于300字节为我们7500万年的url。如果没有足够的可用内存来保存所有的重量、多个通行证可以让(我们的实现使用一半的内存和两个传球)。从当前时间步的权重会保存在内存中，和前面的权重线性访问磁盘。同时，所有的访问数据库的链接，一个是线性的，因为它是排序。因此，也可以保存在磁盘上。尽管这些数据结构都是非常大的，每次迭代线性磁盘访问允许在大约6分钟完成一个典型的工作站。权重融合之后，我们添加悬空链接回到和重新计算排名。注意添加悬空链接回来之后，我们需要迭代多次被要求删除晃来晃去的链接。否则，一些悬空的链接将零重量。整个过程大约需要烟道小时在当前实现中。用更少的严格的收敛标准，更优化，计算可能会快得多。或者，更高效的技术来评估特征向量可以用于提高性能。然而，值得注意的是，计算网页级别所需的成本相比是微不足道的成本需要构建一个全文索引。4收敛性如可以从曲线图在图4中的PageR