4
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Jun 17, 2013 at 13:10
  • 1
    $\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
    Commented Jun 24, 2013 at 13:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .