Java教程

Page Rank 算法

本文主要是介绍Page Rank 算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

背景

总的来讲，对于一个特定的查询，搜索结果的排名取决于两组信息，关于网页的质量信息，和这个查询与每个网页的相关信息。PageRank算法就是一种衡量网页质量的方法。
　

核心思想（原理）

在互联网上，如果一个网页被很多其它网页所连接，说明它受到普遍的承认和信赖，那么它的排名就高。
　

算法细节

算法的思想如上文所诉，但实际上要复杂得多。比如说，对于来自不同网页的链接区别对待，因此网页排名高的那些网页的链接更可靠，于是给这些链接以较大的权重。

可以想像，一个新开的质量差的网站与另一个质量好的老网站它们的权重显然是不同的，否则就可以轻易作弊。

那接下来的问题就是这些网站的权重要如何度量呢，可以想到应该是网页本身的网页排名。现在麻烦来了，计算搜索结果的网页排名的过程中需要用到网页本身的排名。

解决方法是，把这个问题变成一个二维矩阵相乘的问题，并且用迭代的方法解决。先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名 。
　

PageRank计算方法

假定如下向量，为第一、第二、...第N个网页的网页排名。

\[B=(b_1,b_2,...b_N)^T \]

如下矩阵为网页之间的链接数目，其中\(a_{mn}\)代表第m个网页指向第n个网页的链接数。

\[A= \begin{bmatrix} a_{11} & \cdots & a_{1n} & \cdots & a_{1M} \\ \cdots \\ a_{m1} & \cdots & a_{mn} & \cdots & a_{mM} \\ \cdots \\ a_{M1} & \cdots & a_{Mn} & \cdots & a_{MM} \\ \end{bmatrix} \]

A是已知的，B是未知的，是我们需要计算的。
假定\(B_i\)是第i次的迭代的结果，那么

\[B_i=A \cdot B_{i-1} \]

初始假设：所有网页的排名都是1/N，即

\[B_0=\left( \frac{1}{N},\frac{1}{N},\cdots,\frac{1}{N} \right) \]

注：关于矩阵计算的优化与技巧和链接数量的平滑，这里并没有给出，可以查阅相关资源。

参考
《数学之美》

这篇关于Page Rank 算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航