【十大经典数据挖掘算法】PageRank

【十大经典数据挖掘算法】系列

我特地把PageRank作为【十大经典数据挖掘算法】系列的收尾篇，是因为本人是Google脑残粉。因了PageRank而Google得以成立，因了Google而这个世界变得好了那么一点点。

1. 引言

PageRank是Sergey Brin与Larry Page于1998年在WWW7会议上提出来的，用来解决链接分析中网页排名的问题。在衡量一个网页的排名，直觉告诉我们：

当一个网页被更多网页所链接时，其排名会越靠前；
排名高的网页应具有更大的表决权，即当一个网页被排名高的网页所链接时，其重要性也应对应提高。

对于这两个直觉，PageRank算法所建立的模型非常简单：一个网页的排名等于所有链接到该网页的网页的加权排名之和：

egin{equation}
PR_i = sum_{(j,i)in E} frac{PR_j}{O_j}
label{eq:pr1}
end{equation}

(PR_i)表示第(i)个网页的PageRank值，用以衡量每一个网页的排名；若排名越高，则其PageRank值越大。网页之间的链接关系可以表示成一个有向图(G=(V,E))，边((j,i))代表了网页(j)链接到了网页(i)；(O_j)为网页(j)的出度，也可看作网页(j)的外链数（ the number of out-links）。

假定(P=(PR_1, PR_2, cdots, PR_n)^T)为n维PageRank值向量，(A)为有向图(G)所对应的转移矩阵，

[A_{ij}=left { { matrix { frac{1}{O_i} & if (i,j) in E cr 0 & otherwise } } ight. ]

(n)个等式eqref{eq:pr1}可改写为矩阵相乘：

egin{equation}
P = A^T P
label{eq:pr2}
end{equation}

但是，为了获得某个网页的排名，而需要知道其他网页的排名，这不就等同于“是先有鸡还是先有蛋”的问题了么？幸运的是，PageRank采用power iteration方法破解了这个问题怪圈。欲知详情，请看下节分解。

2. 求解

为了对上述及以下求解过程有个直观的了解，我们先来看一个例子，网页链接关系图如下图所示：

那么，矩阵(A)即为

所谓power iteration，是指先给定一个(P)的初始值(P^0)，然后通过多轮迭代求解:

[P^k = A^TP^{k-1} ]

最后收敛于(||P^k-P^{k-1}|| < xi)，即差别小于某个阈值。我们发现式子eqref{eq:pr2}为一个特征方程（characteristic equation），并且解(P)是当特征值（eigenvalue）为(1)时的特征向量（eigenvector）。为了满足eqref{eq:pr2}是有解的，则矩阵(A)应满足如下三个性质：

stochastic matrix，则行至少存在一个非零值，即必须存在一个外链接（没有外链接的网页被称为dangling pages）；
不可约（irreducible），即矩阵(A)所对应的有向图(G)必须是强连通的，对于任意两个节点(u,v in V)，存在一个从(u)到(v)的路径；
非周期性（aperiodic），即每个节点存在自回路。

显然，一般情况下矩阵(A)这三个性质均不满足。为了满足性质stochastic matrix，可以把全为0的行替换为(mathrm{e}/n)，其中(e)为单位向量；同时为了满足性质不可约、非周期，需要做平滑处理：

[P=left( (1-d)frac{mathrm{E}}{n} + dA^T ight) ]

其中，(d)为 damping factor，常置为0与1之间的一个常数；(E)为单位阵。那么，式子eqref{eq:pr1}被改写为

[PR_i = (1-d) + dsum_{(j,i)in E} frac{PR_j}{O_j} ]

3. 参考资料

[1] Bing Liu and Philip S. Yu, "The Top Ten Algorithms in Data Mining" Chapter 6.