A local updating algorithm for Personalized PageRank via Chebyshev Polynomials

Esteban Bautista, Matthieu Latapy

In Social Network Analysis and Mining, 2022, vol. 12, no 1, p. 1-11.

The personalized PageRank algorithm is one of the
most versatile tools for the analysis of networks. In spite of its
ubiquity, maintaining personalized PageRank vectors when the
underlying network constantly evolves is still a challenging task.
To address this limitation, this work proposes a novel distributed
algorithm to locally update personalized PageRank vectors when
the graph topology changes. The proposed algorithm is based on
the use of Chebyshev polynomials and a novel update equation
that encompasses a large family of PageRank-based methods.
In particular, the algorithm has the following advantages: (i) it
has faster convergence speed than state-of-the-art alternatives
for local PageRank updating; and (ii) it can update the solution
of recent generalizations of PageRank for which no updating
algorithms have been developed. Experiments in a real-world
temporal network of an autonomous system validate the effec-
tiveness of the proposed algorithm.