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 3 PRELIMINARIES 3.1 PageRank Algorithm The PageRank, 𝑅[𝑣], of a vertex 𝑣 ∈ 𝑉 in the graph 𝐺(𝑉 , 𝐸), represents its importance and is based on the number of incoming links and their significance. Equation 1 shows how to calculate the PageRank of a vertex 𝑣 in the graph 𝐺, with 𝑉 as the set of vertices (𝑛 = |𝑉 |), 𝐸 as the set of edges (𝑚 = |𝐸|), 𝐺.𝑖𝑛(𝑣) as the incoming neighbors of vertex 𝑣, 𝐺.𝑜𝑢𝑡(𝑣) as the outgoing neighbors of vertex 𝑣, and 𝛼 as the damping factor. Each vertex starts with an initial PageRank of 1/𝑛. The power-iteration method updates these values iteratively until the change is rank values is within a specified tolerance 𝜏 value (indicating that convergence has been achieved). Presence of dead ends is an issue that arises when computing the PageRank of a graph. A dead end is a vertex with no out-link, which forces the random surfer to jump to a random page on the web. Or equivalently, a dead end contributes its rank among all the vertices in the graph (including itself). This introduces a global teleport rank contribution that must be computed every iteration, and can be considered an overhead. We resolve this issue by adding self-loops to all the vertices in the graph [1, 15]. 3.2 Dynamic Graphs Interleaving of graph update and computation: Changes to the graph arrive in a batched manner, with updating of the graph and execution of the desired algorithm being interleaved (i.e., there is only one writer upon the graph at a given point of time). In case it is desirable to update the graph while an algorithm is still running, a snapshot of the graph needs to be obtained, upon which the desired algorithm may be executed. See for example Aspen graph processing framework which significantly minimizes the cost of obtaining a read-only snapshot of the graph [8]. 3.3 Existing approaches for updating PageRank on Dynamic Graphs 3.3.1 Naive-dynamic approach. This is a straightforward approach of updating ranks of vertices in dynamic networks. Here, one initializes the ranks of vertices with ranks obtained from previous snapshot of the graph and runs the PageRank algorithm on all vertices. Rankings obtained through this method will be at least as accurate as those obtained through the static algorithm. 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 3 PRELIMINARIES 3.1 PageRank Algorithm The PageRank, 𝑅[𝑣], of a vertex 𝑣 ∈ 𝑉 in the graph 𝐺(𝑉 , 𝐸), represents its importance and is based on the number of incoming links and their significance. Equation 1 shows how to calculate the PageRank of a vertex 𝑣 in the graph 𝐺, with 𝑉 as the set of vertices (𝑛 = |𝑉 |), 𝐸 as the set of edges (𝑚 = |𝐸|), 𝐺.𝑖𝑛(𝑣) as the incoming neighbors of vertex 𝑣, 𝐺.𝑜𝑢𝑡(𝑣) as the outgoing neighbors of vertex 𝑣, and 𝛼 as the damping factor. Each vertex starts with an initial PageRank of 1/𝑛. The power-iteration method updates these values iteratively until the change is rank values is within a specified tolerance 𝜏 value (indicating that convergence has been achieved). Presence of dead ends is an issue that arises when computing the PageRank of a graph. A dead end is a vertex with no out-link, which forces the random surfer to jump to a random page on the web. Or equivalently, a dead end contributes its rank among all the vertices in the graph (including itself). This introduces a global teleport rank contribution that must be computed every iteration, and can be considered an overhead. We resolve this issue by adding self-loops to all the vertices in the graph [1, 15]. 3.2 Dynamic Graphs Interleaving of graph update and computation: Changes to the graph arrive in a batched manner, with updating of the graph and execution of the desired algorithm being interleaved (i.e., there is only one writer upon the graph at a given point of time). In case it is desirable to update the graph while an algorithm is still running, a snapshot of the graph needs to be obtained, upon which the desired algorithm may be executed. See for example Aspen graph processing framework which significantly minimizes the cost of obtaining a read-only snapshot of the graph [8]. Interleaving of graph update and computation: 3.3 Existing approaches for updating PageRank on Dynamic Graphs 3.3.1 Naive-dynamic approach. This is a straightforward approach of updating ranks of vertices in dynamic networks. Here, one initializes the ranks of vertices with ranks obtained from previous snapshot of the graph and runs the PageRank algorithm on all vertices. Rankings obtained through this method will be at least as accurate as those obtained through the static algorithm. 3.3.1 Naive-dynamic approach. 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.

Efficient PageRank Updates on Dynamic Graphs and Existing Approaches

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

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

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

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

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps