Graph fibrations, graph isomorphism, and PageRank

DOI10.1051/ita:2006004zbMath1112.68002OpenAlexW2148357992MaRDI QIDQ3431437

Sebastiano Vigna, Paolo Boldi, Massimo Santini, Violetta Lonati

Publication date: 10 April 2007

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2006__40_2_227_0

zbMATH Keywords

graph fibrationsPageRankMarkov chain with restart

Mathematics Subject Classification ID

Searching and sorting (68P10) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Stochastic matrices (15B51) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Traps and Pitfalls of Topic-Biased PageRank ⋮ On some analytical properties of a general PageRank algorithm ⋮ Google pageranking problem: The model and the analysis ⋮ Approximate lumpability for Markovian agent-based models using local symmetries ⋮ Spectral rank monotonicity on undirected networks

Uses Software

• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partial least-squares vs. Lanczos bidiagonalization. I: Analysis of a projection method for multiple regression
• Non-negative matrices and Markov chains. 2nd ed
• Partitioning a graph in \(O(|A|\log_ 2|V|)\)
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Constant-to-one and onto global maps of homomorphisms between strongly connected graphs
• An Introduction to Symbolic Dynamics and Coding
• Paradoxical Effects in PageRank Incremental Computations
• Perturbation theory and finite Markov chains
• An Efficient Algorithm for Graph Isomorphism
• GIT—a heuristic program for testing pairs of directed line graphs for isomorphism
• Fibrations of graphs