Geodesic
Graph fibrations, graph isomorphism, and pagerank
Boldi, Paolo ; Lonati, Violetta ; Santini, Massimo1 ; Vigna, Sebastiano
1 Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy;
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 227-253

Voir la notice de l'article provenant de la source Numdam

PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration 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 Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the values that PageRank can assume. Using our results, we show that a recently defined class of graphs that admit a polynomial-time isomorphism algorithm based on the computation of PageRank is really a subclass of fibration-prime graphs, which possess simple, entirely discrete polynomial-time isomorphism algorithms based on classical techniques for graph isomorphism. We discuss efficiency issues in the implementation of such algorithms for the particular case of web graphs, in which O(n) space occupancy (where n is the number of nodes) may be acceptable, but O(m) is not (where m is the number of arcs).

DOI : 10.1051/ita:2006004
Classification : 05C50, 05C85, 05C60, 94C15, 60J10, 15A51
Keywords: graph fibrations, pagerank, Markov chain with restart

Boldi, Paolo  ; Lonati, Violetta  ; Santini, Massimo 1 ; Vigna, Sebastiano 

1 Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy; 
@article{ITA_2006__40_2_227_0,
     author = {Boldi, Paolo and Lonati, Violetta and Santini, Massimo and Vigna, Sebastiano},
     title = {Graph fibrations, graph isomorphism, and pagerank},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {227--253},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {2},
     year = {2006},
     doi = {10.1051/ita:2006004},
     mrnumber = {2252637},
     zbl = {1112.68002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2006004/}
}
TY  - JOUR
AU  - Boldi, Paolo
AU  - Lonati, Violetta
AU  - Santini, Massimo
AU  - Vigna, Sebastiano
TI  - Graph fibrations, graph isomorphism, and pagerank
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 227
EP  - 253
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2006004/
DO  - 10.1051/ita:2006004
LA  - en
ID  - ITA_2006__40_2_227_0
ER  - 
%0 Journal Article
%A Boldi, Paolo
%A Lonati, Violetta
%A Santini, Massimo
%A Vigna, Sebastiano
%T Graph fibrations, graph isomorphism, and pagerank
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 227-253
%V 40
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2006004/
%R 10.1051/ita:2006004
%G en
%F ITA_2006__40_2_227_0
Boldi, Paolo; Lonati, Violetta; Santini, Massimo; Vigna, Sebastiano. Graph fibrations, graph isomorphism, and pagerank. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 227-253. doi: 10.1051/ita:2006004

Cité par Sources :