Connectivity of soft random geometric graphs

DOI10.1214/15-AAP1110zbMATH Open1339.05369arXiv1311.3897OpenAlexW3099777322WikidataQ56533596 ScholiaQ56533596MaRDI QIDQ292916FDOQ292916

Authors: Mathew D. Penrose 

Publication date: 9 June 2016

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

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.

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

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}\).

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)

Cites Work

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

Cited In (43)

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