When is a large graph with a given degree sequence likely to be connected?

Question

Are there any results on whether a large random graph with a given degree distribution is likely to be connected?

In Erdős-Rényi graphs with $n$ vertices and $m$ edges, we have two sudden transitions (for large $n$):

1. A giant component appears above the threshold $m/n = 1/2$.
2. The graph becomes connected above the threshold $m/n = (\ln n)/2$.

There is a result analogous to (1) above by Molloy and Reed for random graphs with a given degree distribution. If $d$ denotes the vertex degree and $\langle \cdot \rangle$ denotes the average, then the quantity of interest is $Q = \langle d^2 \rangle - 2\langle d \rangle$. A giant component suddenly appears above the threshold $Q > 0$.

Question: Is there a result analogous to (2) for random graphs with a fixed degree sequence, in the large graph limit? Is there a quantity that can be computed from the degree distribution, and when it crosses a threshold, the graph suddenly becomes connected (in the $n\rightarrow\infty$ limit)? Let us assume that there are no isolated vertices ($d\ne 0$).

---

Clarification update: Let me try to give a more precisely specified version of the problem. Suppose we have $n$ vertices. Of these, precisely $n_d = f_d n$ have degree $d$: thus we have a degree sequence $$( \overbrace{0,\dots,0}^{\text{$n_0$ times}},\; \overbrace{1,\dots,1}^{\text{$n_1$ times}},\; \overbrace{2,\dots,2}^{\text{$n_2$ times}}, \dots). $$ Choose one simple (labelled) graph with this degree sequence uniformly at random.

What conditions do we need to have on the $f_d$ (the degree distribution), or on $n_d$, so that in the $n \rightarrow \infty$ limit the graph is connected with probability 1?

Clearly, if the $f_0 \ne 0$, then there are isolated vertices and the graph is not connected. Therefore, one condition is that $f_0 = 0$.

Answer 1

Second edition

This is a partial answer to the question per the "Clarification Update", but first I'll generalize a little. Suppose that for each $n$ we have a degree sequence $n_0,n_1,n_2,\ldots$, where $n_d=n_d(n)$ means the number of vertices of degree $d$. Also let the number of edges be $m=m(n)$ and the maximum degree be $\varDelta=\varDelta(n)$. Now we take a random simple graph $G=G(n)$ with this degree sequence, each such graph being equally likely. We seek to know if $G$ is connected. Take $n_0=0$ from now on.

This type of random graph has been extensively studied. I'll just make some simple observations using Theorem 2.1 of this paper.

By Theorem 2.1 the expected number of isolated edges is $$\binom{n_1}{2}\frac{1+O(\varDelta/m)}{2m}$$ if $\varDelta=o(m)$. Assuming the latter condition, the expected number of isolated edges goes to $0,\infty$ according as $n_1^2/m$ goes to $0,\infty$, respectively. This doesn't imply instantly that $n_1\approx \sqrt{m}$ is the threshold for having an isolated edge, but it is true (use the second moment method). So now assume $n_1=o(m)$.

I thought a combination of degrees 1 and 2 might be an issue, but the most likely isolated component, a path of two edges, is unlikely if $n_1=o(\sqrt m)$. (So, if these components are likely, so are isolated edges.)

Now consider isolated cycles. The expected number of isolated cycles of length $k$ is $$\frac{(n_2)_k(1+O(k\varDelta/m))}{2k\,(m)_k},$$ where $(x)_k=x(x-1)\cdots(x-k+1)$, provided $k\varDelta=o(m)$. Since $n_2\le m$, this never goes to infinity for fixed $k$, but the sum over an increasing number of $k$ values does go to infinity if $n_2=(1-o(1))m$. In the other direction, if $n_2=o(m)$ then the expectation goes to 0 for each $k$ and moreover the terms appear to be decreasing exponentially as $k$ increases. Here there is a gap in the proof because $k\varDelta=o(m)$ might not be true for very large $k$ unless also $\varDelta=O(1)$. This gap can be filled but I won't go into it. Modulo some things I haven't quite proved, the probability of connectedness goes to 1 if $n_2=o(m)$ and to 0 if $n_2=(1+o(1))m$. In the intermediate ranger, for example if $n_2=cm$ for $0\lt c\lt 1$, I believe that the distribution of the number of isolated cycles will be Poisson with constant mean.

