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.

An Erdős–Rényi–Gilbert random graph with 1000 vertices at the critical edge probability , 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.

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

edit

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 (in the limit as   goes to infinity) 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

edit

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 tree-like random graphs with non-uniform degree distributions  . The degree distribution does not define a graph uniquely. However, under the 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 have degree  , then the giant component exists[3] if and only if This is known as the Molloy and Reed condition.[4] The first moment of   is the mean degree of the network. In general, the  -th moment is defined as  .

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   However, when there is a giant component, the size of the giant component is more tricky to evaluate.[2]

Criteria for giant component existence in directed and undirected configuration graphs

edit

Similar expressions are also valid for directed graphs, in which case the degree distribution is two-dimensional.[5] There are three types of connected components in directed graphs. For a randomly chosen vertex:

  1. out-component is a set of vertices that can be reached by recursively following all out-edges forward;
  2. in-component is a set of vertices that can be reached by recursively following all in-edges backward;
  3. 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   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  [5]
directed: giant in/out-component  ,[5] or  [5]
directed: giant weak component  [6]

See also

edit

References

edit
  1. ^ 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.
  2. ^ a b Newman, M. E. J. (2010). Networks : an introduction. New York: Oxford University Press. OCLC 456837194.
  3. ^ 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.
  4. ^ Molloy, Michael; Reed, Bruce (March 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.
  5. ^ 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.
  6. ^ 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.