4
$\begingroup$

My question is about the probability distribution over the possible size of the containing cluster of a randomly chosen node in an Erdős–Rényi random graph.

Let G(n,p) be an Erdős–Rényi random graph (with n nodes, and each edge included with probability p). Uniform-randomly select one of the n nodes from the graph. What is the probability of the node belonging to a cluster of size k, for k in {1,2,..,n}?

$\endgroup$

2 Answers 2

3
$\begingroup$

One can break up the probability that a specific vertex is in a component of size $k$ by $$ P(v \text{ is in a component of size }k) = {n-1 \choose k-1}P(k,p)q^{k(n-k)}, $$ where $P(k,p)$ is the probability that $G(k,p)$ is connected. However, now you would need to find $P(k,p)$, which is just as complicated. Often in random graphs, one only cares to bound this probability from above, such as an union bound over all spanning trees, $$ P(k,p) \leq k^{k-2} p^{k-1}, $$ or Stepanov's Inequality, $$ P(k,p) \leq (1-q^{k-1})^{k-1}. $$

$\endgroup$
-1
$\begingroup$

You should check any of:

  • Alon and Spencer 2008, "The Probabilistic Method"

  • Janson Et Al 2001, "Random Graphs"

  • Grimmett 2010 "Probability on Graphs"

  • Durrett 2007 "Random Graph Dynamics"

to cite only a few.

I believe the answer is essentially that dependent on $c$, where $p = \frac{c}{n}$:

  • when $c < 1$, all the connected components are of size $O(\log n)$

  • when $c > 1$, there exists a unique component of size $O(n)$, all other components are of size at most $O(\log n)$

  • when $c=1$, the components size have an amazing structure described by Aldous (1997) "Brownian Excursions, Critical Random Graphs and the Multiplicative Coalescent"

I hope this helps.

$\endgroup$
2
  • 2
    $\begingroup$ Thanks. It seems relatively easy to find results about the largest clusters, and about bounds on cluster size, but the actual distribution of cluster sizes seems to be hard to pin down! $\endgroup$
    – ts09
    Jun 17, 2013 at 13:10
  • 1
    $\begingroup$ I have had a brief look at some of those papers and it seems, that the answer isn't there, at least not in an easy to decipher form! I suppose in particular I would like to know, is there a closed form expression for calculating P(k), from n and p? $\endgroup$
    – ts09
    Jun 24, 2013 at 13:32

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.