Beyond this, I'm reluctant to reinvent the wheel because someone must have done this before except possibly in the case that some degrees are very low and others very high. There are no component types that are likely to occur under conditions when isolated edges or cycles are unlikely to occur. The fact that random regular graphs of degree at least 3 are almost always connected was proved by Wormald in the 1970s. I hypothesize that $n_0=0$, $n_1=o(\sqrt m)$ and $n_2\le cm$ for some $c\le 1$ are necessary and sufficient conditions for almost sure connectivity.

The question also asks us to consider the case that there constants $f_0,f_1,\ldots$ independent of $n$ such that $n_d(n)=f_d\,n$ for all $n,d$. Translating what is above, the condition for connectivity is $f_0=f_1=f_2=0$. Clearly forcing $f_d$ to be independent of $n$ loses a lot of detail.

Answer 2

I think for general random graphs with (very) high probability there cannot be two giant components. For the graph to be connected it should be enough to prove that no small cluster with just a handful of vertices appears.

Your condition $d\neq 0$ prevents all cluster of size 1.

For cluster of size $2$, we have to make sure that no pair of vertices with $d=1$ are connected. This lead to the condition $|\{i:d_i=1\}|<\sqrt{m}$ because $$\mathbb{P}(\exists i,j,d_i=d_j=1 \text{ and } (i,j)\text{ connected} )\leq \sum_{i,d_i=1}\sum_{j,d_j=1} \mathbb{P}((i,j)\text{ connected} ) = m^{-1}|\{i:d_i=1\}|^2$$ Considering a vertex with degree $d_i>1$ we have to make sure it doesn't belong to a small cluster. We do the exploration process visiting the connected vertex one after another and counting the degree. This creates a Galton Watson tree. We denote $X_k$ the number of outgoing edges from the set of visited vertex. $X_0=d_i$. Each time we visite a vertex $$X_{k+1}=X_n +d_{y_{k+1}}-2 $$ where $y_{k+1}$ is the visited vertex. We have a cluster of size $k$ if $X_k = 0$. $$X_{k+1}-X_k = \begin{cases}-1 & \text{ with probability } q = m^{-1}|\{i:d_i=1\}| \\ 0 &\text{ with probability }2 m^{-1}|\{i:d_i=2\}| \\ \geq 1 & \text{with probability larger than } p =m^{-1}|\{i:d_i>2\}| \end{cases}$$ For $p>q$ one can check that $N_n := \left(\frac{q}{p}\right)^{X_n} $ is a positive supermartingale and then that $$\mathbb{P}(X_k=0)=\mathbb{P}(N_k=1)\leq\mathbb{E}(N_k)\leq \mathbb{E}(N_0)=\left(\frac{q}{p}\right)^{d_i}\leq \left(\frac{q}{p}\right)^{2} $$ Therefore no small cluster appears if $\left(\frac{q}{p}\right)^{2}\leq n^{-1}$. To conclude, I claim that the graph is connected if

1-$$|\{i:d_i=1\}|<\sqrt{m}$$

2-$$\frac{|\{i:d_i=1\}|}{|\{i:d_i>2\}|}< n^{-1/2}$$

Remark: the second condition could be improved and probably be made optimal with a better estimate of $\mathbb{P}(X_k=0)$.

Answer 3

Revised Edition to converge to the OP's notations, and slightly augmented.

Let $f_d$ be the distribution of the degrees, and $gF(u)= \Sigma_{0 \le d} f_d u^d $ its generating function; then I think the indicator you seek is $f_1 \over gF'(1)$, with consideration of $f_2 \over gF'(1)$ if necessary.

