Google网站排名PageRank算法原理及numpy代码实现

1，PageRank

1.1。简介

PageRank，又称网页排名、谷歌左排名，是搜索引擎对网页之间的超级排名。链接计算技术作为网站排名的要素之一，是以谷歌创始人拉里·佩奇的姓氏命名的。谷歌用它来反映网页的相关性和重要性。它是搜索引擎优化操作中经常用来评估网站优化效果的因素之一。考虑 4 个网页：A、B、C 和 D。如果所有网页都只链接到 A，则 A 的 PR 值（PageRank）将是 B、C 和 D 的 PageRank 之和。

假设 B 链接到 A 和 C，C 仅链接到 A，D 链接到所有其他 3 个页面。每页总共只有一票。所以 B 给 A 和 C 双方各半票。使用相同的逻辑，D 投出的选票中只有三分之一计入 A 的 PageRank。

1.2。公式

对于 A 页面，PR 值为：

• PR(A) 为页面 A 的 PR 值
• PR(Ti) 为页面 Ti 的 PR 值。这里边Ti是指向A
• 的所有边中的一条边（Ti）是边Ti的出度，即从Ti指向其他边的边的条数
• d是阻尼系数，表示用户在任意时刻到达某个页面并继续向后滚动的概率，

该值是根据互联网用户使用浏览器书签的平均频率估算出来的，通常是一个版本d=0.85 的公式：

N 为总页数

1.3。具体示例

三个页面 A、B、C 为简单起见，我们假设每个页面的初始 PR 值为 1，d 为 0.5。 A 页面的

• PR 值计算如下：

• B 页面的 PR 值计算如下：

页面的值计算如下： :

下面是经过12轮迭代计算后，每个页面的PR值为：

那么迭代什么时候结束呢？一般来说，必须设定收敛条件：例如，如果上一次迭代的结果和本次迭代的结果小于一定的误差，则终止程序；例如，还可以指定最大循环次数。

2。代码实现

import numpy as np
from scipy.sparse import csc_matrix

def pageRank(G, s=.85, maxerr=.0001):
"""
Computes the pagerank for each of the n states
Parameters
----------
G: matrix representing state transitions
Gij is a binary value representing a transition from state i to j.
s: probability of following a transition. 1-s probability of teleporting
to another state.
maxerr: if the sum of pageranks between iterations is bellow this we will
    have converged.
"""
n = G.shape[0]
# 将 G into 马尔科夫 A
A = csc_matrix(G, dtype=np.float)
rsums = np.array(A.sum(1))[:, 0]
ri, ci = A.nonzero()
A.data /= rsums[ri]
sink = rsums == 0
# 计算PR值，直到满足收敛条件
ro, r = np.zeros(n), np.ones(n)
while np.sum(np.abs(r - ro)) > maxerr:
ro = r.copy()
for i in range(0, n):
   Ai = np.array(A[:, i].todense())[:, 0]
    Di = sink / float(n)
    Ei = np.ones(n) / float(n)
   r[i] = ro.dot(Ai * s + Di * s + Ei * (1 - s))
 # 归一化
 return r / float(sum(r))
 if __name__ == '__main__':
 # 上面的例子
 G = np.array([[0, 0, 1],
          [1, 0, 0],
          [1, 1, 0]])
 print(pageRank(G, s=0.85))
 # 结果：
 [0.51203622 0.19313191 0.29483187]