Giant component

Short description: Large connected component of a random graph

An Erdős–Rényi–Gilbert random graph with 1000 vertices at the critical edge probability [math]\displaystyle{ p=1/(n-1) }[/math], showing a large component and many small ones. At this edge probability, the large component is not yet a giant component: it contains only a sublinear number of vertices.

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 component in Erdős–Rényi model

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 [math]\displaystyle{ p \le \frac{1-\epsilon}{n} }[/math] for any constant [math]\displaystyle{ \epsilon\gt 0 }[/math], then with high probability (in the limit as [math]\displaystyle{ n }[/math] goes to infinity) all connected components of the graph have size O(log n), and there is no giant component. However, for [math]\displaystyle{ p \ge \frac{1 + \epsilon}{n} }[/math] there is with high probability a single giant component, with all other components having size O(log n). For [math]\displaystyle{ p=p_c = \frac{1}{n} }[/math], intermediate between these two possibilities, the number of vertices in the largest component of the graph, [math]\displaystyle{ P_{\inf} }[/math] is with high probability proportional to [math]\displaystyle{ n^{2/3} }[/math].

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

At [math]\displaystyle{ p_c }[/math], the distribution of cluster sizes behaves as a power law, [math]\displaystyle{ n(s) }[/math]~[math]\displaystyle{ s^{-5/2} }[/math] 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 [math]\displaystyle{ n/2 }[/math] 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 [math]\displaystyle{ n/2 }[/math], the size of the giant component is approximately [math]\displaystyle{ 4t-2n }[/math]. However, according to the coupon collector's problem, [math]\displaystyle{ \Theta(n\log n) }[/math] edges are needed in order to have high probability that the whole random graph is connected.

Graphs with arbitrary degree distributions

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. 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 has degree [math]\displaystyle{ k }[/math], then the giant component exists if and only if[math]\displaystyle{ \mathbb E [k^2] - 2 \mathbb E [k]\gt 0. }[/math][math]\displaystyle{ \mathbb E [k] }[/math] which is also written in the form of [math]\displaystyle{ {\langle k \rangle} }[/math] is the mean degree of the network. Similar expressions are also valid for directed graphs, in which case the degree distribution is two-dimensional. There are three types of connected components in directed graphs. For a randomly chosen vertex:

1. out-component is a set of vertices that can be reached by recursively following all out-edges forward;
2. in-component is a set of vertices that can be reached by recursively following all in-edges backward;
3. weak component is a set of vertices that can be reached by recursively following all edges regardless of their direction.

Criteria for giant component existence in directed and undirected configuration graphs

Let a randomly chosen vertex has [math]\displaystyle{ k_\text{in} }[/math] in-edges and [math]\displaystyle{ k_\text{out} }[/math] out edges. By definition, the average number of in- and out-edges coincides so that [math]\displaystyle{ c = \mathbb E [k_\text{in}] =\mathbb E [k_\text{out}] }[/math]. If [math]\displaystyle{ G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k }[/math] is the generating function of the degree distribution [math]\displaystyle{ P(k) }[/math] for an undirected network, then [math]\displaystyle{ G_1(x) }[/math] can be defined as [math]\displaystyle{ G_1(x) = \textstyle \sum_{k} \displaystyle \frac{k}{\langle k \rangle}P(k)x^{k-1} }[/math]. For directed networks, generating function assigned to the joint probability distribution [math]\displaystyle{ P(k_{in}, k_{out}) }[/math] can be written with two valuables [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] as: [math]\displaystyle{ \mathcal{G}(x,y) = \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}} }[/math], then one can define [math]\displaystyle{ g(x) = \frac{1}{c} {\partial \mathcal{G}\over\partial x}\vert _{y=1} }[/math] and [math]\displaystyle{ f(y) = \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1} }[/math]. The criteria for giant component existence in directed and undirected random graphs are given in the table below:

Type	Criteria
undirected: giant component	[math]\displaystyle{ \mathbb E [k^2] - 2 \mathbb E [k]\gt 0 }[/math], or [math]\displaystyle{ G'_1(1)=1 }[/math]
directed: giant in/out-component	[math]\displaystyle{ \mathbb E [k_\text{in}k_{out}] - \mathbb E [k_\text{in}]\gt 0 }[/math], or [math]\displaystyle{ g'_1(1)= f'_1(1) = 1 }[/math]
directed: giant weak component	[math]\displaystyle{ 2\mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{in}k_\text{out}] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{in}^2] +\mathbb{E}[k_\text{in}^2]\mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in} k_\text{out}]^2 \gt 0 }[/math]

See also

• Erdős–Rényi model
• Fractals
• Graph theory
• Interdependent networks
• Percolation theory
• Percolation
• Complex Networks
• Network Science
• Scale free networks