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 2. RELATED WORK A number of approaches have been proposed for performing incremental computation (updating PageRank values in a dynamic / evolving graph) of approximate PageRank. Chien et al. [6] identify a tiny region of the graph near the updated vertices and model the remainder of the graph as a single vertex in a new, much smaller graph. PageRanks are computed for the small graph and then transferred to the original graph. Chen et al. [5] propose a number of methods to estimate the PageRank score of a particular web page using only a small subgraph of the entire web, by expanding backwards from the target node following reverse hyperlinks. Bahmani et al. [2] analyze the efficiency of Monte Carlo methods for incremental computation of PageRank. Zhan et al. [24] propose a Monte Carlo based algorithm for PageRank tracking on dynamic networks, by maintaining 𝑅 random walks starting from each node. Pashikanti et al. [20] also follow a similar approach for updating PageRank scores on vertex and edge insertion/deletion. A few approaches have been proposed for updating exact PageRank scores on dynamic graphs. Zhang [25] presents a simple incremental Pagerank computation system for dynamic graphs on hybrid CPU and GPU platforms that incorporates the Update-GatherApply-Scatter (UGAS) computation model. A common approach used for Dynamic PageRank algorithm, given a small change to the input graph, is to find the affected region in the preprocessing step with Breadth-First Search (BFS) or Depth-First Search (DFS) traversal from the vertices connecting the edges that were inserted or deleted, and computing PageRanks only for that region [7, 12, 13, 22]. This approach was originally proposed by Desikan et al. [7]. Kim and Choi [13] use this approach with an asynchronous implementation of PageRank. Giri et al. [12] use this approach with collaborative executions on muti-core CPUs and massively parallel GPUs. Sahu et al. [22] use this approach on a Strongly Connected Component (SCC) based decomposition of the graph to limit the computation to SCCs that are reachable from updated vertices, on multi-core CPUs and GPUs (separately). Ohsaka et al. [18] propose an approach for locally updating PageRank using the Gauss-Southwell method, where the vertex with the greatest residual is updated first — however, their algorithm is inherently sequential. Further, Bahmani et al. [3] propose an algorithm to selectively crawl a small portion of the web to provide an estimate of true PageRank of the graph at that moment, while Berberich et al. [4] present a method to compute normalized PageRank scores that are robust to non-local changes in the graph. Their approaches are orthogonal to our Dynamic Frontier approach which focuses on the computation of the PageRank vector itself, not on the process of crawling the web or maintaining normalized scores. 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 2. RELATED WORK A number of approaches have been proposed for performing incremental computation (updating PageRank values in a dynamic / evolving graph) of approximate PageRank. Chien et al. [6] identify a tiny region of the graph near the updated vertices and model the remainder of the graph as a single vertex in a new, much smaller graph. PageRanks are computed for the small graph and then transferred to the original graph. Chen et al. [5] propose a number of methods to estimate the PageRank score of a particular web page using only a small subgraph of the entire web, by expanding backwards from the target node following reverse hyperlinks. Bahmani et al. [2] analyze the efficiency of Monte Carlo methods for incremental computation of PageRank. Zhan et al. [24] propose a Monte Carlo based algorithm for PageRank tracking on dynamic networks, by maintaining 𝑅 random walks starting from each node. Pashikanti et al. [20] also follow a similar approach for updating PageRank scores on vertex and edge insertion/deletion. A few approaches have been proposed for updating exact PageRank scores on dynamic graphs. Zhang [25] presents a simple incremental Pagerank computation system for dynamic graphs on hybrid CPU and GPU platforms that incorporates the Update-GatherApply-Scatter (UGAS) computation model. A common approach used for Dynamic PageRank algorithm, given a small change to the input graph, is to find the affected region in the preprocessing step with Breadth-First Search (BFS) or Depth-First Search (DFS) traversal from the vertices connecting the edges that were inserted or deleted, and computing PageRanks only for that region [7, 12, 13, 22]. This approach was originally proposed by Desikan et al. [7]. Kim and Choi [13] use this approach with an asynchronous implementation of PageRank. Giri et al. [12] use this approach with collaborative executions on muti-core CPUs and massively parallel GPUs. Sahu et al. [22] use this approach on a Strongly Connected Component (SCC) based decomposition of the graph to limit the computation to SCCs that are reachable from updated vertices, on multi-core CPUs and GPUs (separately). Ohsaka et al. [18] propose an approach for locally updating PageRank using the Gauss-Southwell method, where the vertex with the greatest residual is updated first — however, their algorithm is inherently sequential. Further, Bahmani et al. [3] propose an algorithm to selectively crawl a small portion of the web to provide an estimate of true PageRank of the graph at that moment, while Berberich et al. [4] present a method to compute normalized PageRank scores that are robust to non-local changes in the graph. Their approaches are orthogonal to our Dynamic Frontier approach which focuses on the computation of the PageRank vector itself, not on the process of crawling the web or maintaining normalized scores. 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.

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Dynamic Frontier PageRank Achieves Efficiency and Accuracy with Batch Updates and Parallel Computing

How to Make Sense of the Bipartite Graph

Python Web Development with Reflex: Creating Dynamic Graphs Easily

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

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

Dynamic Frontier PageRank Achieves Efficiency and Accuracy with Batch Updates and Parallel Computing

Dynamic Frontier PageRank Achieves Efficiency and Accuracy with Batch Updates and Parallel Computing

How to Make Sense of the Bipartite Graph

Python Web Development with Reflex: Creating Dynamic Graphs Easily

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

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

Dynamic Frontier PageRank Achieves Efficiency and Accuracy with Batch Updates and Parallel Computing

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps