Probability that there is an edge between two nodes in a random geometric graph

865 Views Asked by At

I am new to Random geometric graphs. I have a graph with vertices being generated uniformly over $[0,1]^2$. There is an edge between two vertices if the Euclidean distance between the two vertices is $\le r$. I am trying to find the probability of this. For that I am starting as below: $$P(\mbox{two random nodes have an edge between them})=P((x_i-x_j)^2+(y_i-y_j)^2\le r^2)$$ I am taking the nodes to be uniformly and independently generated over $[0,1]^2$, hence $p(x_i)=p(x_j)=p(y_i)=p(y_j)=1$ and they are all independent. Using these and after some calculations I found that the probability is $r^4$. But I could not get any reference where I can verify this result and I have a feeling that I am wrong. So, can anyone kindly comment on this result and please help correct it if it is wrong? Thanks in advance.

EDIT: The following is my calculations that led to the result $r^4$. Please suggest corrections if something is wrong.

$$P((x_i-x_j)^2+(y_i-y_j)^2\le r^2)\\ =\int\int\int P((x_i-x_j)^2+(y_i-y_j)^2\le r^2|x_i,y_i,x_j)p_{x_i,y_i,x_j}(x_i,y_i,x_j)dx_idy_idx_j\\ =\int_{|x_i-x_j|\le r}\int_{|y_i-y_j|\le \sqrt{r^2-(x_i-x_j)^2}}dx_i dx_j dy_i dy_j$$ Now using the transformations $X=x_i-x_j,\ Y=y_i-y_j$, I rewrote the integral as $$\frac{}{}\int_{-r}^{r}\int_{\sqrt{r^2-X^2}}^{\sqrt{r^2-X^2}}XY dY dX=r^4$$

Note: I do not want the probability that a particular node has an edge with some other node which is easily seen to be $\pi r^2$.

1

There are 1 best solutions below

0
On

After some hesitations, it seems that one is actually throwing two points uniformly and independently in $[0,1]^2$ and that one asks for the probability $p(r)$ that their distance is at most $r$. Thus, $$ p(r)=\iint_{[0,1]^2}A(x,r)\,\mathrm dx, $$ where $A(x,r)$ is the area of the set $$ [0,1]^2\cap D(x,r), $$ where $D(x,r)$ is the full disk $$ D(x,r)=\{y\in\mathbb R^2\mid\|y-x\|\leqslant r\}. $$ The computation of the exact value of $p(r)$ is tedious (except when $r\geqslant\sqrt2$ since then $p(r)=1$) but one can note that, for every $r\leqslant1$, the set $[0,1]^2\cap D(x,r)$ is at most $D(x,r)$, whose area is $\pi r^2$, and at least a quarter of $D(x,r)$. Thus, $$ \tfrac14\pi r^2\leqslant p(r)\leqslant\pi r^2. $$ Recall that this holds only for $$ 0\lt r\leqslant1. $$