PageRank is a fundamental property of graph and there have been plenty of PageRank algorithms. Generally, we consider undirected graph as a complicated directed graph. However, some properties of undirected graph, such as symmetry, are ignored when computing PageRank by existing algorithms. In this paper, we propose a parallel PageRank algorithm which is specially for undirected graph. We first demonstrate that the PageRank vector can be viewed as a linear combination of eigenvectors of probability transition matrix and the corresponding coefficients are the functions of eigenvalues. Then we introduce the Chebyshev polynomial approximation by which PageRank vector can be computed iteratively. Finally, we propose the parallel PageRank algorithm as the Chebyshev polynomial approximating algorithm(CPAA). Experimental results show that CPAA only takes 60% of iteration rounds of the power method and is at least 4 times faster than the power method.
翻译:PageRank 是图形的一个基本属性, 并有大量 PageRank 算法。 一般来说, 我们把非方向性图表视为复杂的定向图形。 但是, 在用现有算法计算 PageRank 时, 某些非方向性图表的属性, 如对称性, 被忽略。 在本文中, 我们提议了一种平行的 PageRank 算法, 专门用于非方向性图表 。 我们首先显示, PageRank 矢量可被视为概率转换矩阵和相应系数的元素的线性组合。 然后, 我们引入了 Chebyshev 多边近似值, 从而可以迭代计算 PageRank 矢量。 最后, 我们提议将平行的 PageRank 算法建议为 Chebyshev 多元相近算算算算算算法 。 我们实验结果显示, CPAAA 只能使用60% 的电源法循环, 并且至少比电法快4倍 。