Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

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.