Random Geometric Graph

• Motivation: We want to capture spatial or geometric constraints in real-world networks over a given space
• Notation: $G(n,r)$
• Model: Fixed number of $n$ nodes uniformly sampled over a given metric space, e.g., $[0,1{]}^2$ with Euclidean distance, undirected, form an edge between two nodes if their distance is less than or equal to $r$
  • To avoid dealing with boundary effects, we can also use the toroidal distance: $\mathrm{dist}(x,y)={\min }_{z\in {\mathbb{Z}}^2}\Vert x_1-x_2+z\Vert$
• Phase transitions in terms of $r(n)$
  • Connectivity: $t(n)=\sqrt{\ln n/n}$
    • There exists $c_1>c_2>0$ such that the graph is connected if $r(n)\ge c_1\sqrt{\ln n/n}$ and disconnected if $r(n)\le c_2\sqrt{\ln n/n}$
  • Giant component: $r\approx \sqrt{\frac{1}{\pi n}}$ for $[0,1{]}^2$ with Euclidean distance

Poisson Point Process

A Poisson point process generalizes the Poisson Process to higher dimensions but enjoys similar properties. Specifically, a counting process $N:X\to \mathbb{N}$ on space $X$ is a (homogenous) Poisson point process if

1. for any disjoint sets $A_1,\dots ,A_k$, the r.v.s $N(A_1),\dots ,N(A_k)$ are independent, and
2. for any bounded and closed set $A$, $N(A)\sim \mathrm{Poisson}(\lambda |A|)$ for some $\lambda >0$ and $|A|$ is the volume of $A$.

Some properties of a Poisson Process also enjoyed by a Poisson point process:

• Conditioned on $N(A)=n$, the $n$ points in $A$ are i.i.d. uniformly distributed over $A$.

Analyzing a random geometric graph using a Poisson point process with parameter $\lambda =n$ is backed by the following theorem:

Tauberian

For any function that acts on $G(n,r)$ and is non-decreasing in $n$, let $f(N)$ be the corresponding random variable when $f$ is evaluated on nodes generated by a Poisson point process with intensity $\lambda =n$. Then, if $\mathbb{E}[f(N)]\asymp \Theta (n^{\alpha })$ for some $\alpha >0$, then $f(n)\asymp \Theta (n^{\alpha })$.

Connectivity

We evenly partition $[0,1{]}^2$ into $m^2$ squares. Then, a sufficient condition of connectivity is that each square has at least one node, and that of disconnectivity is that 8 squares around a center square are empty. For any square to have no node, the probability is $\exp (-n/m^2)$. Let $5/m^2=r(n{)}^2-ϵ$ for some $ϵ>0$. Then, the probability of the complement of the first event is bounded above by

$$m^2\exp (-n/m^2)\le \frac{5}{r^2-ϵ}\exp (-n(r^2-ϵ)/5).$$

Let $r=\sqrt{5a\ln n/n}$ for some $a\ge 1$. We get

$$m^2\exp (-n/m^2)\lesssim \frac{n^{1-a}}{a\ln n}\to 0.$$

Thus, $c_1=\sqrt{5.1}$ works for connectivity.

For disconnectivity, let $m=r(n{)}^{-1}$. Then, the probability of a square that has a node but all its 8 neighbors are empty is

$$p_0:=(1-\exp (-n/m^2))\exp (-8n/m^2).$$

Let $r=\sqrt{b\ln n/n}$ for some $b\in (0,1/8)$. We get

$$p_0=(1-n^{-b})(n^{-8b})\gtrsim n^{-8b}.$$

Then, the number of such squares is lower bounded by

$$\frac{m^2}{9}{p}_0\gtrsim \frac{n^{1-8b}}{9b\ln n}\to \infty .$$

Since the number of such squares follows a Binomial Distribution, its variance is smaller than its mean. Then, by the Moment Method, we have the probability of having at least one such square, and thus the probability of disconnectivity, approaches 1. Thus, $c_2=\sqrt{0.1}$ works for disconnectivity.