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 vertices is present, independently of the other edges, with probability . In this model, if $p \le \frac$ for any constant $\epsilon>0$, then with high probability all connected components of the graph have size , and there is no giant component. However, for $p \ge \frac$ there is with high probability a single giant component, with all other components having size . For $p=p_c = \frac$, intermediate between these two possibilities, the number of vertices in the largest component of the graph, $P_$ is with high probability proportional to $n^$..

Giant component is also important in percolation theory. 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$. Above $p_c$ there exists a giant component (largest cluster) of size, $P_$. $P_$ fulfills, $P_=p(1-\exp(-\langle k \rangle P_))$. For p the solution of this equation is $P_=0$, i.e., there is no giant component.

At $p_c$, the distribution of cluster sizes behaves as a power law, $n(s)$~$s^$ 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 $n/2$ edges have been added that the graph contains a large component, and soon after that the component becomes giant. More precisely, when edges have been added, for values of close to but larger than $n/2$, the size of the giant component is approximately $4t-2n$. 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 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 $k$, then the giant component exists if and only if\mathbb E ^2- 2 \mathbb E 0.
\mathbb E which is also written in the form of $$

is the mean degree of the network. 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:

# 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 $k_\text$ in-edges and $k_\text$ out edges. By definition, the average number of in- and out-edges coincides so that c = \mathbb E _\text=\mathbb E _\text. If $G_0(x) = \textstyle \sum_ \displaystyle P(k)x^k$ is the generating function of the degree distribution $P(k)$ for an undirected network, then $G_1(x)$ can be defined as $G_1(x) = \textstyle \sum_ \displaystyle \fracP(k)x^$. For directed networks, generating function assigned to the joint probability distribution $P(k_, k_)$ can be written with two valuables $x$ and $y$ as: $\mathcal(x,y) = \sum_ \displaystyle P()x^y^$, then one can define $g(x) = \frac \vert _$ and $f(y) = \frac \vert _$.
The criteria for giant component existence in directed and undirected random graphs are given in the table below:

See also

* Erdős–Rényi model
* Fractals
* Graph theory
* Interdependent networks
* Percolation theory
* Percolation
* Complex Networks
* Network Science
* Scale free networks

References

{{reflist

Graph connectivity
Random graphs