Skip to content

Instantly share code, notes, and snippets.

@wolfram77

wolfram77/notes-incremental-page-rank-computation-on-evolving-graphs.md

Last active September 26, 2021 01:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save wolfram77/f0a7534d49d5c07d4479ec3966c5d635 to your computer and use it in GitHub Desktop.
Save wolfram77/f0a7534d49d5c07d4479ec3966c5d635 to your computer and use it in GitHub Desktop.
Download ZIP
Incremental Page Rank Computation on Evolving Graphs : NOTES
Raw
notes-incremental-page-rank-computation-on-evolving-graphs.md

Highlighted notes on:
Incremental Page Rank Computation on Evolving Graphs.
While doing research work with:
Prof. Dip Sankar Banerjee and Prof. Kishore Kothapalli:
https://dl.acm.org/doi/10.1145/1062745.1062885

This paper describes a simple method for computing dynamic pagerank, based on the fact that change of out-degree of a node does not affect its pagerank (first order markov property). The part of graph which is updated (edge additions / edge deletions / weight changes) is used to find the affected partition of graph using BFS. The unaffected partition is simply scaled, and pagerank computation is done only for the affected partition.

Display the source blob
Display the rendered blob
Raw
notes-incremental-page-rank-computation-on-evolving-graphs.pdf
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment