# An Incrementally Expanding Approach for Updating PageRank on Dynamic Graphs

**Authors:** Subhajit Sahu  
**arXiv:** [2401.03256](https://arxiv.org/abs/2401.03256)  
**Date:** 2024-01-06  
**Summary page:** https://www.summarizepaper.com/en/paper/2401.03256v1/

## Key points

- PageRank is a widely used centrality metric that assigns importance to vertices in a graph based on their connections and scores.
- Efficient parallel algorithms for updating PageRank on dynamic graphs are essential for various applications, especially as dataset sizes continue to grow.
- The Dynamic Frontier approach aims to efficiently update PageRank in response to batch updates involving edge deletions and insertions by progressively identifying affected vertices likely to change ranks with minimal overhead.
- Performance comparison results showed that Dynamic Frontier PageRank outperformed Static, Naive-dynamic, and Dynamic Traversal methods significantly when subjected to uniformly random batch updates ranging from size 10^-7 |E| to 10^-3 |E|.
- Detailed analysis conducted on various graph datasets demonstrated the effectiveness of the Dynamic Frontier approach in updating PageRank efficiently across different types of graphs.

## Summary

, , , , 

PageRank is a widely used centrality metric that assigns importance to vertices in a graph based on their connections and scores. Efficient parallel algorithms for updating PageRank on dynamic graphs are essential for various applications, especially as dataset sizes continue to grow. In this technical report, the authors introduce their Dynamic Frontier approach, which aims to efficiently update PageRank in response to batch updates involving edge deletions and insertions. The Dynamic Frontier method progressively identifies affected vertices that are likely to change their ranks with minimal overhead. The authors conducted experiments on a server equipped with a 64-core AMD EPYC-7742 processor, comparing the performance of Dynamic Frontier PageRank with Static, Naive-dynamic, and Dynamic Traversal PageRank methods. The results showed that Dynamic Frontier PageRank outperformed the other methods by significant margins: 7.8x better than Static, 2.9x better than Naive-dynamic, and 3.9x better than Dynamic Traversal PageRank when subjected to uniformly random batch updates ranging from size 10^-7 |E| to 10^-3 |E|. Additionally, the approach demonstrated an average performance improvement rate of 1.8x for every doubling of threads. Furthermore, detailed analysis was conducted on various graph datasets such as indochina-2004, arabic-2005, uk-2005, webbase-2001, it-2004, sk-2005, com-LiveJournal, com-Orkut, asia_osm,europe_osm,kmer_A2a,and kmer_V1r.The results showcased the effectiveness of the Dynamic Frontier approach in updating PageRank efficiently across different types of graphs. Overall, the study highlights the significance of efficient parallel algorithms like Dynamic Frontier in updating PageRank on dynamic graphs and demonstrates its superior performance compared to existing methods across various scenarios and datasets.