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.

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\leq {\frac {1-\epsilon }{n}}$ for any constant $\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\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}={\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}$ .^[1]

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

At $p_{c}$ , the distribution of cluster sizes behaves as a power law, $n(s)~s^{-5/2}$ which is a feature of phase transition. Giant component appears also in percolation of lattice networks.^[2]

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

Graphs with arbitrary degree distribution

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$ , then the giant component exists^[5] if and only if $\mathbb {E} [k^{2}]-2\mathbb {E} [k]>0.$ 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:

a. out-component is a set of vertices that can be reached by recursively following all out-edges forward;

b. in-component is a set of vertices that can be reached by recursively following all in-edges backward;

c. weak component is a set of vertices that can be reached by recursively following all edges regardless of their direction.

Let a randomly chosen vertex has $k_{\text{in}}$ in-edges and $k_{\text{in}}$ out edges. By definition, the average number of in- and out-edges coincides so that $\mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]$ . The criteria for giant component existence in directed and undirected random graphs are given in the table below.

Criteria for giant component existence in directed and undirected configuration graphs, $\mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]$
Type	Criteria
undirected: giant component	$\mathbb {E} [k^{2}]-2\mathbb {E} [k]>0$ ^[5]
directed: giant in/out-component	$\mathbb {E} [k_{\text{in}}k_{out}]-\mathbb {E} [k_{\text{in}}]>0$ ^[6]
directed: giant weak component	$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}]+[k_{\text{in}}^{2}]k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}k_{\text{out}}]^{2}>0$ ^[7]

For other properties of the giant component and its relation to percolation theory and critical phenomena, see references.^[3]^[4]^[2]

References

^ ^a ^b ^c Bollobás, Béla (2001), "6. The Evolution of Random Graphs—The Giant Component", Random Graphs, Cambridge studies in advanced mathematics, vol. 73 (2nd ed.), Cambridge University Press, pp. 130–159, ISBN 978-0-521-79722-1.
^ ^a ^b ^c Armin., Bunde, (1996). Fractals and Disordered Systems. Havlin, Shlomo. (Second rev. and enlarged ed.). Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642848681. OCLC 851388749.{{cite book}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)
^ ^a ^b Cohen, Reuven; Havlin, Shlomo (2010). Complex Networks: Structure, Robustness and Function. Cambridge: Cambridge University Press. doi:10.1017/cbo9780511780356. ISBN 9780521841566.
^ ^a ^b Newman, M. E. J. (2010). Networks : an introduction. New York: Oxford University Press. OCLC 456837194.
^ ^a ^b M. Molloy and B. Reed (1995). "A critical point for random graphs with a given degree sequence". "Random Struct. Algorithms" 6, 161
^ M. E. J. Newman, S. H. Strogatz, and D. J. Watts (2001). "Random graphs with arbitrary degree distributions and their applications". Phys. Rev. E 64, 026118
^ I. Kryven (2016). "Emergence of the giant weak component in directed random graphs with arbitrary degree distributions" Phys. Rev. E 94, 012315

[b-1] Bollobás, Béla (2001), "6. The Evolution of Random Graphs—The Giant Component", Random Graphs, Cambridge studies in advanced mathematics, vol. 73 (2nd ed.), Cambridge University Press, pp. 130–159, ISBN 978-0-521-79722-1.

[:0-2] Armin., Bunde, (1996). Fractals and Disordered Systems. Havlin, Shlomo. (Second rev. and enlarged ed.). Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642848681. OCLC 851388749.{{cite book}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)

[:1-3] Cohen, Reuven; Havlin, Shlomo (2010). Complex Networks: Structure, Robustness and Function. Cambridge: Cambridge University Press. doi:10.1017/cbo9780511780356. ISBN 9780521841566.

[:2-4] Newman, M. E. J. (2010). Networks : an introduction. New York: Oxford University Press. OCLC 456837194.

[Molloy&Reed1995-5] M. Molloy and B. Reed (1995). "A critical point for random graphs with a given degree sequence". "Random Struct. Algorithms" 6, 161

[NewmanStrogatzWatts2001-6] M. E. J. Newman, S. H. Strogatz, and D. J. Watts (2001). "Random graphs with arbitrary degree distributions and their applications". Phys. Rev. E 64, 026118

[Kryven2016-7] I. Kryven (2016). "Emergence of the giant weak component in directed random graphs with arbitrary degree distributions" Phys. Rev. E 94, 012315

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Giant component in Erdős–Rényi model

Graphs with arbitrary degree distribution

See also

References