First passage percolation on inhomogeneous random graphs

DOI10.1239/AAP/1435236989MaRDI QIDQ5262455zbMATH OpenOpenAlexFDO

Authors

Publication date 15 July 2015

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

Full work available at URL https://arxiv.org/abs/1201.3137, https://projecteuclid.org/euclid.aap/1435236989

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)

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.

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

Cites work

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

Cited in

(18)

• First passage percolation on locally treelike networks. I. Dense random graphs
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• Polynomial growth in degree-dependent first passage percolation on spatial random graphs
• Inhomogeneous first-passage percolation
• First passage percolation on the Newman-Watts small world model
• Universality for first passage percolation on sparse random graphs
• First passage percolation on the Erdős-Rényi random graph
• Weighted distances in scale-free configuration models
• Information Spreading in a Large Population of Active Transmitters and Passive Receivers
• First passage percolation on sparse random graphs with boundary weights
• Competing first passage percolation on random regular graphs
• Short paths for first passage percolation on the complete graph
• Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks
• scientific article; zbMATH DE number 3907536 (Why is no real title available?)
• First passage percolation on nilpotent Cayley graphs and beyond
• First-passage percolation on ladder-like graphs with inhomogeneous exponential times
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Asymptotics of First-Passage Percolation on One-Dimensional Graphs

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)