Giant component

In network theory, a giant component is a connected component of a given random graph that contains a constant fraction of the entire graph's vertices.

Giant component in Erdős–Rényi model

Giant components are a prominent feature of the Erdős–Rényi model of random graphs, in which each possible edge connecting pairs of a given set of n vertices is present, independently of the other edges, with probability p. In this model, if $p \le \frac{1-\epsilon}{n}$ for any constant $\epsilon >0$, then with high probability all connected components of the graph have size O(log n), and there is no giant component. However, for $p \ge \frac{1 + \epsilon}{n}$ there is with high probability a single giant component, with all other components having size O(log n). For $p={\frac {1}{n}}$, intermediate between these two possibilities, the number of vertices in the largest component of the graph is with high probability proportional to $n^{2/3}$.^[1]

Alternatively, if one adds randomly selected edges one at a time, starting with an empty graph, then it is not until approximately $n/2$ edges have been added that the graph contains a large component, and soon after that the component becomes giant. More precisely, when $t$ edges have been added, for values of $t$ close to but larger than $n/2$, the size of the giant component is approximately $4t-2n$.^[1] However, according to the coupon collector's problem, $\Theta (n\log n)$ edges are needed in order to have high probability that the whole random graph is connected.

Graphs with arbitrary degree distribution

A similar sharp threshold between parameters that lead to graphs with all components small and parameters that lead to a giant component also occurs in random graphs with non-uniform degree distributions. The degree distribution does not define a graph uniquely. However under assumption that in all respects other than their degree distribution, the graphs are treated as entirely random, many results on finite/infinite-component sizes are known. It is enough to know only first few moments of the degree distribution to answer if a giant component is present in the graph. In undirected graphs the existence of the giant component is defined by the first and second moments,^[2] i.e. the giant component exists if and only if ${\displaystyle \mu _{2}-2\mu _{1}>0}$, where ${\displaystyle \mu _{i}=\sum _{k}k^{i}d(k)}$ and $d(k)$ is the degree distribution. Similar expression are also known for directed graphs, in which case the degree distribution becomes two-dimensional. In directed graphs, three types of connected components are defined. For a selected vertex: (a) out-component is a set of vertices that can be reached by recursively following all out-edges forward; (b)in-component is a set of vertices that can be reached by recursively following all in-edges backward; and (c) weak component is a set of vertices that can be reached by recursively following all edges regardless of their orientation.^[3] Let ${\displaystyle \mu _{ij}=\sum _{n,k}n^{i}k^{j}d(n,k)}$ denote partial moments of the two-dimensional degree distribution, the criteria for existence of giant connected components of these types are given in the table.

Existence criteria for various types of giant components in directed and undirected graphs as a function of degree-distribution moments.

Type	Criteria	Reference
undirected graphs: giant component	${\displaystyle \mu _{2}-2\mu _{1}>0}$	[2]
directed graphs: giant in-component, giant out-component	${\displaystyle \mu _{11}-\mu >0}$	[4]
directed graphs: giant weak component	${\displaystyle 2\mu \mu _{11}-\mu \mu _{02}-\mu \mu _{20}+\mu _{02}\mu _{20}-\mu _{11}^{2}>0}$	[3]

References

1. Bollobás, Béla (2001), "6. The Evolution of Random Graphs—The Giant Component", Random Graphs, Cambridge studies in advanced mathematics, 73 (2nd ed.), Cambridge University Press, pp. 130–159, ISBN 978-0-521-79722-1.
2. M. Molloy and B. Reed (1995). "A critical point for random graphs with a given degree sequence". "Random Struct. Algorithms" 6, 161
3. I. Kryven (2016). "Emergence of the giant weak component in directed random graphs with arbitrary degree distributions" Phys. Rev. E 94, 012315
4. M. E. J. Newman, S. H. Strogatz, and D. J. Watts (2001). "Random graphs with arbitrary degree distributions and their applications". Phys. Rev. E 64, 026118