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 4. APPROACH 4.1 Our Dynamic Frontier approach 4.1.2 A simple example. Figure 1 shows an example of the Dynamic Frontier approach. The initial graph, shown in Figure 1(a), comprises 16 vertices and 25 edges. Subsequently, Figure 1(b) shows a batch update applied to the original graph involving the deletion of an edge from vertex 2 to 1 and the insertion of an edge from vertex 4 to 12. Following the batch update, we perform the initial step of the Dynamic Frontier approach, marking outgoing neighbors of 2 and 4 as affected, i.e., 1, 3, 4, 8, and 12 are marked as affected (indicated with a yellow fill). Note that vertex 2 is not affected as it is a source of the change while vertex 4 being a neighbour of 2 is marked as affected. Now, we are ready to execute the first iteration of PageRank algorithm. During the first iteration (see Figure 1(c)), the ranks of affected vertices are updated. It is observed that the rank changes of vertices 1 and 12 surpass the frontier tolerance 𝜏𝑓 (highlighted with a red border). In response to this, we incrementally mark the outgoing neighbors of 1 and 12 as affected, i.e., vertices 3, 5, 11, and 14. During the second iteration (see Figure 1(d)), the ranks of affected vertices are again updated. Here, its is observed that the change in rank of vertices 3, 5, 11, and 14 is greater than frontier tolerance 𝜏𝑓 . Thus, we mark the outgoing neighbors of 3, 5, 11, and 14 as affected, namely vertices 4, 6, and 15. In the subsequent iteration, the ranks of affected vertices are again updated. If the change in rank of each vertex is within iteration tolerance 𝜏, the ranks of vertices have converged, and the algorithm terminates. 4.2 Synchronous vs Asynchronous implementation In a synchronous implementation, separate input and output rank vectors are used, ensuring deterministic results for parallel algorithms through vector swapping at the end of each iteration. In contrast, an asynchronous implementation utilizes a single rank vector, potentially achieving faster convergence and eliminating memory copies for unaffected vertices in dynamic approaches. 4.3 Determination of Frontier tolerance (𝜏𝑓) 4.4 Our Dynamic Frontier PageRank implementation Algorithm 1 shows our implementation of Dynamic Frontier PageRank, which is designed to compute the PageRank of vertices in a graph while efficiently handling dynamic changes in the graph structure over time. The algorithm takes as input the previous and current versions of the graph, edge deletions and insertions in the batch update, and the previous rank vector. 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 4. APPROACH 4.1 Our Dynamic Frontier approach 4.1.2 A simple example. Figure 1 shows an example of the Dynamic Frontier approach. The initial graph, shown in Figure 1(a), comprises 16 vertices and 25 edges. Subsequently, Figure 1(b) shows a batch update applied to the original graph involving the deletion of an edge from vertex 2 to 1 and the insertion of an edge from vertex 4 to 12. Following the batch update, we perform the initial step of the Dynamic Frontier approach, marking outgoing neighbors of 2 and 4 as affected, i.e., 1, 3, 4, 8, and 12 are marked as affected (indicated with a yellow fill). Note that vertex 2 is not affected as it is a source of the change while vertex 4 being a neighbour of 2 is marked as affected. Now, we are ready to execute the first iteration of PageRank algorithm. 4.1.2 A simple example. During the first iteration (see Figure 1(c)), the ranks of affected vertices are updated. It is observed that the rank changes of vertices 1 and 12 surpass the frontier tolerance 𝜏𝑓 (highlighted with a red border). In response to this, we incrementally mark the outgoing neighbors of 1 and 12 as affected, i.e., vertices 3, 5, 11, and 14. During the second iteration (see Figure 1(d)), the ranks of affected vertices are again updated. Here, its is observed that the change in rank of vertices 3, 5, 11, and 14 is greater than frontier tolerance 𝜏𝑓 . Thus, we mark the outgoing neighbors of 3, 5, 11, and 14 as affected, namely vertices 4, 6, and 15. In the subsequent iteration, the ranks of affected vertices are again updated. If the change in rank of each vertex is within iteration tolerance 𝜏, the ranks of vertices have converged, and the algorithm terminates. 4.2 Synchronous vs Asynchronous implementation In a synchronous implementation, separate input and output rank vectors are used, ensuring deterministic results for parallel algorithms through vector swapping at the end of each iteration. In contrast, an asynchronous implementation utilizes a single rank vector, potentially achieving faster convergence and eliminating memory copies for unaffected vertices in dynamic approaches. 4.3 Determination of Frontier tolerance (𝜏𝑓) 4.4 Our Dynamic Frontier PageRank implementation Algorithm 1 shows our implementation of Dynamic Frontier PageRank, which is designed to compute the PageRank of vertices in a graph while efficiently handling dynamic changes in the graph structure over time. The algorithm takes as input the previous and current versions of the graph, edge deletions and insertions in the batch update, and the previous rank vector. 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.

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Batch Processing Role in Deep Learning

Best Practices for Effective AI Model Deployment

Implementing AI in Retail With Apache Cassandra and Apache Pulsar

Streaming Wars: Why Apache Flink Could Outshine Spark

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Batch Processing Role in Deep Learning

Best Practices for Effective AI Model Deployment

Implementing AI in Retail With Apache Cassandra and Apache Pulsar

Streaming Wars: Why Apache Flink Could Outshine Spark

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps