Connectivity of soft random geometric graphs

DOI10.1214/15-AAP1110MaRDI QIDQ292916zbMATHOpenAlexWikidataFDO

Authors Mathew D. Penrose

Publication date 9 June 2016

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

random graphconnectivitycontinuum percolationstochastic geometryisolated pointsrandom connection model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Connectivity (05C40)

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 $noinfty$ 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^{-varepsilon})$, some $varepsilon>0$. We generalize the first result to higher dimensions and to a larger class of connection probability functions.

Recommendations

• scientific article; zbMATH DE number 1340281
• Connectivity of random k-nearest-neighbour graphs
• The distribution of the number of isolated nodes in the 1-dimensional soft random geometric graph
• The random connection model: Connectivity, edge lengths, and degree distributions
• The connectivity of a graph on uniform points on [0,\,1]\(^{d}\).

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1254188 (Why is no real title available?)
• scientific article; zbMATH DE number 1340281 (Why is no real title available?)
• ASYMPTOTIC DISTRIBUTION OF THE NUMBER OF ISOLATED NODES IN WIRELESS AD HOC NETWORKS WITH UNRELIABLE NODES AND LINKS
• Connectivity threshold of Bluetooth graphs
• Continuum Percolation
• Full connectivity: corners, edges and faces
• Fundamentals of Wireless Communication
• Hamilton cycles in random geometric graphs
• On a continuum percolation model
• Performance of the Eschenauer–Gligor Key Distribution Scheme Under an ON/OFF Channel
• Random Geometric Graphs
• Random graphs.
• The capacity of wireless networks
• The longest edge of the random minimal spanning tree

Cited in

(43)

• Higher-order spectral clustering for geometric graphs
• Random geometric graph: some recent developments and perspectives
• Recurrence versus transience for weight-dependent random connection models
• The longest edge of the one-dimensional soft random geometric graph with boundaries
• Poisson approximation and connectivity in a scale-free random connection model
• Phase transition in noisy high-dimensional random geometric graphs
• Random walk on the random connection model
• Annulus graphs in \(\mathbb{R}^d\)
• Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier
• Asymptotic analysis of \(k\)-hop connectivity in the 1D unit disk random graph model
• Connectivity of soft random geometric graphs over annuli
• The acquaintance time of (percolated) random geometric graphs
• The random connection model and functions of edge-marked Poisson processes: second order properties and normal approximation
• Connectivity for line-of-sight networks in higher dimensions
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• The connectivity of a graph on uniform points on [0,\,1]\(^{d}\).
• Zero-one law for connectivity in superposition of random key graphs on random geometric graphs
• Connectivity of random geometric graphs related to minimal spanning forests
• Minimum spanning trees of random geometric graphs with location dependent weights
• Continuum AB percolation and AB random geometric graphs
• Full connectivity: corners, edges and faces
• Random Geometric Graphs
• Connectivity of random high dimensional geometric graphs
• On random points in the unit disk
• One-dimensional geometric random graphs with nonvanishing densities. II: A very strong zero-one law for connectivity
• The emergence of a giant component in one-dimensional inhomogeneous networks with long-range effects
• Nonuniform random geometric graphs with location-dependent radii
• Sunflower hard disk graphs
• Geometric random intersection graphs with general connection probabilities
• A probabilistic view of latent space graphs and phase transitions
• A research on connectivity in communication networks
• The connectivity threshold of random geometric graphs with Cantor distributed vertices
• scientific article; zbMATH DE number 7650120 (Why is no real title available?)
• The distribution of the number of isolated nodes in the 1-dimensional soft random geometric graph
• On the distances within cliques in a soft random geometric graph
• Two-point concentration in random geometric graphs
• Sharp threshold for embedding balanced spanning trees in random geometric graphs
• Inhomogeneous random graphs, isolated vertices, and Poisson approximation
• Isolation and connectivity in random geometric graphs with self-similar intensity measures
• Phase transition in a stochastic geometry model with applications to statistical mechanics
• Transience versus recurrence for scale-free spatial networks
• Hyperbolic graph generator
• Giant component of the soft random geometric graph

This page was built for publication: Connectivity of soft random geometric graphs

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