【作者】 张宇；

【导师】 凌思涛；

【作者基本信息】 中国矿业大学 ， 数学， 2024， 硕士

【摘要】 非回溯PageRank是经典PageRank算法的一种变体,它是一种基于非回溯随机游走的算法。然而,如果网络中存在大量悬挂节点,会导致非回溯PageRank算法需要巨大的内存和高昂的计算代价。因此,非回溯PageRank算法仅适用于悬挂节点较少的中小型图。在本论文中,首先考虑使用Jacobi迭代方法来近似求解非回溯PageRank的问题。然后,本论文提出了两种加速非回溯PageRank算法的策略,分别是随机非回溯PageRank和确定性非回溯PageRank。不论是采用“随机”还是“确定性”方法,在计算过程中本论文都充分利用了非回溯PageRank算法独特的结构性和稀疏性,并详细讨论了具体的计算过程。本论文提出的改进算法具有两个方面的创新。首先,与原始的非回溯PageRank相比,矩阵计算问题的规模大大缩小。其次,在随机和确定性方法中,不需要形成带有Kronecker积的非回溯边矩阵,从而大大简化了非回溯PageRank问题的结构。我们在一些真实网络矩阵进行了有关的数值实验,结果表明提出的两种算法得到的解与非回溯PageRank算法高度相关,并且这两种算法的速度比原始算法快几十倍甚至几百倍。更多还原

【Abstract】 Non-backtracking PageRank is a variation of Google ’s PageRank,which is based on a non-backtracking random walk.However,if the number of dangling nodes of a graph is large,the non-backtracking PageRank algorithm may suffer from huge memory requirements and heavily computational costs.Thus,the non-backtracking PageRank algorithm is only applicable to small-scale or medium-sized graphs with few dangling nodes.In this work,we first consider how to compute the non-backtracking PageRank vector efficiently by using the Jacobi iteration,and then propose two strategies to speed up the computation of non-backtracking PageRank.The first one is the randomized non-backtracking PageRank and the second one is the deterministic nonbacktracking PageRank,in which we add some edges to a graph in a randomized and a deterministic way,respectively.The computational issues exploiting the structure and sparsity of the underlying matrices are discussed in detail.The advantages of the proposed algorithms are two-fold.First,the sizes of the matrix computation problems are much smaller than that of the original one.Second,there is no kronecker product in the randomized and deterministic non-backtracking edge matrices,and the structure of the non-backtracking PageRank problem is greatly simplified.Comprehensive numerical experiments are performed on some real-world network matrices,which show that the solutions obtained from the two proposed algorithms and that from the non-backtracking PageRank algorithm are highly correlated,while the two proposed algorithms can be tens or even hundreds times faster than their original counterpart.更多还原