First Passage Percolation on Inhomogeneous Random Graphs

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ás, 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.

References in corpus (3)

• Generating simple random graphs with prescribed degree distribution
• Distances in random graphs with finite variance degrees
• The diameter of weighted random graphs

Cited by in corpus (9)

• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Explosion and distances in scale-free percolation
• Weighted distances in scale-free configuration models
• Explosive Crump-Mode-Jagers branching processes
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• First passage percolation on the Newman-Watts small world model
• Degrees and distances in random and evolving Apollonian networks
• Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
• First passage percolation on Erdős-Rényi graphs with general weights