Rank adjustment strategies for Dynamic PageRank : REPORT

report-rank-adjustment-strategies-for-incremental-dynamic-pagerank.md

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.

report-rank-adjustment-strategies-for-incremental-dynamic-pagerank.pdf

slides-rank-adjustment-strategies-for-incremental-dynamic-pagerank.pdf