giant component

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|n}} vertices is present, independently of the other edges, with probability {{mvar|p}}. In this model, if $p\; \backslash le\; \backslash frac\{1-\backslash epsilon\}\{n\}$ for any constant $\backslash epsilon>0$, then with high probability (in the limit as $n$ goes to infinity) all connected components of the graph have size {{math|O(log n)}}, and there is no giant component. However, for $p\; \backslash ge\; \backslash frac\{1\; +\; \backslash epsilon\}\{n\}$ there is with high probability a single giant component, with all other components having size {{math|O(log n)}}. For $p=p\_c\; =\; \backslash frac\{1\}\{n\}$, intermediate between these two possibilities, the number of vertices in the largest component of the graph, $P\_\{\backslash inf\}$ is with high probability proportional to $n^\{2/3\}$.{{citation|contribution=6. The Evolution of Random Graphs—The Giant Component|pages=130–159|title=Random Graphs|volume=73|series=Cambridge studies in advanced mathematics|first=Béla|last=Bollobás|edition=2nd|publisher=Cambridge University Press|year=2001|isbn=978-0-521-79722-1}}.

Giant component is also important in percolation theory.{{Cite book |last=Newman |first=M. E. J. |title=Networks : an introduction |date=2010 |publisher=Oxford University Press |location=New York |oclc=456837194}} When a fraction of nodes, $q=1-p$, is removed randomly from an ER network of degree $\backslash langle\; k\; \backslash rangle$, there exists a critical threshold, $p\_c=\; \backslash frac\{1\}\{\backslash langle\; k\; \backslash rangle\}$. Above $p\_c$ there exists a giant component (largest cluster) of size, $P\_\{\backslash inf\}$. $P\_\{\backslash inf\}$ fulfills, $P\_\{\backslash inf\}=p(1-\backslash exp(-\backslash langle\; k\; \backslash rangle\; P\_\{\backslash inf\}))$. For

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.

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 {{mvar|t}} edges have been added, for values of {{mvar|t}} 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, $\backslash Theta(n\backslash log\; n)$ edges are needed in order to have high probability that the whole random graph is connected.

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 $P(k)$. 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 $k$, then the giant component exists{{cite journal | last1=Molloy | first1=Michael | last2=Reed | first2=Bruce | title=A critical point for random graphs with a given degree sequence | journal=Random Structures & Algorithms | volume=6 | issue=2–3 | year=1995 | issn=1042-9832 | doi=10.1002/rsa.3240060204 | pages=161–180}} if and only if$$\backslash langle\; k^2\; \backslash rangle\; -\; 2\; \backslash langle\; k\; \backslash rangle>0.$$This is known as the Molloy and Reed condition.{{Cite journal |last=Molloy |first=Michael |last2=Reed |first2=Bruce |date=March 1995 |title=A critical point for random graphs with a given degree sequence |url=https://onlinelibrary.wiley.com/doi/10.1002/rsa.3240060204 |journal=Random Structures & Algorithms |language=en |volume=6 |issue=2-3 |pages=161–180 |doi=10.1002/rsa.3240060204 |issn=1042-9832}} The first moment of $P(k)$ is the mean degree of the network. In general, the $n$-th moment is defined as $\backslash langle\; k^n\; \backslash rangle\; =\; \backslash mathbb\; E\; [k^n]\; =\; \backslash sum\; k^n\; P(k)$.

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 $1+\backslash frac\{\backslash langle\; k\; \backslash rangle\; ^2\}\{2\backslash langle\; k\; \backslash rangle\; +\; \backslash langle\; k^2\; \backslash rangle\}.$ However, when there is a giant component, the size of the giant component is more tricky to evaluate.

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:

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 $k\_\backslash text\{in\}$ in-edges and $k\_\backslash text\{out\}$ out edges. By definition, the average number of in- and out-edges coincides so that $c\; =\; \backslash mathbb\; E\; [k\_\backslash text\{in\}]\; =\backslash mathbb\; E\; [k\_\backslash text\{out\}]$. If $$

G_0(x) = \textstyle \sum_{k} \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_{k} \displaystyle \frac{k}{\langle k \rangle}P(k)x^{k-1}

. For directed networks, generating function assigned to the joint probability distribution $$

P(k_{in}, k_{out})

can be written with two valuables $$

x

and $$

y

as: $$

\mathcal{G}(x,y) = \sum_{k_{in},k_{out}} \displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}

, then one can define $$

g(x) = \frac{1}{c} {\partial \mathcal{G}\over\partial x}\vert _{y=1}

and $$

f(y) = \frac{1}{c} {\partial \mathcal{G}\over\partial y}\vert _{x=1}

.

The criteria for giant component existence in directed and undirected random graphs are given in the table below:

• {{annotated link|Erdős–Rényi model}}
• {{annotated link|Fractals}}
• {{annotated link|Graph theory}}
• {{annotated link|Interdependent networks}}
• {{annotated link|Percolation theory}}
• {{annotated link|Percolation}}
• {{annotated link|Complex network}}
• {{annotated link|Network science}}
• {{annotated link|Scale-free network}}

{{reflist}}

Category:Graph connectivity

Category:Random graphs