PageRank python 实施、算法

Question

我正在尝试在 Python 中写这个 matlab implementation，但我有一段时间没看懂：

last_v = ones(N, 1) * inf;

我们在这里得到一个包含所有无穷大的向量吗？在这种情况下，while 中的条件立即为假，我们没有获得任何迭代：

while(norm(v - last_v, 2) > v_quadratic_error)

我理解错了什么？

这是方法，我试过了：

from numpy import *

def pagerank(M,d,v_quadratic_error):
    count = 0
    N=M.shape[1]
    v=random.rand(N,1)
    v=v/linalg.norm(v)
    ainf=array([[inf]])
    last_v = dot(ones((N,1)),ainf)
    R = d*M + ((1-d)/N * ones((N,N)))

    while linalg.norm(v-last_v,2) > v_quadratic_error:
        last_v = v
        v = dot(R,v)
        count+=1
        print 'iteration #', count
    return v

Answer 1

是的，你是对的，这条线将产生一个无穷大向量。也可以直接使用 inf：https://de.mathworks.com/help/matlab/ref/inf.html -> inf(N,1).

条件虽然不会产生假，但为什么会产生假呢？请看一下欧几里得范数：https://en.wikipedia.org/wiki/Euclidean_distance --> inf 向量的范数（减去一些随机值，仍然有效地产生 infs 向量）将再次产生 inf，所以

inf > v_quadratic_error

会是真的。在循环中，last_v 被覆盖，因此在下一次迭代中它将收敛。

Answer 2

在Matlab/Octave中：

octave:4> last_v = ones(N, 1) * inf;
octave:10> norm(v - last_v, 2)
ans = Inf
octave:13> norm(v - last_v, 2) > v_quadratic_error
ans =  1

在Python中：

In [139]: last_v = np.dot(np.ones((N,1)),ainf)
In [140]: np.linalg.norm(v - last_v, 2)
Out[140]: nan
In [141]: np.linalg.norm(v - last_v, 2) <= v_quadratic_error
Out[141]: False

所以条件在 Matlab/Octave 中为 True 但在 Python 中类似的表达式为 False。在 Python 中，而不是使用

while linalg.norm(v-last_v,2) > v_quadratic_error:

你可以使用

while True:
    last_v = v
    ...
    if np.linalg.norm(v - last_v, 2) <= v_quadratic_error: break

这保证了执行流程至少进入while-loop一次，然后在条件为真时中断。到那时 last_v 将具有有限值，因此避免了 NaN 与 Inf 问题。

import numpy as np

def pagerank(M, d, v_quadratic_error):
    count = 0
    N = M.shape[1]
    while True:
        v = np.random.rand(N, 1)
        if (v != 0).all(): break
    v = v / np.linalg.norm(v)
    R = d * M + ((1 - d) / N * np.ones((N, N)))
    while True:
        last_v = v
        v = np.dot(R, v)
        count += 1
        print('iteration # {}: {}'.format(count, np.isfinite(v)))
        if np.linalg.norm(v - last_v, 2) <= v_quadratic_error: break
    return v

M = np.array(np.mat('0 0 0 0 1 ; 0.5 0 0 0 0 ; 0.5 0 0 0 0 ; 0 1 0.5 0 0 ; 0 0 0.5 1 0'))
print(pagerank(M, 0.80, 0.001))

产量（类似）

[[ 0.46322263]
 [ 0.25968575]
 [ 0.25968575]
 [ 0.38623472]
 [ 0.48692059]]

PageRank python 实施、算法

PageRank python implementation, algorithm

python

matlab

pagerank

linear-algebra