Connectivity of inhomogeneous random graphs
Preprint
Abstract
We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when p = c log n/n. We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i,j) is added with probability min(1, \K(X_i,X_j) log n/n), where \K \ge 0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Percolation on dense graph sequencesThe Annals of Probability, 2010
- Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testingAdvances in Mathematics, 2008
- The phase transition in inhomogeneous random graphsRandom Structures & Algorithms, 2007
- Limits of dense graph sequencesJournal of Combinatorial Theory, Series B, 2006
- Complex Graphs and Networks2006
- General formalism for inhomogeneous random graphsPhysical Review E, 2002
- The longest edge of the random minimal spanning treeThe Annals of Applied Probability, 1997
- Random Plane NetworksJournal of the Society for Industrial and Applied Mathematics, 1961
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952