thumb|upright=1.35|An [[Erdős–Rényi model|Erdős–Rényi–Gilbert random graph with 1000 vertices at the critical edge probability <math>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 vertices is present, independently of the other edges, with probability . In this model, if <math>p \le \frac{1-\epsilon}{n}</math> for any constant <math>\epsilon>0</math>, then with high probability (in the limit as <math>n</math> goes to infinity) all connected components of the graph have size , and there is no giant component. However, for <math>p \ge \frac{1 + \epsilon}{n}</math> there is with high probability a single giant component, with all other components having size . For <math>p=p_c = \frac{1}{n}</math>, intermediate between these two possibilities, the number of vertices in the largest component of the graph, <math>P_{\inf}</math> is with high probability proportional to <math>n^{2/3}</math>.
Giant component is also important in percolation theory. When a fraction of nodes, <math>q=1-p</math>, is removed randomly from an ER network of degree <math>\langle k \rangle</math>, there exists a critical threshold, <math>p_c= \frac{1}{\langle k \rangle}</math>. Above <math>p_c</math> there exists a giant component (largest cluster) of size, <math>P_{\inf}</math>. <math>P_{\inf}</math> fulfills, <math>P_{\inf}=p(1-\exp(-\langle k \rangle P_{\inf}))</math>. For <math>p<p_c</math> the solution of this equation is <math>P_{\inf}=0</math>, i.e., there is no giant component.
At <math>p_c</math>, the distribution of cluster sizes behaves as a power law, <math>n(s)</math>~<math>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>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 edges have been added, for values of close to but larger than <math>n/2</math>, the size of the giant component is approximately <math>4t-2n</math>. if and only if<math display="block">\langle k^2 \rangle - 2 \langle k \rangle>0.</math>This is known as the Molloy and Reed condition. The first moment of <math>P(k)</math> is the mean degree of the network. In general, the <math>n</math>-th moment is defined as <math>\langle k^n \rangle = \mathbb E [k^n] = \sum k^n P(k)</math>.
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 <math>1+\frac{\langle k \rangle ^2}{2\langle k \rangle + \langle k^2 \rangle}.</math> However, when there is a giant component, the size of the giant component is more tricky to evaluate. or <math>g'_1(1)= f'_1(1) = 1</math>
|-
|+
|}