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}?
 A: 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}.
$$
A: 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.  
