First passage percolation on inhomogeneous random graphs

DOI10.1239/AAP/1435236989zbMATH Open1317.05176arXiv1201.3137OpenAlexW1908254782MaRDI QIDQ5262455FDOQ5262455

Author name not available (Why is that?)

Publication date: 15 July 2015

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: We investigate first passage percolation on inhomogeneous random graphs. The random graph model G(n,kappa) we study is the model introduced by Bollob'as, Janson and Riordan, where each vertex has a type from a type space S and edge probabilities are independent, but depending on the types of the end vertices. Each edge is given an independent exponential weight. We determine the distribution of the weight of the shortest path between uniformly chosen vertices in the giant component and show that the hopcount, i.e. the number of edges on this minimal weight path, properly normalized follows a central limit theorem. We handle the cases where lambda(n)->lambda is finite or infinite, under the assumption that the average number of neighbors lambda(n) of a vertex is independent of the type. The paper is a generalization the paper by Bhamidi, van der Hofstad and Hooghiemstra, where FPP is explored on the Erdos-Renyi graphs.

Full work available at URL: https://arxiv.org/abs/1201.3137

Recommendations

• First passage percolation on the Erdős-Rényi random graph
• First passage percolation on locally treelike networks. I. Dense random graphs
• Universality for first passage percolation on sparse random graphs
• First passage percolation on random graphs with finite mean degrees
• Nonuniversality of weighted random graphs with infinite variance degree

zbMATH Keywords

first passage percolationhopcountinhomogeneous random graphcontinuous-time multitype branching processshortest-weight path

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Applications of branching processes (60J85) Stochastic network models in operations research (90B15)

Cites Work

• The phase transition in inhomogeneous random graphs
• Connected components in random graphs with given expected degree sequences
• The Average Distance in a Random Graph with Given Expected Degrees
• On a conditionally Poissonian graph process
• Generating simple random graphs with prescribed degree distribution
• First passage percolation on random graphs with finite mean degrees
• Distances in random graphs with finite mean and infinite variance degrees
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• First Passage Percolation on the Erdős–Rényi Random Graph
• Approximating the epidemic curve
• Almost Sure Behavior of Linear Functionals of Supercritical Branching Processes
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• The Numbers of Generations in a Branching Process with an Arbitrary Set of Particle Types
• The front of the epidemic spread and first passage percolation
• Generations and degree of relationship in supercritical Markov branching processes
• The diameter of random regular graphs
• Weak disorder asymptotics in the stochastic mean-field model of distance
• First passage percolation on locally treelike networks. I. Dense random graphs
• Distances in random graphs with finite variance degrees
• Title not available (Why is that?)
• Title not available (Why is that?)
• The diameter of weighted random graphs
• The diameter of sparse random graphs

Cited In (15)

• Weighted distances in scale-free configuration models
• Competing first passage percolation on random regular graphs
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• First passage percolation on the Newman-Watts small world model
• Title not available (Why is that?)
• Inhomogeneous first-passage percolation
• Asymptotics of First-Passage Percolation on One-Dimensional Graphs
• Information Spreading in a Large Population of Active Transmitters and Passive Receivers
• First passage percolation on locally treelike networks. I. Dense random graphs
• First passage percolation on sparse random graphs with boundary weights
• First passage percolation on nilpotent Cayley graphs and beyond
• Random shortest paths: non-Euclidean instances for metric optimization problems
• Short paths for first passage percolation on the complete graph
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks

This page was built for publication: First passage percolation on inhomogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5262455)