1
$\begingroup$

I would be really glad if someone could help me with the following problem:

Let us consider a circular environment with $R=1$ and $n$ points uniformly distributed within the circle's area.

All these vertices are assigned a range (think of sensors being capable of transmitting data wirelessly from one to another) $d$ (fixed and equal for all vertices).

For running simulations, I would like to find a minimum $n$ that with high probability (say $0.99$) ensures, that the resulting graph consists of just one single connected component.

First, I somehow tried to reduce the problem to computing the expectation of pairwise distances, however soon enough realized that this is not easily applicable since smaller components might very well contain more than just one vertex.

Could anyone provide pointers or tell me how one would solve this problem? Sorry if I messed up any of the terminology, my stats is quite rusty.

Improve this question
$\endgroup$
1
  • $\begingroup$ This question appears to come out of an unstated context in which so much is taken for granted that in its present location it is incomprehensible. Is $R$ perhaps a radius? Is a "circle" the one-dimensional boundary of a disk or the entire disk? Is a "range" a distance or an interval of angles? What is the "resulting graph"? What is a "component"? Although readers can make reasonable guesses about these, we cannot suppose everyone will guess the same. Therefore, please edit this question to provide the particulars needed to make it answerable. $\endgroup$
    – whuber ♦
    Commented Nov 13, 2013 at 16:14

1 Answer 1

Reset to default
2
$\begingroup$

The number of connected components won't just depend on n, but d as well (if that's something can be varied).

Anyway, your best bet is probably to generate a large number of random graphs using the same parameter n (and d) and use this to estimate the probability of getting a single connected component for that n. Vary the magnitude of n and repeat the process for several n. After doing this for several n, you should be able to build a regression model (or otherwise fit a curve through your data) to estimate the probability of getting a single connected component for any given n.

Improve this answer
$\endgroup$
2
  • $\begingroup$ $d$ is supposed to be fixed. The idea with the regression model sounds tempting, but if there was an analytical way of solving this, that would be even more awesome :) $\endgroup$
    – limbonic
    Commented Nov 13, 2013 at 2:48
  • 1
    $\begingroup$ There's almost certainly an analytic solution here. You might have better luck over at the math stackexchange. Those folks probably have more collective experience with graph theory than us stats folk. $\endgroup$
    – David Marx
    Commented Nov 13, 2013 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.