Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save wolfram77/eb7a3b2e44e3c2069e046389b45ead03 to your computer and use it in GitHub Desktop.
Save wolfram77/eb7a3b2e44e3c2069e046389b45ead03 to your computer and use it in GitHub Desktop.
Rank adjustment strategies for Dynamic PageRank : REPORT

Rank adjustment strategies for Incremental / Dynamic PageRank

While doing research work with Prof. Kishore Kothapalli, and Prof. Dip Sankar Banerjee.

Abstract — To avoid calculating ranks of vertices in a dynamic graph from scratch for every snapshot, the ones computed in the previous snapshot of the graph can be used, with adjustment. Four different rank adjustment strategies for dynamic PageRank are studied here. These include zero-fill, 1/N-fill, scaled zero-fill, and scaled 1/N-fill. Results indicate that both 1/N-fill and scaled 1/N-fill strategies require the least number of iterations, on average. As long as the graph has no affected dead ends (including dead ends in the previous snapshot), unaffected vertices can be skipped with the scaled 1/N-fill adjustment strategy. (🎞️ slides)

Index terms — Temporal graph, Incremental / Dynamic PageRank, Rank adjustment, Initial ranks, Affected vertices, Scaled 1/N-fill strategy.


Experiments

Update new vertices only zero-fill 1/N-fill
Update old and new vertices scaled zero-fill scaled 1/N-fill
  1. Comparing strategies to update ranks for incremental/dynamic PageRank.
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Loading
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