Pagerank因google的快熟发展并提供高质量搜索结果而受到广泛关注。Pagerank的主要目标是评价网页的重要程度,并以此作为网页的排名依据。算法主要参考网页被引用的数量,及引用者的权威性。参考下面的简单的网页引用模型:
首先我们需要一个合适的数据结构来表示这个网络结构。这涉及到图的表示,我们在数据结构课程中学过,常用的方法是邻接矩阵法和链接法。实际中不会单独的只使用某一种方法,这涉及到图的存储优化,矩阵的稀疏表示等其他技术,在此不做说明。此处我们用邻接矩阵表示。而各节点的值可以使用图节点的出度的倒数表示:
这样矩阵M表示了各图节点到其他节点转移的概率。初始状态下每个节点(网页)自身的值(权重)可以表示为1/N,N为图节点数。A-D初始权重极为v=(1/4,1/4,1/4,1/4).
新的v^1表示各节点的新rank,下一个新rank为v^2=Mv^1. 循环迭代至收敛。
Pagerank在google的搜索排序算法中只是其中的一部分。还有很多其它算法和因素用于考量页面的排序。同时pagerank也有很多改进的版本。
参考:
http://pr.efactory.de/e-pagerank-implementation.shtml
原文《The PageRank Citation Ranking: Bringing Order to the Web》