如何理解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))）下的行，这看起来像方程的第一部分（β乘以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之和中的浮点误差累积。

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