A parallel PageRank algorithm for undirected graph

Qi Zhang, Rongxia Tang, Zhengan Yao and Zan-Bo Zhang

Applied Mathematics and Computation, 2023, vol. 459, issue C

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—symmetry on edges, for example—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 a 50% higher convergence rate when the damping factor c=0.85. Experiments on six datasets illustrate that our algorithm with 38 parallelism can be up to 43 times faster than the single-thread Power method.

Keywords: PageRank; Undirected graph; Chebyshev Polynomial; Parallel (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323004459
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:459:y:2023:i:c:s0096300323004459

DOI: 10.1016/j.amc.2023.128276

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().