Giant component

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

More precisely, in graphs drawn randomly from a probability distribution over arbitrarily large graphs, a giant component is a connected component whose fraction of the overall number of vertices is bounded away from zero. In sufficiently dense graphs distributed according to the Erdős–Rényi model, a giant component exists with high probability.

Giant components are a prominent feature of the Erdős–Rényi model (ER) 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 ${\displaystyle p\leq {\frac {1-\epsilon }{n}}}$ for any constant ${\displaystyle \epsilon >0}$, then with high probability (in the limit as ${\displaystyle n}$ goes to infinity) all connected components of the graph have size O(log n), and there is no giant component. However, for ${\displaystyle p\geq {\frac {1+\epsilon }{n}}}$ there is with high probability a single giant component, with all other components having size O(log n). For ${\displaystyle p=p_{c}={\frac {1}{n}}}$, intermediate between these two possibilities, the number of vertices in the largest component of the graph, ${\displaystyle P_{\inf }}$ is with high probability proportional to ${\displaystyle n^{2/3}}$.

Giant component is also important in percolation theory. When a fraction of nodes, ${\displaystyle q=1-p}$, is removed randomly from an ER network of degree ${\displaystyle \langle k\rangle }$, there exists a critical threshold, ${\displaystyle p_{c}={\frac {1}{\langle k\rangle }}}$. Above ${\displaystyle p_{c}}$ there exists a giant component (largest cluster) of size, ${\displaystyle P_{\inf }}$. ${\displaystyle P_{\inf }}$ fulfills, ${\displaystyle P_{\inf }=p(1-\exp(-\langle k\rangle P_{\inf }))}$. For ${\displaystyle p<p_{c}}$ the solution of this equation is ${\displaystyle P_{\inf }=0}$, i.e., there is no giant component.

At ${\displaystyle p_{c}}$, the distribution of cluster sizes behaves as a power law, ${\displaystyle n(s)}$~${\displaystyle s^{-5/2}}$ which is a feature of phase transition.

Alternatively, if one adds randomly selected edges one at a time, starting with an empty graph, then it is not until approximately ${\displaystyle 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 ${\displaystyle n/2}$, the size of the giant component is approximately ${\displaystyle 4t-2n}$. However, according to the coupon collector's problem, ${\displaystyle \Theta (n\log n)}$ edges are needed in order to have high probability that the whole random graph is connected.

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 tree-like random graphs with non-uniform degree distributions ${\displaystyle P(k)}$. The degree distribution does not define a graph uniquely. However, under the 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. In this model, the existence of the giant component depends only on the first two (mixed) moments of the degree distribution. Let a randomly chosen vertex have degree ${\displaystyle k}$, then the giant component exists if and only if$${\displaystyle \langle k^{2}\rangle -2\langle k\rangle >0.}$$This is known as the Molloy and Reed condition. The first moment of ${\displaystyle P(k)}$ is the mean degree of the network. In general, the ${\displaystyle n}$-th moment is defined as ${\displaystyle \langle k^{n}\rangle =\mathbb {E} [k^{n}]=\sum k^{n}P(k)}$.

When there is no giant component, the expected size of the small component can also be determined by the first and second moments and it is ${\displaystyle 1+{\frac {\langle k\rangle ^{2}}{2\langle k\rangle +\langle k^{2}\rangle }}.}$ However, when there is a giant component, the size of the giant component is more tricky to evaluate.