TruRank: taking PageRank to the limit

ABSTRACT

PageRank is defined as the stationary state of a Markov chain depending on a damping factor α that spreads uniformly part of the rank. The choice of α is eminently empirical, and in most cases the original suggestion α=0.85 by Brin and Page is still used. It is common belief that values of α closer to 1 give a "truer to the web" PageRank, but a small α accelerates convergence. Recently, however, it has been shown that when α=1 all pages in the core component are very likely to have rank 0 [1]. This behaviour makes it difficult to understand PageRank when α≈1, as it converges to a meaningless value for most pages. We propose a simple and natural modification to the standard preprocessing performed on the adjacency matrix of the graph, resulting in a ranking scheme we call TruRank. TruRank ranks the web with principles almost identical to PageRank, but it gives meaningful values also when α☰ 1.

REFERENCES

• 1: Paolo Boldi , Massimo Santini , Sebastiano Vigna, PageRank as a function of the damping factor, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060827]
• 2: [2] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, Stanford University, Stanford, CA, USA, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
PageRank, web graph