Connectivity of Random Geometric Graphs understanding the derivation

63 Views Asked by At

In the paper "On the Connectivity of Dynamic Random Geometric Graphs" ( https://arxiv.org/pdf/cs/0702074.pdf ) the authors state that the expected value for a node being isolated is $$E[X]=N\cdot(1-\pi\cdot r^2)^{N-1}$$ with $N$ as the number of nodes and $r$ the radius in which two nodes are connected and nodes are distributed uniformly. The generation plane is wlog a square with edge length $1$. Now the paper reshapes the equation to $$E[X]=N\cdot(1-\pi\cdot r^2)^{N-1}=N\cdot e^{-\pi\cdot r^2\cdot N}-\mathcal{O}(r^4\cdot N)$$ I've been told that this follows some Taylor series expansion $$N\cdot(1-\pi\cdot r^2)^{N-1}=N\cdot(1-\pi\cdot r^2\cdot N+...)=N\cdot e^{-\pi\cdot r^2\cdot N}$$ Could somebody explain me in detail how this follows a taylor series expansion and where the $-\mathcal{O}(r^4\cdot N)$ come from in the paper. In general I know that there must be terms of the given size and smaller that have been omitted so the approximations result is about this amount larger than the expected result (since the $\mathcal{O}$ is negative).

Additionally they conclude in the paper that from the expected value giving the number of expected isolated nodes, they are able to derive the probability that the random geometric graph will have zero isolated nodes:

$$P[X=0]\approx e^{-N\cdot e^{-\pi\cdot r^2\cdot N}}$$

To understand the derivation of this result I also feel like I need a more detailed explanation.

@Paul Sinclair

$$(1+(-\pi r^2))^{N-1}=1-\pi r^2 N+\mathcal{O}(r^2+Nr^4)$$

considering that $r\in[0,1]$ mostly even in $r\in[0,0.12]$ and $N\in[50, 500]$ we can (maybe) assume $\mathcal{O}(Nr^4)$. Considering that most of the times $r\gtrapprox\sqrt{\frac{1}{N}}$.

Multiplied by $N$ it would give $N(1-\pi r^2 N)+\mathcal{O}(Nr^2+N^2r^4)$ with the $+$ being only one of many problems.

Since $(N+1)\cdot(1+(-\pi r^2))^N$ doesn't seem to change much. Even with some brave approximation like $(1-\pi r^2)^{N-1}\approx(1-\pi r^2)^N$ the problem you've mentioned still remains. I really don't get it (yet). I found that all of it based on some publications by Penrose but I am still trying to understand and untangle that part.

Bonus-Question: How can there be such bold, uncommented statements in a paper?