Efficient PageRank Updates on Dynamic Graphs and Existing Approaches

This section covers the PageRank algorithm's iterative computation, its challenges like dead ends, and updates on dynamic graphs through batch processing. Existing methods like Naive-dynamic recompute PageRank entirely, while Dynamic Traversal selectively processes affected vertices. Dynamic graph frameworks such as Aspen minimize snapshot costs, enabling efficient PageRank updates in evolving networks.

Table of Links

Abstract and 1 Introduction

2 Related Work

3 Preliminaries

4 Approach

5.1 Experimental Setup

5.2 Performance of Dynamic Frontier PageRank

5.3 Strong Scaling of Dynamic Frontier PageRan

6 Conclusion, Acknowledgments, and References

3 PRELIMINARIES

3.1 PageRank Algorithm

The PageRank, 𝑅[𝑣], of a vertex 𝑣 ∈ 𝑉 in the graph 𝐺(𝑉 , 𝐸), represents its importance and is based on the number of incoming links and their significance. Equation 1 shows how to calculate the PageRank of a vertex 𝑣 in ...