16
$\begingroup$

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value? I'm specially interested in what happens for small values of p, before the giant component emerges.

$\endgroup$
  • 6
    $\begingroup$ Your questions might be answered here or here. $\endgroup$ – Johannes Trost Jun 18 '14 at 14:18
  • $\begingroup$ IIRC, there is an answer in N.Alon & J.Spenser "The Probabilistic Method". $\endgroup$ – Dima Pasechnik Jun 18 '14 at 19:59
7
$\begingroup$

Have a look at Chapter 11 of Alon and Spencer's The Probabilistic Method. They focus entirely on the case $p = \Theta(1/n)$, and the smallest p they consider is of the form $c/n$, which perhaps counts as "small p" as in your question. In 11.6, they study the smallest case $c < 1$ in detail (they refer to this case as Very Subcritical). The results are always asymptotic as $n\to \infty$. They prove that the size of a component is modeled well by a Poisson Branching Process, so 11.4.2 gives you the probability distribution of sizes of components. Now it's a simple exercise to find the expected number of components: do a branching process to fill up the first component, then do one for the second, etc. until you run out of vertices. Write down how many components you ended up with.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

See Mathew Kahle and Elizabeth Meckes "Limit theorems for Betti numbers of random simplicial complexes"

They say that the distribution is Gaussian in $G(n,p)$ with $n \to \infty$, but only state the theorem for first homology or higher i.e. not for connected components. Nevertheless, the number of components converges via a central limit theorem to the normal distribution.

In fact, asymptotically almost all nodes are isolated when $np \to 0$ as $n \to \infty$.

With $np \to c$ with $0 < c < 1$, we have normal isolated nodes, normal 2-cliques, and so on. Though they intersect, this is vanishingly small as $n \to \infty$, so the branching processes are asymptotically independent. How many branching processes survive until exactly displaying cardinality 2 (i.e. one child)? Then count three, four etc. All normal, but expectation and variance need to be calculated. See the comments to the OP.

When critical, also normal. When there is a giant component, as long as $n$ is large, then the expected number of e.g. isolated vertices is large, so asymptotically normal. All we need is an asymptotically infinite number of connected components I think. See the proof in that paper.

If, for example, $np = c \log(n)$ with $c>1$, then the number of components is the number of isolated nodes plus one for the giant component itself. This is because each node has binomial degree with expectation $np$, and in the limit is isolated with probability $e^{-np}$. So coin toss for each node i.e. take $n$ chances of being isolated with this probability, giving $\mathbb{E}I_{0} = n e^{-np}$.

When the graph is a.a.s. connected, there is only one component. But this is just normal, with zero variance and unit mean. In fact, all the Betti numbers of the corresponding random clique complex are normal. The main theorems in that paper give the normality, and formulas for the expectation.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

In case this isn't obvious, a simple insight used in many papers is that for small p, the network is (whp) simply a random tree, which allows for simple estimates of these and many other properties.

Added in response to comments: oops, I should have said "tree-like" and one can use "tree counting" techniques to analyze the structure of the connected components. This is discussed in the classic paper by Newman, Strogatz and Watts -- http://arxiv.org/pdf/cond-mat/0007235v2.pdf

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It's a good start to an answer, but please consider fleshing it out more. $\endgroup$ – Todd Trimble Jan 31 '16 at 23:51
  • 1
    $\begingroup$ s/tree/forest. Also, for $p<\frac{1}{n}$ before the giant component appears, you are likely to see a small number of cyclic components. $\endgroup$ – David Eppstein Feb 1 '16 at 0:26
  • $\begingroup$ A very small number of cycles if p=a/n for a<1. For example, the expected number of 3-cycles is approximately $a^3/6$ as n-->\infty. The expected number of all cycles is a function of a independent of n in this limit, so irrelevant for counting arguments. $\endgroup$ – ericf Mar 15 '16 at 4:05
1
$\begingroup$

For $p= \frac c N$, the mean number of components per node is $(1-s_0) (1- \frac c 2 (1-s_0))$, where $s_0$ is the fraction of nodes in the largest component. (So, trivially, in the non-percolating phase for $c<1$, where $s_0=0$, one obtains $1- \frac c 2$, which corresponds to the simple argument to having $N$ nodes and $M=\frac {N(N-1)} 2 \frac c N= \frac {c(N-1)} 2$ about $\frac {cN} 2$ edges, i.e. in the loop-less case, about $N-M=N(1- \frac c 2)$ components).

The result, including the full distribution, also in the percolating phase, can be found (obtained by statistical mechanics methods and simulations) in J. Stat. Phys. 117, 387 (2004), see also https://arxiv.org/abs/cond-mat/0311535.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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