# Probability distribution over cluster size in Erdős–Rényi random graph.

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

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.

• 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