A parallel pagerank algorithm for undirected graph

DOI10.1016/J.AMC.2023.128276MaRDI QIDQ6095043zbMATH OpenFDO

Authors

Publication date 11 October 2023

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.01743

zbMATH Keywords

Chebyshev polynomialpagerankparallelundirected graph

Mathematics Subject Classification ID

Graph theory (05Cxx) Markov processes (60Jxx) Numerical linear algebra (65Fxx)

Abstract: As a measure of vertex importance according to the graph structure, PageRank has been widely applied in various fields. While many PageRank algorithms have been proposed in the past decades, few of them take into account whether the graph under investigation is directed or not. Thus, some important properties of undirected graph extemdash symmetry on edges, for example extemdash is ignored. In this paper, we propose a parallel PageRank algorithm specifically designed for undirected graphs that can fully leverage their symmetry. Formally, our algorithm extends the Chebyshev Polynomial approximation from the field of real function to the field of matrix function. Essentially, it reflects the symmetry on edges of undirected graph and the density of diagonalizable matrix. Theoretical analysis indicates that our algorithm has a higher convergence rate and requires less computation than the Power method, with the convergence rate being up to 50% higher with a damping factor of $c=0.85$. Experiments on six datasets illustrate that our algorithm with 38 parallelism can be up to 39 times faster than the Power method.

Recommendations

• Parallelizing the Computation of PageRank
• Distributed Randomized Algorithms for the PageRank Computation
• Parallel multisplitting iteration methods based on M-splitting for the PageRank problem
• An optimal parallel algorithm for node ranking of cographs
• Fast distributed PageRank computation
• Distributed randomized algorithms for PageRank computation: recent advances
• A sublinear time algorithm for PageRank computations

Cites work

• A Power–Arnoldi algorithm for computing PageRank
• A Survey on PageRank Computing
• Adaptive methods for the computation of PageRank
• Distributed random walks
• scientific article; zbMATH DE number 911331 (Why is no real title available?)
• Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
• PageRank beyond the web

This page was built for publication: A parallel pagerank algorithm for undirected graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095043)