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

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

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

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

Гигантская составляющая также важна в теории перколяции.^[1][2][3][4] Когда часть узлов, ${ Displaystyle д = 1-р}$, случайным образом удаляется из сети ER степени ${ Displaystyle langle к rangle}$, существует критический порог, ${ displaystyle p_ {c} = { frac {1} { langle k rangle}}}$. Над ${ displaystyle p_ {c}}$ существует гигантский компонент (самый большой кластер) размера, ${ displaystyle P_ {inf}}$. ${ displaystyle P_ {inf}}$ выполняет, ${ displaystyle P_ {inf} = p (1- exp (- langle k rangle P_ {inf}))}$. Для ${ displaystyle p$ решение этого уравнения есть ${ displaystyle P_ {inf} = 0}$, т.е. отсутствует гигантская компонента.

В ${ displaystyle p_ {c}}$, распределение размеров кластеров ведет себя как степенной закон, ${ displaystyle n (s)}$~${ displaystyle s ^ {- 5/2}}$ что является особенностью фаза перехода. Гигантская составляющая появляется также в перколяции решетчатых сетей.^[2]

В качестве альтернативы, если добавить случайно выбранные ребра по одному, начиная с пустой график, то только примерно ${ displaystyle n / 2}$ были добавлены ребра, что граф содержит большую компоненту, и вскоре после этого компонент становится гигантским. Точнее, когда ${ displaystyle t}$ ребра были добавлены для значений ${ displaystyle t}$ близко, но больше чем ${ displaystyle n / 2}$, размер гигантской компоненты примерно равен ${ displaystyle 4t-2n}$.^[1] Однако, согласно проблема сборщика купонов, ${ Displaystyle Theta (п журнал п)}$ ребра необходимы для того, чтобы иметь высокую вероятность связности всего случайного графа.

Гигантский компонент во взаимозависимых сетях

Рассмотрим для простоты две сети ER с одинаковым количеством узлов и одинаковой степенью. Каждый узел в одной сети зависит от узла (для работы) в другой сети и наоборот через двунаправленные ссылки. Эта система называется взаимозависимыми сетями.^[5] Для того, чтобы система функционировала, обе сети должны иметь гигантские компоненты, где каждый узел в одной сети зависит от узла в другой. Это называется взаимной гигантской составляющей.^[5]Этот пример можно обобщить на систему из n сетей ER, связанных через связи зависимостей в древовидной структуре.^[6]Интересно, что для любого дерева, состоящего из n взаимозависимых сетей ER, взаимный гигантский компонент (MGC) определяется выражением ${ displaystyle P_ {inf} = p (1- exp (- langle k rangle P_ {inf})) ^ {n}}$что является естественным обобщением формулы для одной сети, см. уравнение выше.

Усиленные узлы

Компонент гиганта перколяции в присутствии усиленного (децентрализация сети) был изучен Юань и др.^[7]Усиленные узлы имеют дополнительные источники, которые могут поддерживать конечные компоненты, которым они принадлежат, то есть эквивалентно наличию альтернативных ссылок на гигантские компоненты.

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

Подобный резкий порог между параметрами, которые приводят к графам со всеми маленькими компонентами, и параметрами, которые приводят к гигантскому компоненту, также встречается в случайных графах с неравномерным распределение степеней Распределение степеней не определяет граф однозначно. Однако при предположении, что во всех отношениях, кроме распределения по степеням, графы рассматриваются как полностью случайные, многие результаты о конечных / бесконечных размерах компонентов известны. В этой модели существование гигантской компоненты зависит только от первых двух (смешанных) моменты распределения степеней. Пусть случайно выбранная вершина имеет степень ${ displaystyle k}$, то существует гигантская компонента^[8] если и только если

${ Displaystyle mathbb {E} [к]}$ который также записывается в виде ${ Displaystyle { langle к rangle}}$ - средняя степень сети. Подобные выражения верны и для ориентированные графы, в этом случае распределение степеней двумерный.^[9] Есть три типа связанных компонентов в ориентированные графы. Для случайно выбранной вершины:

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

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

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

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

О других свойствах гигантского компонента и его связи с теорией перколяции и критическими явлениями см. Ссылки.^[3][4][2]

Смотрите также

• Модель Эрдеша – Реньи
• Фракталы
• Теория графов
• Взаимозависимые сети
• Теория перколяции
• Перколяция
• Комплексные сети
• Сетевые науки
• Сети без масштабирования

использованная литература