Гигантский компонент

Случайный граф Эрдеша – Реньи – Гилберта с 1000 вершинами при критической вероятности ребра. $p=1/(n-1)$, показывающий большой компонент и множество мелких. При такой вероятности ребра большой компонент еще не является гигантским компонентом: он содержит только сублинейное количество вершин.

В теории сетей гигантский компонент — это связный компонент данного случайного графа всего графа , который содержит значительную часть вершин .

Точнее, в графах, построенных случайным образом из распределения вероятностей по произвольно большим графам, гигантский компонент — это компонент связности, доля которого в общем числе вершин отделена от нуля. В достаточно плотных графах, распределенных по модели Эрдеша–Реньи , с большой вероятностью существует гигантская компонента.

Гигантская компонента в модели Эрдеша – Реньи

Гигантские компоненты являются характерной особенностью модели Эрдеша-Реньи (ER) случайных графов, в которой каждое возможное ребро, соединяющее пары заданного набора из n вершин, присутствует независимо от других ребер с вероятностью p . В этой модели, если $p\leq {\frac {1-\epsilon }{n}}$ для любой константы $\epsilon >0$, то с большой вероятностью (в пределе $n$ стремится к бесконечности) все компоненты связности графа имеют размер O(log n ) и гигантской компоненты нет. Однако для $p\geq {\frac {1+\epsilon }{n}}$ с высокой вероятностью существует один гигантский компонент, а все остальные компоненты имеют размер O(log n ) . Для $p=p_{c}={\frac {1}{n}}$, промежуточное между этими двумя возможностями, число вершин в наибольшей компоненте графа, $P_{\inf }$ с высокой вероятностью пропорционален $n^{2/3}$.

Гигантская компонента также важна в теории перколяции. Когда часть узлов, $q=1-p$, удаляется случайным образом из сети ER степени $\langle k\rangle$, существует критический порог, $p_{c}={\frac {1}{\langle k\rangle }}$. Выше $p_{c}$ существует гигантский компонент (самый большой кластер) размера, $P_{\inf }$. $P_{\inf }$ выполняет, $P_{\inf }=p(1-\exp(-\langle k\rangle P_{\inf }))$. Для $p<p_{c}$ решение этого уравнения есть $P_{\inf }=0$, т. е. гигантской компоненты нет.

В $p_{c}$, распределение размеров кластеров ведет себя по степенному закону: $n(s)$~ $s^{-5/2}$ что является особенностью фазового перехода .

Альтернативно, если добавлять случайно выбранные ребра по одному, начиная с пустого графа , то это произойдет только примерно до тех пор, пока $n/2$ добавлены ребра, что граф содержит большую компоненту, и вскоре после этого компонента становится гигантской. Точнее, когда t было добавлено ребер, для значений t, близких к, но превышающих $n/2$, размер гигантской компоненты примерно $4t-2n$. Однако, согласно задаче сборщика купонов , $\Theta (n\log n)$ ребра необходимы для того, чтобы иметь высокую вероятность того, что весь случайный граф связен.

Графы с произвольными распределениями степеней

Аналогичный резкий порог между параметрами, которые приводят к графам со всеми компонентами малыми, и параметрами, которые приводят к гигантской компоненте, также встречается в случайных графах с неравномерным распределением степеней .Распределение степеней не определяет граф однозначно. Однако если предположить, что во всех отношениях, кроме распределения степеней,графы рассматриваются как полностью случайные, известны многие результаты о конечных/бесконечных размерах компонентов. В этой модели существование гигантской компоненты зависит только от первых двух (смешанных) моментов распределения степеней. Пусть случайно выбранная вершина имеет степень $k$, то гигантская компонента существует тогда и только тогда, когда $$\mathbb {E} [k^{2}]-2\mathbb {E} [k]>0.$$$\mathbb {E} [k]$ что также записывается в виде ${\langle k\rangle }$ — средняя степень сети. Подобные выражения справедливы и для ориентированных графов , в этом случае распределение степеней является двумерным. есть три типа связных компонент В ориентированных графах . Для случайно выбранной вершины:

1. out-компонент — это набор вершин, до которых можно добраться, рекурсивно следуя вперед по всем исходящим ребрам;
2. in-компонент — это набор вершин, до которого можно добраться, рекурсивно следуя по всем внутренним ребрам назад;
3. слабый компонент — это набор вершин, до которого можно добраться, рекурсивно следуя по всем ребрам независимо от их направления.

Критерии существования гигантских компонент в ориентированных и неориентированных графах конфигурации.

Пусть случайно выбранная вершина имеет $k_{\text{in}}$ по краям и $k_{\text{out}}$ внешние края. По определению среднее количество входящих и исходящих ребер совпадает, так что $c=\mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]$. Если $G_{0}(x)=\textstyle \sum _{k}\displaystyle P(k)x^{k}$ является производящей функцией распределения степеней $P(k)$ для ненаправленной сети, то $G_{1}(x)$ может быть определен как $G_{1}(x)=\textstyle \sum _{k}\displaystyle {\frac {k}{\langle k\rangle }}P(k)x^{k-1}$. Для направленных сетей производящая функция присваивается совместному распределению вероятностей $P(k_{in},k_{out})$ можно записать с двумя значениями $x$ и $y$ как: ${\mathcal {G}}(x,y)=\sum _{k_{in},k_{out}}\displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}$, то можно определить $g(x)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial x}\vert _{y=1}$ и $f(y)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial y}\vert _{x=1}$. Критерии существования гигантской компоненты в направленных и неориентированных случайных графах приведены в таблице ниже:

Тип	Критерии
ненаправленный: гигантский компонент	$\mathbb {E} [k^{2}]-2\mathbb {E} [k]>0$, или $G'_{1}(1)=1$
направление: гигантский входной/выходной компонент	$\mathbb {E} [k_{\text{in}}k_{out}]-\mathbb {E} [k_{\text{in}}]>0$, или $g'_{1}(1)=f'_{1}(1)=1$
направлено: гигантский слабый компонент	$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$

См. также

• Модель Эрдеша – Реньи - две тесно связанные модели для создания случайных графов.
• Фракталы – бесконечно подробная математическая структура. Страницы с краткими описаниями целей перенаправления.
• Теория графов – Область дискретной математики
• Взаимозависимые сети - Подобласть сетевой науки
• Теория перколяции - Математическая теория поведения связанных кластеров в случайном графе.
• Перколяция - фильтрация жидкостей через пористые материалы.
• Сложная сеть - сеть с нетривиальными топологическими особенностями.
• Сетевая наука - Академическая область
• Безмасштабная сеть - сеть, распределение степеней которой подчиняется степенному закону.