Edited after reading Pr. McKay's comments & the OP's clarifications. Fist, choose some $N \gg 1$, $n_d$'s all $ \ge 0 $ adding up to $N$ for the number of nodes of degree $d \le N - 1 $, and let $f_d = n_d / N $, so that $\Sigma_{1 \le d \le N-1} f_d = 1$. Then, pick a simple graph (no loop, no duplicate edges) uniformly at random amongst all those having $n_d = f_d N$ nodes of degree $d$ for each $d$, the degree sequence.

Alternatively, you may want to choose the $f_d$'s, the degree distribution, before settling on a graph size; if so, relax the normalization to $gF(1) = 1 + o(1)$, then constrain $N$ by $\Sigma_{d \ge N-O(1)} f_d = o(1)$, choose $ n_d = f_d (N + O(1))$ for each $d \le N - 1$ and pick your random graph, of size $\Sigma_{1 \le d \le N-1} n_d = N + O(1)$.

By convention $gF(1) = 1$ and $f_0 = 0$. Assume further the Molloy-Reed criterion is met: $gF''(1)/gF'(1)$ is at least $ 1 + \Omega(1)$, else there will be no giant component to speak of. In particular $2 f_2$ is $(1 - \Omega(1)) gF'(1) $.

Consider 1st the case I'm familiar with, that $gF$ is a polynomial of degree $ O(1)$. Then things are mighty clear:

