Using Graph Partitioning to Calculate PageRank in a Changing Network
Christopher Engström, Sergei D. Silvestrov · 2019
PageRank was first defined by S. Brin and L. Page in 1998 in order to rank home pages on the Internet by ranking pages according to the stationary distribution of a random walk on the web graph. While the original way to calculate PageRank is fast, due to the huge size and growth of the web there have been many attempts at improving upon the calculation speed of PageRank through various means. This chapter looks at a slightly different but equally important problem, namely how to improve the calculation of PageRank in a changing network where PageRank of an earlier stage of the network is available. In particular, it considers two types of changes in the graph, the change in rank after changing the personalization vector used in calculating PageRank as well as added or removed edges between different strongly connected components (SCCs) in the network.