What is the expected size of the largest strongly connected component of a graph?

Question

Given a directed graph with n vertices and the probability of any edge existing being p, what is the size of the largest strongly connected component in the graph? What if its undirected graph? Can we also estimate the number of components too in terms of n and p?

Answer 1

Much is known about the behavior of the (undirected) random graph $G(n, p)$ in the Erdős–Rényi model, including the following:

$\langle$Begin quote$\rangle$

• If $np < 1$, then a graph in $G(n, p)$ will almost surely have no connected components of size larger than $O(\log(n))$.

• If $np = 1$, then a graph in $G(n, p)$ will almost surely have a largest component whose size is of order $n^{2/3}$.

• If $np → c > 1$, where $c$ is a constant, then a graph in $G(n, p)$ will almost surely have a unique giant component containing a positive fraction of the vertices. No other component will contain more than $O(\log(n))$ vertices.

• If $p<\tfrac{(1-\epsilon)\ln n}{n}$, then a graph in $G(n, p)$ will almost surely contain isolated vertices, and thus be disconnected.

• If $p>\tfrac{(1+\epsilon) \ln n}{n}$, then a graph in $G(n, p)$ will almost surely be connected.

• Thus $\tfrac{\ln n}{n}$ is a sharp threshold for the connectedness of $G(n, p)$.

$\langle$End quote$\rangle$

The directed case is studied here.

Answer 2

The random directed graph on $n$ vertices, where each potential arc is present with probability $p$ independent of any other arc is typically denoted by $D(n,p)$. As Did's link mentions, $p=\ln n/n$ is a sharp threshold for strong connectedness. The following results deal with sparse random digraphs.

A $complex$ strong component is a strong component with more arcs than vertices. In other words, a complex strong component is a strong component that is neither a single vertex or a cycle.

Karp (1990, "The transitive closure of a random digraph") and Luczak (1990, "The phase transition in the evolution of random digraphs") proved that for any $\omega(n)$ tending to $\infty$, with probability tending to 1,

1) each strong component of $D(n,p=c/n), c<1$ has size less than $\omega$ and there are no complex strong components.

2) there is an unique complex strong component in $D(n,p=c/n),c>1$ which is of size on the order of $n$, and each other strong component has size less than $\omega$.

As opposed to undirected random graphs, this $\omega$ can tend to $\infty$ however slowly!

The behavior of $D(n,p=1/n)$ has been difficult to establish. As far as I know, the most up to date information, proved by Luczak and Seierstad (2009, "The Critical Behavior of Random Digraphs"), is that there is some $a,b \in (0,1)$ such that for $n$ large enough

$$P(\text{there exists a complex component in }D(n,p=1/n)) \in [a,b]$$

In the same paper, they show analogous results to 1) and 2) above for $c$ tending to 1, but $n^{1/3}|c-1| \to \infty$.