MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

share|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.

share|cite|improve this answer
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! – ts09 Jun 17 '13 at 13:10
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? – ts09 Jun 24 '13 at 13:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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