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

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

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

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

Гигантская составляющая также важна в теории перколяции. ^{[1] [2] [3] [4]} Когда доля узлов, , удаляется случайным образом из ER сети степени , существует критический порог, . Выше находится гигантский компонент (самый большой кластер) размером . отрабатывает, . Ибо решение этого уравнения есть , т. Е. Отсутствует гигантская составляющая.${\ Displaystyle д = 1-р}$${\displaystyle \langle k\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<p_{c}}$${\displaystyle P_{inf}=0}$

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

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

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

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

Усиленные узлы [ править ]

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]