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 p ≤ 1 − ϵ n {\displaystyle p\leq {\frac {1-\epsilon }{n}}} for any constant ϵ > 0 {\displaystyle \epsilon >0} , then with high probability (in the limit as n {\displaystyle n} goes to infinity) all connected components of the graph have size O(log n), and there is no giant component. However, for p ≥ 1 + ϵ n {\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 p = p c = 1 n {\displaystyle p=p_{c}={\frac {1}{n}}} , intermediate between these two possibilities, the number of vertices in the largest component of the graph, P inf {\displaystyle P_{\inf }} is with high probability proportional to n 2 / 3 {\displaystyle n^{2/3}} . Giant component is also important in percolation theory. When a fraction of nodes, q = 1 − p {\displaystyle q=1-p} , is removed randomly from an ER network of degree ⟨ k ⟩ {\displaystyle \langle k\rangle } , there exists a critical threshold, p c = 1 ⟨ k ⟩ {\displaystyle p_{c}={\frac {1}{\langle k\rangle }}} . Above p c {\displaystyle p_{c}} there exists a giant component (largest cluster) of size, P inf {\displaystyle P_{\inf }} . P inf {\displaystyle P_{\inf }} fulfills, P inf = p ( 1 − exp ( − ⟨ k ⟩ P inf ) ) {\displaystyle P_{\inf }=p(1-\exp(-\langle k\rangle P_{\inf }))} . For p < p c {\displaystyle p<p_{c}} the solution of this equation is P inf = 0 {\displaystyle P_{\inf }=0} , i.e., there is no giant component. At p c {\displaystyle p_{c}} , the distribution of cluster sizes behaves as a power law, n ( s ) {\displaystyle n(s)} ~ s − 5 / 2 {\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 n / 2 {\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 n / 2 {\displaystyle n/2} , the size of the giant component is approximately 4 t − 2 n {\displaystyle 4t-2n} . However, according to the coupon collector's problem, Θ ( n log n ) {\displaystyle \Theta (n\log n)} edges are needed in order to have high probability that the whole random graph is connected.
… excerpt ends here. Continue reading the full article.
