Author:
(1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India (subhajit.sahu@research.iiit.ac.in). 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 web page ranking, identifying misinformation, predicting traffic flow, and protein target identification. The increasing availability of vast amounts of data represented as graphs has led to a significant interest in parallel algorithms for computing PageRank [10–12, 23]. However, most real-world graph evolve with time. Here, frequent edge insertions and deletions make recomputing PageRank from scratch impractical, particularly for small, rapid changes. Existing strategies optimize by iterating from the prior snapshot’s ranks, reducing the number of iterations needed for convergence. For further improvements, it is essential to recompute only the ranks of vertices likely to change. A prevalent approach involves identifying reachable vertices from the updated regions of the graph, and limiting processing to such vertices. However, if updates are randomly distributed, they often fall within dense graph regions, necessitating processing of a substantial portion of the graph. To reduce computational effort, one can incrementally expand the set of affected vertices starting from the updated graph region, rather than processing all reachable vertices from the first iteration. Additionally, it is possible to skip processing a vertex’s neighbors if the change in its rank is small and is expected to have minimal impact on the ranks of its neighboring vertices. This technical report introduces such an approach. 1.1 Our Contributions This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. Author: (1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India (subhajit.sahu@research.iiit.ac.in). Author: Author: (1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India (subhajit.sahu@research.iiit.ac.in). Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Related Work 2 Related Work 3 Preliminaries 3 Preliminaries 4 Approach 4 Approach 5.1 Experimental Setup 5.1 Experimental Setup 5.2 Performance of Dynamic Frontier PageRank 5.2 Performance of Dynamic Frontier PageRank 5.3 Strong Scaling of Dynamic Frontier PageRan 5.3 Strong Scaling of Dynamic Frontier PageRan 6 Conclusion, Acknowledgments, and References 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 web page ranking, identifying misinformation, predicting traffic flow, and protein target identification. The increasing availability of vast amounts of data represented as graphs has led to a significant interest in parallel algorithms for computing PageRank [10–12, 23]. However, most real-world graph evolve with time. Here, frequent edge insertions and deletions make recomputing PageRank from scratch impractical, particularly for small, rapid changes. Existing strategies optimize by iterating from the prior snapshot’s ranks, reducing the number of iterations needed for convergence. For further improvements, it is essential to recompute only the ranks of vertices likely to change. A prevalent approach involves identifying reachable vertices from the updated regions of the graph, and limiting processing to such vertices. However, if updates are randomly distributed, they often fall within dense graph regions, necessitating processing of a substantial portion of the graph. To reduce computational effort, one can incrementally expand the set of affected vertices starting from the updated graph region, rather than processing all reachable vertices from the first iteration. Additionally, it is possible to skip processing a vertex’s neighbors if the change in its rank is small and is expected to have minimal impact on the ranks of its neighboring vertices. This technical report introduces such an approach. 1.1 Our Contributions This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Incremental Vertex Processing Boosts PageRank Update Efficiency on Dynamic Graphs

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Key Insights and Future Directions for PageRank on Dynamic Graphs

Python Web Development with Reflex: Creating Dynamic Graphs Easily

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Strong Scaling Achieves 15.2× Speedup for Dynamic Graph Updates with Multi-Threaded Efficiency

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Key Insights and Future Directions for PageRank on Dynamic Graphs

Python Web Development with Reflex: Creating Dynamic Graphs Easily

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Strong Scaling Achieves 15.2× Speedup for Dynamic Graph Updates with Multi-Threaded Efficiency

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps