Google pagerank算法的python语言实现

本次我们用以下的习题为例

 首先我们需要画出这个图的Google矩阵

代码如下所示：

此处运用了numpy

import numpy as np

p = 0.85  # 社交网络阻尼系数p=0.85

a = np.array([[0, 0, 0, 0, 0, 0],
              [1/3, 0, 0, 0, 0, 1/2],
              [1/3, 1/3, 0, 1/2, 0, 0],
              [1/3, 1/3, 1, 0, 0, 1/2],
              [0, 0, 0, 0, 0, 0],
              [0, 1/3, 0, 1/2, 1, 0]], dtype=float)  # dtype指定为float类型，因为最后算出来的结果可能为小数
length = a.shape[1]  # 网页数量
# 构造转移矩阵
b = np.transpose(a)  # b为a的转置矩阵
m = np.zeros((a.shape), dtype=float)
for i in range(a.shape[0]):
    for j in range(a.shape[1]):
        # 如果一个节点没有任何出链，Dead Ends
        if b[j].sum() == 0:
            b[j] = b[j] + np.array([1 / length] * length)

        m[i][j] = a[i][j] / (b[j].sum())  # 完成初始化分配

# pr值得初始化
v = np.zeros((m.shape[0], 1), dtype=float)  # 构造一个存放pr值得矩阵
for i in range(m.shape[0]):
    v[i] = float(1) / m.shape[0]

count = 0
ee = np.array([[1 / length] * length]).reshape(length, -1)
# 循环100次计算pageRank值
for i in range(100):
    #  解决spider traps问题，spider traps会导致网站权重向一个节点偏移，将转移矩阵加上打开其他网页的概率1-p
    v = p * np.dot(m, v) + (1 - p) * ee
    count += 1
    print("第{}次迭代".format(count))
# pageRank值
print(v)

结果如下：

在经过了100迭代后，从上到下的六位数就是6个页面的重复数