Average degree of vertex at least distance r from boundary of a random geometric graph?

151 Views Asked by At

Given a random geometric graph $G(n, r)$, how can you estimate the average degree of a vertex that is at least distance $r$ from the boundary?

Note: I'm not asking for a simple expression, rather, how to think about and solve such a problem a step at a time.

1

There are 1 best solutions below

4
On BEST ANSWER

This sort of problem can be solved using the linearity of expectation. The average degree can be not only estimated but given exactly.

I interpret your notation to mean that $n$ vertices are independently uniformly distributed in the unit square and two vertices are joined by an edge if their distance is $\le r$. Then a given vertex $v$ at least distance $r$ from the boundary shares an edge with another vertex if that vertex lies in a circle of radius $r$ around $v$. The probability for this is $\pi r^2$. Thus by linearity of expectation the expected number of vertices that share an edge with $v$ is $(n-1)\pi r^2$.