Connectivity of soft random geometric graphs

Abstract

Consider a graph on $n$ uniform random points in the unit square, each pair being connected by an edge with probability $p$ if the inter-point distance is at most $r$. We show that as $n\to \infty$ the probability of full connectivity is governed by that of having no isolated vertices, itself governed by a Poisson approximation for the number of isolated vertices, uniformly over all choices of $p,r$. We determine the asymptotic probability of connectivity for all $(p_n,r_n)$ subject to $r_n=O(n^{-\epsilon })$, some $\epsilon >0$. We generalize the first result to higher dimensions and to a larger class of connection probability functions.

Published at http://dx.doi.org/10.1214/15-AAP1110 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (32)

• Clustering implies geometry in networks
• Statistical properties of the quantum internet
• Graphon Signal Processing
• Topological data analysis of continuum percolation with disks
• On resilience and connectivity of secure wireless sensor networks under node capture attacks
• Small worlds and clustering in spatial networks
• Recurrence versus Transience for Weight-Dependent Random Connection Models
• Topological versus spectral properties of random geometric graphs
• The shape of shortest paths in random spatial networks
• Entropy of Spatial Network Ensembles
• Connectivity in One-Dimensional Soft Random Geometric Graphs
• Random geometric graphs in high dimension
• Limit theory of isolated and extreme points in hyperbolic random geometric graphs
• Spatial networks with wireless applications
• Dynamic Hidden-Variable Network Models
• Higher-Order Spectral Clustering for Geometric Graphs
• Probabilistic key predistribution in mobile networks resilient to node-capture attacks
• On secure communication in sensor networks under q-composite key predistribution with unreliable links
• Isolation probabilities in dynamic soft random geometric graphs
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes
• Isolation and connectivity in random geometric graphs with self-similar intensity measures
• The random walk on the random connection model
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• The Distribution of the Number of Isolated Nodes in the 1-Dimensional Soft Random Geometric Graph
• Finiteness of the percolation threshold for inhomogeneous long-range models in one dimension
• The longest edge of the one-dimensional soft random geometric graph with boundaries
• Temporal connectivity in finite networks with non-uniform measures
• Poisson Approximation and Connectivity in a Scale-free Random Connection Model
• On the distances within cliques in a soft random geometric graph
• Large algebraic connectivity fluctuations in spatial network ensembles imply a predictive advantage from node location information
• Entropy of Random Geometric Graphs in High and Low Dimensions
• Graphlets in multilayer networks