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

Большая связная компонента случайного графа

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

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

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

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

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

Гигантская компонента также важна в теории перколяции. ^{[1] [2]} Когда часть узлов , , случайно удаляется из сети ER степени , существует критический порог , . Выше существует гигантская компонента (самый большой кластер) размером . выполняет, . Для решения этого уравнения есть , т. е. гигантская компонента отсутствует. ${\displaystyle q=1-p}$ ${\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}$

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

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

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

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

$${\displaystyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0.}$$

${\displaystyle \mathbb {E} [k]}$ориентированных графовраспределение степеней^{[4] В} ориентированных графах ${\displaystyle {\langle k\rangle }}$

1. out-comment — это набор вершин, до которых можно добраться, рекурсивно следуя вперед по всем исходящим ребрам;
2. in-компонент — это набор вершин, до которого можно добраться, рекурсивно следуя по всем внутренним ребрам назад;
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}}$

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

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

Рекомендации

1. Bollobás, Бела (2001), «6. Эволюция случайных графов - гигантская компонента», Случайные графики , Кембриджские исследования по высшей математике, том. 73 (2-е изд.), Cambridge University Press, стр. 130–159, ISBN. 978-0-521-79722-1.
2. Ньюман, MEJ (2010). Сети: введение . Нью-Йорк: Издательство Оксфордского университета. ОСЛК  456837194.
3. Моллой, Майкл; Рид, Брюс (1995). «Критическая точка для случайных графов с заданной последовательностью степеней». Случайные структуры и алгоритмы . 6 (2–3): 161–180. дои : 10.1002/rsa.3240060204. ISSN  1042-9832.
4. Ньюман, MEJ; Строгац, С.Х.; Уоттс, ди-джей (24 июля 2001 г.). «Случайные графы с произвольным распределением степеней и их приложения». Физический обзор E . 64 (2): 026118. arXiv : cond-mat/0007235 . Бибкод : 2001PhRvE..64b6118N. дои : 10.1103/physreve.64.026118 . ISSN  1063-651X. ПМИД  11497662.
5. Кривень, Иван (27 июля 2016 г.). «Появление гигантской слабой компоненты в ориентированных случайных графах с произвольным распределением степеней». Физический обзор E . 94 (1): 012315. arXiv : 1607.03793 . Бибкод : 2016PhRvE..94a2315K. doi : 10.1103/physreve.94.012315. ISSN  2470-0045. PMID  27575156. S2CID  206251373.