Giant component

In network theory, a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices. In network theory, a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices. 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 pleq {frac {1-epsilon }{n}}} for any constant ϵ > 0 {displaystyle 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 ≥ 1 + ϵ n {displaystyle pgeq {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 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 angle } , there exists a critical threshold, p c = 1 ⟨ k ⟩ {displaystyle p_{c}={frac {1}{langle k angle }}} . Above p c {displaystyle p_{c}} there exists a giant component (largest cluster) of size, P i n f {displaystyle P_{inf}} . P i n f {displaystyle P_{inf}} fulfills, P i n f = p ( 1 − exp ⁡ ( − ⟨ k ⟩ P i n f ) {displaystyle P_{inf}=p(1-exp(-langle k angle P_{inf})} . For p < p c {displaystyle p<p_{c}} the solution of this equation is P i n f = 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 )   s − 5 / 2 {displaystyle n(s)~s^{-5/2}} which is a feature of phase transition. Giant component appears also in percolation of lattice networks. 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 {displaystyle t} edges have been added, for values of t {displaystyle 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 (nlog 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 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 k {displaystyle k} , then the giant component exists if and only if