Giant component Information
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 for any constant , then with high probability all connected components of the graph have size O(log n), and there is no giant component. However, for there is with high probability a single giant component, with all other components having size O(log n). For , intermediate between these two possibilities, the number of vertices in the largest component of the graph, is with high probability proportional to .^{ [1]}
Giant component is also important in percolation theory.^{ [1]}^{ [2]} When a fraction of nodes, , is removed randomly from an ER network of degree , there exists a critical threshold, . Above there exists a giant component (largest cluster) of size, . fulfills, . For the solution of this equation is , i.e., there is no giant component.
At , the distribution of cluster sizes behaves as a power law, ~ 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 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 , the size of the giant component is approximately .^{ [1]} However, according to the coupon collector's problem, 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 , then the giant component exists^{ [3]} if and only if
- out-component is a set of vertices that can be reached by recursively following all out-edges forward;
- in-component is a set of vertices that can be reached by recursively following all in-edges backward;
- 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 in-edges and out edges. By definition, the average number of in- and out-edges coincides so that . If is the generating function of the degree distribution for an undirected network, then can be defined as . For directed networks, generating function assigned to the joint probability distribution can be written with two valuables and as: , then one can define and . The criteria for giant component existence in directed and undirected random graphs are given in the table below:
Type | Criteria |
---|---|
undirected: giant component | ,^{ [3]} or ^{ [4]} |
directed: giant in/out-component | ,^{ [4]} or ^{ [4]} |
directed: giant weak component | ^{ [5]} |
See also
- Erdős–Rényi model
- Fractals
- Graph theory
- Interdependent networks
- Percolation theory
- Percolation
- Complex Networks
- Network Science
- Scale free networks
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.
- ^ Newman, M. E. J. (2010). Networks : an introduction. New York: Oxford University Press. OCLC 456837194.
- ^ ^{a} ^{b} Molloy, Michael; Reed, Bruce (1995). "A critical point for random graphs with a given degree sequence". Random Structures & Algorithms. 6 (2–3): 161–180. doi: 10.1002/rsa.3240060204. ISSN 1042-9832.
- ^ ^{a} ^{b} ^{c} ^{d} Newman, M. E. J.; Strogatz, S. H.; Watts, D. J. (2001-07-24). "Random graphs with arbitrary degree distributions and their applications". Physical Review E. 64 (2): 026118. arXiv: cond-mat/0007235. Bibcode: 2001PhRvE..64b6118N. doi: 10.1103/physreve.64.026118. ISSN 1063-651X. PMID 11497662.
- ^ Kryven, Ivan (2016-07-27). "Emergence of the giant weak component in directed random graphs with arbitrary degree distributions". Physical Review E. 94 (1): 012315. arXiv: 1607.03793. Bibcode: 2016PhRvE..94a2315K. doi: 10.1103/physreve.94.012315. ISSN 2470-0045. PMID 27575156. S2CID 206251373.