This content originally appeared on HackerNoon and was authored by PageRank
:::info Author:
(1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India (subhajit.sahu@research.iiit.ac.in).
:::
Table of Links
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.
\
\
:::info This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license.
:::
\
This content originally appeared on HackerNoon and was authored by PageRank
PageRank | Sciencx (2025-01-22T18:30:15+00:00) Efficient PageRank Updates on Dynamic Graphs and Existing Approaches. Retrieved from https://www.scien.cx/2025/01/22/efficient-pagerank-updates-on-dynamic-graphs-and-existing-approaches/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.