Graph fibrations, graph isomorphism, and PageRank
Paolo Boldi, Violetta Lonati, Massimo Santini, Sebastiano Vigna (2006)
RAIRO - Theoretical Informatics and Applications
Similarity:
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and , a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the values that PageRank...