Comparing Apples and Oranges: Normalized PageRank for Evolving Graphs
- Klaus Berberich (Max-Planck Institute for Informatics)
- Srikanta Bedathur (Max-Planck Institute for Informatics)
- Gerhard Weikum (Max-Planck Institute for Informatics)
- Michalis Vazirgiannis (INRIA/FUTURS)
PageRank is the best known technique for link-based importance ranking. The computed importance scores, however, are not directly comparable across different snapshots of an evolving graph. We present an efficiently computable normalization for PageRank scores that makes them comparable across graphs. Furthermore, we show that the normalized PageRank scores are robust to non-local changes in the graph, unlike the standard PageRank measure.