Incremental Vertex Processing Boosts PageRank Update Efficiency on Dynamic Graphs

Dynamic Frontier enhances PageRank updates on evolving graphs by incrementally processing only the affected vertices after edge insertions or deletions. This approach minimizes computational overhead, outperforming Static, Naive-dynamic, and Dynamic Traversal methods by up to 7.8× on parallel systems. It achieves an average performance boost of 1.8× with each doubling of threads, making it highly efficient for large-scale, dynamic datasets.

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

ABSTRACT

KEYWORDS

Parallel PageRank algorithm, Dynamic Frontier approach

1. INTRODUCTION

PageRank [19] is an algorithm that measures the importance of nodes in a network by assigning numerical scores based on the structure of links. It finds applications in ...