Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
1  
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
add comment

Your Answer

 
discard

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.