PageRank算法

一.定义-迭代算法

输入:含有$n$个结点的有向图,转移矩阵$M$,阻尼因子$d$,初始向量$R_0$,计算精度$ϵ$

输出:有向图的PageRank向量$R$

(1)令$t=0$

(2)计算
$$R_{t+1}=dM{R}_t+\frac{1-d}{n}1$$
(3)如果$R_{t+1}$与$R_t$充分接近,令$R=R_{t+1}$,停止迭代。

(4)否则,令$t=t+1,执行步骤(2)$

输入空间

$n$

$M=\left|\begin{array}{ccc}{1}_1& \cdots & 1_n\\ ⋮& ⋮& ⋮\\ n_1& \cdots & n_n\end{array}\right|$

$d$

$R_0=\left|\begin{array}{c}{1}_1\\ ⋮\\ n_1\end{array}\right|$

$ϵ$

import numpy as np
n = 7  #有向图中一共有7个节点
M = np.array([[0, 1/4, 1/3, 0, 0, 1/2, 0],[1/4, 0, 0, 1/5, 0, 0, 0],[0, 1/4, 0, 1/5, 1/4, 0, 0],[0, 0, 1/3, 0, 1/4, 0, 0],[1/4, 0, 0, 1/5, 0, 0, 0],[1/4, 1/4, 0, 1/5, 1/4, 0, 0],[1/4, 1/4, 1/3, 1/5, 1/4, 1/2, 0]])  #根据有向图中各节点的连接情况写出转移矩阵
d = 0.85  #阻尼因子根据经验值确定，这里我们随意给一个值
R0 = np.full((7, 1), 1/7)  #设置初始向量R0，R0是一个7*1的列向量，因为有7个节点，我们把R0的每一个值都设为1/7
eps = 0.000001  #设置计算精度

np.shape(M)

np.shape(R0)

PageRank的迭代算法

$$R_{t+1}=dM{R}_t+\frac{1-d}{n}1$$

t = 0  #用来累计迭代次数
R = R0
judge = False  #用来判断是否继续迭代
while not judge:next_R = d * np.matmul(M, R) + (1 - d) / n * np.ones((7, 1))diff = np.linalg.norm(R - next_R)if diff < eps:judge = TrueR = next_Rt += 1
R = R / np.sum(R)

print('iter：', t)
print('PageRank: \n', R)

二.定义-幂法算法

输入:含有$n$个结点的有向图,有向图的转移矩阵$M$,系数$d$,初始向量$x_0$,计算精度$ϵ$

输出:有向图的PageRank向量$R$

(1)令$t=0,选择初始向量x_0$

(2)计算有向图的一般转移矩阵A
$$A=dM+\frac{1-d}{n}E$$
(3)迭代并规范化结果向量

$$y_{t+1}=A_{xt}$$
$$x_{t+1}=\frac{y_{t+1}}{||y_{t+1}||}$$
(4)$当||x_{t+1}-x_t||<ϵ时,令R=x_t,停止迭代$

(5)否则,令$t=t+1,执行步骤(3)$

(6)对$R$进行规范化处理,使其表示概率分布。

输入空间

$n$

$M=\left|\begin{array}{ccc}{1}_1& \cdots & 1_n\\ ⋮& ⋮& ⋮\\ n_1& \cdots & n_n\end{array}\right|$

$d$

$x_0=\left|\begin{array}{c}{1}_1\\ ⋮\\ n_1\end{array}\right|$

$ϵ$

n = 7  #有向图中一共有7个节点
M = np.array([[0, 1/4, 1/3, 0, 0, 1/2, 0],[1/4, 0, 0, 1/5, 0, 0, 0],[0, 1/4, 0, 1/5, 1/4, 0, 0],[0, 0, 1/3, 0, 1/4, 0, 0],[1/4, 0, 0, 1/5, 0, 0, 0],[1/4, 1/4, 0, 1/5, 1/4, 0, 0],[1/4, 1/4, 1/3, 1/5, 1/4, 1/2, 0]])  #根据有向图中各节点的连接情况写出转移矩阵
d = 0.85  #阻尼因子根据经验值确定，这里我们随意给一个值
x_0 = np.full((7, 1), 1/7) #对x向量进行初始化
eps = 0.000001  #设置计算精度

np.shape(M)

np.shape(x_0)

PageRank的幂法算法

$$A=dM+\frac{1-d}{n}E$$
$$y_{t+1}=A_{xt}$$
$$x_{t+1}=\frac{y_{t+1}}{||y_{t+1}||}$$

t = 0  #用来累计迭代次数
judge = False  #用来判断是否继续迭代
A = d * M + (1 - d) / n * np.eye(n)  #计算A矩阵，其中np.eye(n)用来创建n阶单位阵E
while not judge:next_y = np.matmul(A, x_0)  #计算新的y向量next_x = next_y / np.linalg.norm(next_y)  #对新的y向量规范化得到新的x向量diff = np.linalg.norm(x_0 - next_x)  #计算新的x向量与之前的x向量之间的距离，这里采用的是欧氏距离if diff < eps:  #若两向量之间的距离足够小judge = True  #则停止迭代R = x_0  #得到R向量x_0 = next_x  #更新x向量t += 1  #迭代次数加一
R = R / np.sum(R)  #对R向量进行规范化，保证其总和为1，表示各节点的概率分布

print('iter：', t)
print('PageRank: \n', R)