Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save wolfram77/94c38b9cfbf0c855e5f42fa24a8602fc to your computer and use it in GitHub Desktop.
Save wolfram77/94c38b9cfbf0c855e5f42fa24a8602fc to your computer and use it in GitHub Desktop.
Dead End handling strategies for PageRank algorithm : REPORT

Dead End handling strategies for PageRank algorithm

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

Abstract — Presence of dead ends, which are vertices without any out-edges, in a graph under PageRank computation can cause importance to leak out. This is undesirable since this can cause ranks of all vertices to converge to zero, which is a valid, but useless solution. Four different dead end handling strategies for static, incremental, and dynamic PageRank are studied here. These include: teleport, loop, loop-all, and remove. Results indicate that the remove strategy performs best, on average. This however is suitable only if it is possible to keep track of the dead-end free version of the graph, as otherwise the cost of recursively removing dead ends from the graph is significant. The loop and loop-all strategies perform similarly. Additionally, loop-all is a fair strategy and may be a better choice for networks associated with people. Teleport strategy performs the worst, but this clearly depends upon the nature of the graph. However, it is the only strategy that does not allow distributed computation without per-iteration communication. When using 32-bit floating format for rank of each vertex on large graphs, precision issues are observed. This does not happen when 64-bit floating point format is used instead, indicating it to be a good choice when accuracy of ranks is important on large graphs. (🎞️ slides)

Index terms — Fixed / Temporal graphs, Static / Incremental / Dynamic PageRank, Dead ends, Teleport, Loop, Remove, Precision issues.


Experiments

fixed graphs static PageRank teleport loop loop-all remove
temporal graphs static PageRank teleport loop loop-all remove
temporal graphs incremental PageRank teleport loop loop-all remove
temporal graphs dynamic PageRank teleport loop loop-all remove
  1. Comparing various strategies of handling dead ends for PageRank (pull, CSR).
  2. Comparing various strategies of handling dead ends for dynamic PageRank (pull, CSR).
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