Connectivity of soft random geometric graphs

Research output: Contribution to journalArticlepeer-review

40 Citations (Scopus)
111 Downloads (Pure)

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^{-\eps}),$ some $\eps >0$. We generalize the first result to higher dimensions,and to a larger class of connection probability functions.
Original languageEnglish
Pages (from-to)986-1028
Number of pages43
JournalAnnals of Applied Probability
Volume26
Issue number2
DOIs
Publication statusPublished - Apr 2016

Keywords

  • Random graph
  • stochastic geometry
  • random connection model
  • connectivity
  • isolated points
  • continuum percolation

Fingerprint Dive into the research topics of 'Connectivity of soft random geometric graphs'. Together they form a unique fingerprint.

Cite this