如何理解这种高效的 PageRank 计算实现

Question

作为参考，我使用的是 this 页面。我理解原始的 pagerank 方程

但我不明白为什么稀疏矩阵实现是正确的。下面是他们转载的代码：

def compute_PageRank(G, beta=0.85, epsilon=10**-4):
    '''
    Efficient computation of the PageRank values using a sparse adjacency 
    matrix and the iterative power method.

    Parameters
    ----------
    G : boolean adjacency matrix. np.bool8
        If the element j,i is True, means that there is a link from i to j.
    beta: 1-teleportation probability.
    epsilon: stop condition. Minimum allowed amount of change in the PageRanks
        between iterations.

    Returns
    -------
    output : tuple
        PageRank array normalized top one.
        Number of iterations.

    '''    
    #Test adjacency matrix is OK
    n,_ = G.shape
    assert(G.shape==(n,n))
    #Constants Speed-UP
    deg_out_beta = G.sum(axis=0).T/beta #vector
    #Initialize
    ranks = np.ones((n,1))/n #vector
    time = 0
    flag = True
    while flag:        
        time +=1
        with np.errstate(divide='ignore'): # Ignore division by 0 on ranks/deg_out_beta
            new_ranks = G.dot((ranks/deg_out_beta)) #vector
        #Leaked PageRank
        new_ranks += (1-new_ranks.sum())/n
        #Stop condition
        if np.linalg.norm(ranks-new_ranks,ord=1)<=epsilon:
            flag = False        
        ranks = new_ranks
    return(ranks, time)

首先，我试图追踪代码并了解它与 PageRank 方程式的关系。对于 with 语句 (new_ranks = G.dot((ranks/deg_out_beta))) 下的行，这看起来像是等式的第一部分（beta 乘以 M），但它似乎忽略了所有被零除的部分。我对此感到困惑，因为 PageRank 算法要求我们将零列替换为一列（沿对角线除外）。我不确定这里是如何解释的。

下一行 new_ranks += (1-new_ranks.sum())/n 是我认为是等式的第二部分。我能理解这是做什么的，但我看不出这是如何转化为原始方程式的。我原以为我们会做类似 new_ranks += (1-beta)*ranks.sum()/n.

的事情

Answer 1

发生这种情况是因为行总和

e.T * M * r = e.T * r

由M的列求和构造。带有系数 beta 的凸组合的效果是新 r 向量的总和再次为 1。现在算法所做的是取第一个矩阵向量乘积 b=beta*M*r 然后找到一个常数 c 这样 r_new = b+c*e 的行总和为 1。理论上这应该与公式所说的相同，但在浮点实践中，这种方法纠正并防止了 r 和中的浮点错误累积。

以这种方式计算还可以忽略零列，因为它们的补偿是自动计算的。

如何理解这种高效的 PageRank 计算实现

How to understand this efficient implementation of PageRank calculation

algorithm

sparse-matrix

numerical-methods

python-3.x