Английская Википедия:Giant component
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 Шаблон:Mvar vertices is present, independently of the other edges, with probability Шаблон:Mvar. In this model, if <math>p \le \frac{1-\epsilon}{n}</math> for any constant <math>\epsilon>0</math>, then with high probability (in the limit as <math>n</math> goes to infinity) all connected components of the graph have size Шаблон:Math, and there is no giant component. However, for <math>p \ge \frac{1 + \epsilon}{n}</math> there is with high probability a single giant component, with all other components having size Шаблон:Math. For <math>p=p_c = \frac{1}{n}</math>, intermediate between these two possibilities, the number of vertices in the largest component of the graph, <math>P_{\inf}</math> is with high probability proportional to <math>n^{2/3}</math>.[1]
Giant component is also important in percolation theory.[1][2] When a fraction of nodes, <math>q=1-p</math>, is removed randomly from an ER network of degree <math>\langle k \rangle</math>, there exists a critical threshold, <math>p_c= \frac{1}{\langle k \rangle}</math>. Above <math>p_c</math> there exists a giant component (largest cluster) of size, <math>P_{\inf}</math>. <math>P_{\inf}</math> fulfills, <math>P_{\inf}=p(1-\exp(-\langle k \rangle P_{\inf}))</math>. For <math>p<p_c</math> the solution of this equation is <math>P_{\inf}=0</math>, i.e., there is no giant component.
At <math>p_c</math>, the distribution of cluster sizes behaves as a power law, <math>n(s)</math>~<math>s^{-5/2}</math> 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 <math>n/2</math> edges have been added that the graph contains a large component, and soon after that the component becomes giant. More precisely, when Шаблон:Mvar edges have been added, for values of Шаблон:Mvar close to but larger than <math>n/2</math>, the size of the giant component is approximately <math>4t-2n</math>.[1] However, according to the coupon collector's problem, <math>\Theta(n\log n)</math> 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 <math>k </math>, then the giant component exists[3] if and only if<math display="block">\mathbb E [k^2] - 2 \mathbb E [k]>0.</math><math>
\mathbb E [k]
</math> which is also written in the form of <math> {\langle k \rangle} </math> is the mean degree of the network. Similar expressions are also valid for directed graphs, in which case the degree distribution is two-dimensional.[4] There are three types of connected components in directed graphs. For a randomly chosen vertex:
- 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 <math>k_\text{in} </math> in-edges and <math>k_\text{out} </math> out edges. By definition, the average number of in- and out-edges coincides so that <math>c = \mathbb E [k_\text{in}] =\mathbb E [k_\text{out}] </math>. If <math> G_0(x) = \textstyle \sum_{k} \displaystyle P(k)x^k </math> is the generating function of the degree distribution <math> P(k) </math> for an undirected network, then <math> G_1(x)
</math> can be defined as <math> G_1(x) = \textstyle \sum_{k} \displaystyle \frac{k}{\langle k \rangle}P(k)x^{k-1} </math>. For directed networks, generating function assigned to the joint probability distribution <math> P(k_{in}, k_{out}) </math> can be written with two valuables <math> x </math> and <math> y </math> as: <math> \mathcal{G}(x,y) = \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}} </math>, then one can define <math> g(x) = \frac{1}{c} {\partial \mathcal{G}\over\partial x}\vert _{y=1} </math> and <math> f(y) = \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1} </math>. The criteria for giant component existence in directed and undirected random graphs are given in the table below:
| Type | Criteria |
|---|---|
| undirected: giant component | <math>\mathbb E [k^2] - 2 \mathbb E [k]>0</math>,[3] or <math>G'_1(1)=1</math>[4] |
| directed: giant in/out-component | <math>\mathbb E [k_\text{in}k_{out}] - \mathbb E [k_\text{in}]>0</math>,[4] or <math>g'_1(1)= f'_1(1) = 1</math>[4] |
| directed: giant weak component | <math>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] +\mathbb{E}[k_\text{in}^2]\mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in} k_\text{out}]^2 >0
</math>[5]
|
See also
- Erdős–Rényi model
- Fractals
- Graph theory
- Interdependent networks
- Percolation theory
- Percolation
- Complex Networks
- Network Science
- Scale free networks
References
