一种改进的PageRank算法

徐 京，陶 皖 （安徽工程大学计算机与信息学院，安徽 芜湖241000）

21世纪，搜索引擎成为获取信息的重要工具。而随着Web数量的急剧增加，搜索引擎如何以较快的速度给用户提供权威的相关网页。下面，笔者将提出一种改进的PageRank算法，即在传统的PageRank算法［1］中加入MapReduce和Gauss－Seidel，以减少迭代次数，减少时间消耗，提高并行效率。

1 PageRank算法

PageRank算法用于计算网页的权威值，该值是Google对检索的网页进行排序的一个重要依据［2］。PageRank算法由Sergey Brin和Larry Page在1998年4月举行的第7届国际万维大会 （WWW7）上提出［3］。PageRank的基本思想如下：网页A链向网页B是网页A对网页B的认可，视为网页A对网页B投了一票。一个网页得票越多，网页的权威值越大。网页i的权威值Pi按照以上的思想化为公式：

其中，Oj是网页j的链出数目。

互联网链接结构的形成都是自发和无序的，可能存在沉淀现象：一些网页簇只链向簇内的其他一些网页，而不链向簇外的网页；传递进来的PageRank值滞留在网页簇内部，不能传递出去。解决办法是：设定浏览者会随机选择一个链接继续浏览的概率是d，设定浏览者不通过链接，而跳到另一个随机网页的概率是1－d。所得的公式为：

PageRank算法计算时使用幂迭代法，根据上述公式得出迭代公式为：

其中，P为各个网点的PageRank值，是n行1列矩阵；E是一个全为1的n×n方阵；A是链接矩阵，每行和为1，即把每行做求和分解，Aij表示节点i链向节点j。

由于链接结构的自发和无序性，矩阵A存在“黑洞效应”：网络链接图中存在入度为0的网页，经过有限次迭代后，该链接图中的所有网页的PageRank值均为0。……