1. if $f_1 = 0$, then w. p. $1 - o(1)$, a node chosen at random amongst those of the chosen graph is in the giant component. I think it is even true that w. p. $1 - o(1)$, the chosen graph has only $O(1)$ nodes outside the g. c. On the other hand, the condition does not ensure exactly 1 c. c.:

   • (1.a) if $f_2 = \Omega(1)$, then a node chosen at random amongst those of degree 2 will belong w. p. $ \sim {1 \over N} {1 \over {gF'(1) - 2 f_2}}$ in a ring of length $O(1)$. Except I forbade multiple edges, so the ring must be of length $ \ge 3$ and the probability $ \sim {1 \over N} {{2 f_2} \over gF'(1) } {1 \over {gF'(1) - 2 f_2}}$ , so w. p. $ \sim 1 - e^{- {2 f_2 \over gF'(1)} {f_2 \over {gF'(1) - 2 f_2 }}} = \Omega(1)$, the chosen graph will contain $\ge 1$ such c. c.;

   • (1.b) if $f_2 = o(1)$, then it remains true that w. p. $\Omega( {({f_2 \over gF'(1)})}^2) = \Omega({f_2 \over gF'(1)})$, at least 1 c. c. of the chosen graph is a ring of size $O(1)$; whereas I think w. p. $1 - o(1)$, all nodes of degree $\ge 3$ are connected to the g. c.; thus, it is now the case that w. p. $1 - o(1)$, the graph coincides with the g. c.

2. If $f_1 = o(1) > 0$, then cutting all edges incident to leaves will not change $gF$ in any appreciable way, and the same conclusion applies as in the case $f_1 = 0$: w. p. $1 - o(1)$, a fraction $1 - o(1)$ of the nodes is in the g. c.

   • (2.a) if $f_2 = \Omega(1)$, then w. p. $\Omega(1)$, at least $\Omega(1)$ nodes are in other c. c.'s than the giant one; on the other hand, if $f_2 = o(1)$, then the graph is connected, right? Well, not so fast. A fraction $\sim gF(p) = o(1)$ of the nodes is still in trees of size $O(1)$, with $p \sim { f_1 \over {gF'(1) - 2 f_2}} $ the fixed point of ${1 \over gF'(1)} gF' $; so:
   • (2.b) if $f_2 = o(1)$ and $ gF(p) \sim {f_1}^2/gF'(1) \ge \Omega(1/N)$, then w. p. $\Omega(1)$ the graph is not connected; if $ {f_1}^2/gF'(1) \gg 1/N $, the number of stray nodes is even $ \gg 1 $;
   • (2.c) if $f_2 = o(1)$ and $ {f_1}^2/gF'(1) = \Omega(1/N)$ however, then w. p. $1 - o(1)$ only $O(1)$ nodes are in other components than the g. c.;
   • (2.d) if $f_2 = o(1)$ and $ {f_1}^2/gF'(1) = o(1/N)$, then w. p. $1 - o(1)$ the graph is connected.

3. If $f_1 = \Omega(1)$, then w. p. $\Omega(1)$, a node chosen at random is in a connected component of size $O(1)$; this c. c. will be a tree having $k = O(1)$ leaves with probability ${f_1}^k O(1)$. So, a fraction ${f_1 \over {gF'(1) - 2 f_2}} + O({f_1}^2) $ of the leaves will not be in the giant component; the main contribution $ f_1 \over {gF'(1) - 2 f_2} $ comes from the c. c.'s that are chains of length $O(1)$ with 2 leaves at their ends, and is $\Omega(f_1)$.

These conclusions extend to any $gF(u)$, even though $gF'(1)$ is not guaranteed to remain $O(1)$ as in the polynomial case: just consider $f_1 \over gF'(1)$ in stead of $f_1$ and $ f_2 \over gF'(1)$ in stead of $f_2$ when deciding in which of the 7 cases above your $gF$ stands.

To summarize:

• the giant component of the chosen graph contains almost every node w. p. $1 - o(1)$ iff $ {f_1 \over gF'(1) } = o(1)$. Else, w. p. $\Omega(1)$, a fraction $\Omega(1)$ of the nodes will be in components of size $O(1)$.

• moreover, the number of nodes disconnected from the giant component shrinks from $o(N)$ to $\Omega(1)$ w. p. $1 - o(1) $ iff $ { {f_1}^2 \over gF'(1) } = \Omega({1 \over N})$, equivalently, $ { f_1 \over gF'(1) } = \Omega({1 \over \sqrt{N gF'(1)}})$.

• The giant component contains each and every node w. p. $1 - o(1)$ iff, in addition, $ { f_2 \over gF'(1) } = o(1)$ and $ { {f_1}^2 \over gF'(1) } = o({1 \over N})$ ; equivalently, $ { f_1 \over gF'(1) } = o({1 \over \sqrt{N gF'(1)}})$. Else, w. p. $\Omega(1)$, the graph will also contain $ \ge 1$ component disconnected from the g. c.: rings of total size $O(1)$ if the condition on $f_2$ is not met, else $O(1)$ pairs of leaves.

Note that the average node degree is $ \sim gF'(1)$ and the number of edges is $ E \sim {1 \over 2} N gF'(1)$; so in stead of $ f_1 \over gF'(1)$ , you may want to compare $ n_1 \over E $ w. r. t. $ o(1)$ and $ \Omega(1/\sqrt E)$, and $ n_2 \over E $ rather than $ f_2 \over gF'(1) $ to $ o(1)$.

I think I'll let my keyboard cool down some, to Mr Trimble's satisfaction. Looks like I took great pains to reinvent the wheel; so much for not reading the classics.

Answer 4

If you assume, as you do, there are no isolated vertices with high probability, you most likely have connectivity with high probability.

It is an interesting question to ask what conditions on the graph lead to exceptions to this coincidence between connectivity and isolated vertices. A 1d RGG is an example.

If the graph (of $n$ nodes) is formed non-randomly, the only condition to ensure connectivity is that the number of edges in the graph is strictly less than ${n \choose 2} - (n-2)$, since then there is at least the possibility of an isolated node (otherwise, packing the edges into their ${n \choose 2}$ possible spaces means you have a complete graph $K_{n-1}$ and a straggler node, connected by at least one edge to the main body).

If the graph is formed randomly, with some degree distribution (not necessarily with a specific, fixed degree sequence), the lack of isolated nodes is sufficient for connectivity in most cases. This is true in the Erdos-Renyi graph, and in various random geometric graphs. There is most likely the same coincidence in random graphs with unusual degree distributions.

Two clusters of nodes eventually have a bridge unless you force them not to, particularly if a singleton cluster is required to connect to another cluster with probability one from the outset.