建设银行网站用360浏览器,建设信用卡中心网站,哈尔滨教育云平台网站建设,网络营销学什么内容一.定义-迭代算法
输入:含有 n n n个结点的有向图,转移矩阵 M M M,阻尼因子 d d d,初始向量 R 0 R_0 R0,计算精度 ϵ \epsilon ϵ 输出:有向图的PageRank向量 R R R (1)令 t 0 t0 t0 (2)计算 R t 1 d M R t 1 − d n 1 R_{t1} dMR_t \frac{ 1 - d }{ n} 1 Rt1dMRt…一.定义-迭代算法
输入:含有 n n n个结点的有向图,转移矩阵 M M M,阻尼因子 d d d,初始向量 R 0 R_0 R0,计算精度 ϵ \epsilon ϵ 输出:有向图的PageRank向量 R R R (1)令 t 0 t0 t0 (2)计算 R t 1 d M R t 1 − d n 1 R_{t1} dMR_t \frac{ 1 - d }{ n} 1 Rt1dMRtn1−d1 (3)如果 R t 1 R_{t1} Rt1与 R t R_t Rt充分接近,令 R R t 1 R R_{t1} RRt1,停止迭代。 (4)否则,令 t t 1 , 执行步骤 ( 2 ) tt1,执行步骤(2) tt1,执行步骤(2)
输入空间 n n n M ∣ 1 1 ⋯ 1 n ⋮ ⋮ ⋮ n 1 ⋯ n n ∣ M \left| \begin{array}{cccc} 1_1 \cdots 1_n \\ \vdots \vdots \vdots\\ n_1 \cdots n_n \end{array} \right| M 11⋮n1⋯⋮⋯1n⋮nn d d d R 0 ∣ 1 1 ⋮ n 1 ∣ R_0 \left| \begin{array}{cccc} 1_1 \\ \vdots \\ n_1 \end{array} \right| R0 11⋮n1 ϵ \epsilon ϵ
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) #设置初始向量R0R0是一个7*1的列向量因为有7个节点我们把R0的每一个值都设为1/7
eps 0.000001 #设置计算精度np.shape(M)np.shape(R0)PageRank的迭代算法 R t 1 d M R t 1 − d n 1 R_{t1} dMR_t \frac{ 1 - d }{ n} 1 Rt1dMRtn1−d1
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 n n个结点的有向图,有向图的转移矩阵 M M M,系数 d d d,初始向量 x 0 x_0 x0,计算精度 ϵ \epsilon ϵ 输出:有向图的PageRank向量 R R R (1)令 t 0 , 选择初始向量 x 0 t0,选择初始向量x_0 t0,选择初始向量x0 (2)计算有向图的一般转移矩阵A A d M 1 − d n E A dM \frac{ 1 - d }{ n} E AdMn1−dE (3)迭代并规范化结果向量 y t 1 A x t y_{t1} A_{xt} yt1Axt x t 1 y t 1 ∣ ∣ y t 1 ∣ ∣ x_{t1} \frac{ y_{t1} }{ ||y_{t1}||} xt1∣∣yt1∣∣yt1 (4) 当 ∣ ∣ x t 1 − x t ∣ ∣ ϵ 时 , 令 R x t , 停止迭代 当||x_{t1}-x_t|| \epsilon时,令R x_t,停止迭代 当∣∣xt1−xt∣∣ϵ时,令Rxt,停止迭代 (5)否则,令 t t 1 , 执行步骤 ( 3 ) t t1,执行步骤(3) tt1,执行步骤(3) (6)对 R R R进行规范化处理,使其表示概率分布。
输入空间 n n n M ∣ 1 1 ⋯ 1 n ⋮ ⋮ ⋮ n 1 ⋯ n n ∣ M \left| \begin{array}{cccc} 1_1 \cdots 1_n \\ \vdots \vdots \vdots\\ n_1 \cdots n_n \end{array} \right| M 11⋮n1⋯⋮⋯1n⋮nn d d d x 0 ∣ 1 1 ⋮ n 1 ∣ x_0 \left| \begin{array}{cccc} 1_1 \\ \vdots \\ n_1 \end{array} \right| x0 11⋮n1 ϵ \epsilon ϵ
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 d M 1 − d n E A dM \frac{ 1 - d }{ n} E AdMn1−dE y t 1 A x t y_{t1} A_{xt} yt1Axt x t 1 y t 1 ∣ ∣ y t 1 ∣ ∣ x_{t1} \frac{ y_{t1} }{ ||y_{t1}||} xt1∣∣yt1∣∣yt1
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)
