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}?


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}. $$

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • 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 '13 at 13:10
  • $\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 '13 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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