10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Re: 1), see also arxiv.org/abs/1601.03714 $\endgroup$ – Steve Huntsman Feb 12 at 13:36
  • $\begingroup$ Re: 2), you may be interested in the Chung-Lu model, see, e.g. doi.org/10.1007/PL00012580 $\endgroup$ – Steve Huntsman Feb 12 at 13:43
  • 1
    $\begingroup$ @SteveHuntsman The Chung-Lu model is not quite the same kind of thing though because it is not for exact degrees, but expected ones. If I (numerically) generate a large graph from the Chung-Lu model with all expected degrees being 3, I get actual degrees between roughly 0 and 10, and in practice I always get a disconnected graph. If I generate random cubic graphs (exact degrees) by applying repeated random degree-preserving edge switches, in practice I always get a connected graph. $\endgroup$ – Szabolcs Horvát Feb 12 at 14:22
  • 1
    $\begingroup$ Consider a sequence of degree sequences $\boldsymbol{d}(n)=(d_1(n),d_2(n),\ldots,d_{n-1}(n))$. I believe that the probability of connectedness converges to 1 if $d_1(n) = o(\sqrt n)$ and $d_2(n)=o(n)$. I'm not giving this as an answer because I don't recall where it was studied, but I'm sure it has been. $\endgroup$ – Brendan McKay Apr 18 at 5:15
  • 2
    $\begingroup$ My understanding of the question, which is different from the understanding of all answers so far, is that we are given a degree sequence, then we must generate a graph uniformly at random from all graphs with that degree sequence. Is that correct? $\endgroup$ – Brendan McKay Apr 18 at 10:49
2
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ With the highest probability, to wit, $1 - o(1)$, the g. c. is unique; doesn't rank very high on my own scale. Just being pedantic, I know... couldn't resist. $\endgroup$ – François Jurain Apr 18 at 14:02
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Every edit bumps the post to the top of the stack. We're up to 28 now. Please avoid making tiny edits; make each edit really count. $\endgroup$ – Todd Trimble Apr 19 at 16:03
  • $\begingroup$ @Todd Trimble hadn't noticed; I'll see to it. $\endgroup$ – François Jurain Apr 19 at 22:15
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ There is an issue with exactly what the question is. It is certainly not true that for a fixed degree sequence without 0 a random graph with that degree sequence is probably connected. Consider if every degree is 1, or even if every degree is 2. $\endgroup$ – Brendan McKay Apr 18 at 10:46
  • $\begingroup$ If it has a fixed degree sequence, I think it is different to fixed degree distribution. The second case (fixed degree distribution) is the random graph which I think is probably connected without isolated nodes. Otherwise it is definitely not necessarily connected, even when built randomly, as you say. $\endgroup$ – apkg Apr 18 at 10:54
  • $\begingroup$ I will edit the answer to clarify what I mean by random graph. $\endgroup$ – apkg Apr 18 at 10:56
  • $\begingroup$ Isn't "all degree 1" a distribution? I don't know what you mean by with some degree distribution". Also, see OP's answer to SteveHuntsman. $\endgroup$ – Brendan McKay Apr 18 at 12:14
  • 1
    $\begingroup$ I clarified the question to note that it's about fixed degree sequences. BTW it took me a while to figure out who you are with the funky new username ;-) $\endgroup$ – Szabolcs Horvát Apr 18 at 13:56

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.