Теорема о гигантской компоненте. Поиск в ширину в случайном графе

Эта статья находится в разработке!

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

Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.

Определение:

Простейший ветвящийся процесс. Пусть [math]Z_1,\dotsc Z_n,\dotsc [/math] — независимые пуассоновские величины с одним и тем же средним [math]\lambda[/math]. Положим [math]Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1[/math].

Представлять себе описанный только что процесс можно так. В начальный момент времени есть одна активная частица. Затем она делает [math]Z_1 \geq 0[/math] (можжет ыть достигнуто, так как величина [math]Z_1[/math] равна нулю с положительной вероятностью) активных потомков и перестает быть активной. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает [math]Z_2[/math] новых частиц, а сама перестает быть активной. И так далее. Данный процесс может как завершиться (частицы перестанут быть активными), так и продолжаться бесконечно.

Теорема:

Пусть [math]\lambda \leq 1[/math]. Тогда с вероятностью 1 процесс [math]Y_t[/math] вырождается, т.е. [math]P(\exists t: Y_t \leq 0) = 1[/math].

Теорема:

Пусть [math]\lambda \ge 1[/math]. Пусть [math]\gamma \in (0, 1)[/math] — единственное решение уравнения [math]1 - \gamma = e^{-\lambda \gamma}[/math]. Тогда процесс [math]Y_t[/math] вырождается с вероятностью [math]1 - \gamma[/math], т.е. [math]P(\exists t: Y_t \leq 0) = 1 - \gamma[/math].

Определение:

Ветвящийся процесс на случайном графе. Пусть [math]Z_1,\dotsc Z_n,\dotsc [/math] — независимые пуассоновские величины с одним и тем же средним [math]\lambda[/math]. Положим [math]Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1[/math].

Пусть дан граф [math]G = (V,E)[/math]. Зафиксируем [math]v_1 \in V[/math]. Пометим ее как активную, а все остальные вершины — нейтральными. Выберем среди нейтральных вершин всех соседей вершины [math]v_1[/math]. После этого пометим вершину [math]v_1[/math] как неактивную , а смежных с ней — как активных, а все остальные вершины — нейтральными.

Снова зафиксируем какую-нибудь активную вершину [math]v_2[/math], и повторим процесс. Не меняем статус остальных уже активных вершин.

Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую [math]v_1[/math]) и нейтральные вершины.

Обозначим число активных вершин в момент времени [math]t[/math] через [math]Y_t[/math], число нейтральных вершин — через [math]N_t[/math], а число соседей вершины, которую собираемся пометить как неактивную, — через [math]Z_t[/math]. Тогда [math]Y_0 = 1,Y_t = Y_t−1 + Z_t − 1[/math]. Все введенные величины зависят от графа [math]G[/math] и от последовательности выбираемых вершин [math]v_1,\dotsc[/math].

Если [math]G[/math] посчитать случайным, то при любом выборе вершин [math]v_1,\dotsc[/math] получатся случайные величины [math]Y_t, N_t, Z_t[/math] на пространстве [math]G(n, p)[/math].

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

Теорема (о гигантской компоненте):

Рассмотрим модель [math]G(n, p)[/math]. Пусть [math]p = \dfrac{ c }{n}[/math]. Если [math]c \lt 1[/math], то найдется такая константа [math]\beta = \beta(с)[/math], что а.п.н. размер каждой связной компоненты случайного графа не превосходит [math]b\ln n[/math]. Если же [math]c \gt 1[/math], то найдется такая константа [math]\gamma = \gamma(c)[/math], что а.п.н. в случайном графе есть ровно одна компонента размера [math]\geq\gamma n[/math]. Размер остальных компонент не превосходит [math]b\ln n[/math].

Доказательство:

[math]\triangleright[/math]

Приведем здесь идеи, изложенные А.М. Райгородским [1], основанные на доказательстве Р. Карпа [2]. Данное доказательство может быть, не настолько строгое, как приведенное в [3], однако отличается лаконичностью и наглядностью. Случай [math]c \lt 1[/math]. Положим [math]t_0=[\beta \ln n][/math], где [math]\beta = \beta(c)[/math] — константа, которую мы подберем позднее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер [math]\le t_0[/math]. Но размер компоненты — это момент вырождения процесса [math]Y_t[/math] на случайном графе. Значит, интересующее нас утверждение можно записать в следующем виде: [math]P_{n, p}(\exists v_1 : Y_{t_0} \gt 0) \rightarrow 0, n \rightarrow \infty[/math] Поскольку [math]P_{n, p}(\exists v_1 : Y_{t_0} \gt 0) \le nP_{n, p}(Y_{t_0} \ge 0)[/math], достаточно найти такое [math]\beta[/math], при котором [math]P_{n, p}(Y_{t_0} \gt 0) = o\left(\dfrac{1}{n}\right).[/math] Далее: [math]P_{n, p}(Y_{t_0} \gt 0) = P_{n, p}(\xi_{t_o} \gt t_0) \thickapprox P_{n, p}(Binom(n, 1 - (1 - p)^{t_0}) \gt t_0) \thickapprox ([/math] с учетом асимптотики [math]1 - (1 - p)^{t_0} \thicksim pt_0) \thickapprox P_{n, p}(Binom(n, pt_0) \gt t_0)[/math] [math]\thickapprox ([/math]с учетом центральной предельной теоремы) [math] \thickapprox [/math] [math]\int\limits_{\dfrac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \dfrac{1}{\sqrt{2\pi}}e^{-\dfrac{x^2}{2}}\,dx[/math]. Поскольку [math]c \lt 1[/math], нижний предел интегрирования имеет порядок [math]\sqrt{t_0}[/math]. Таким образом, весь интеграл не превосходит величины [math]e^{−\delta t_0}[/math]. Выберем [math]\beta[/math] таким, чтобы [math]e^{−\delta t_0}[/math] оказалось меньше, чем [math]e^{-2 \ln n} = \dfrac{1}{n^2}[/math], и в случае [math]c \lt 1[/math] теорема доказана. Случай [math]c \gt 1[/math]. В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что почти наверняка хотя бы в одном запуске возникнет гигантская компонента. Подробности можно найти в [3], мы же лишь поясним, откуда в текущей ситуации появляется константа [math]\gamma[/math] из формулировки предыдущей теоремы и почему она совпадает с одноименной константой из той же теоремы. Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже при [math]t \thickapprox \gamma n[/math]. Иными словами, необходимо, чтобы: [math]P_{n, p}(Y_{t_0} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty[/math] Так как по условию [math]p = \dfrac{ c }{n}[/math], то при [math]t \thicksim \alpha n[/math] выполнено: [math] 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}[/math] Применим центральную предельную теорему к [math]P_{n, p}(Y_{t_0} \le 0)\thickapprox P_{n, p}(Binom(n, 1 - e^{-c\alpha}) \le \alpha n).[/math] Интегрирование пойдет от минус бесконечности до [math]\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}[/math]. Если [math]\alpha \lt 1 - e^{-c\alpha}[/math], то мы получим искомое стремление вероятности к нулю. Если [math]\alpha \gt 1 - e^{-c\alpha}[/math], то вероятность, напротив, будет стремиться к единице. Таким образом, критическое значение [math]\alpha[/math], вплоть до которого есть именно стремление к нулю, — это решение уравнения [math]\alpha = 1 - e^{-c\alpha}[/math] или, что равносильно, [math]1 - \alpha = e^{-c\alpha}[/math]. А это и есть уравнение из предыдущей теоремы, если заменить [math]\lambda[/math] на [math]c[/math].

[math]\triangleleft[/math]

Обход случайного графа

Приведем ряд утверждений, которые будут использованы а дальнейшем. Доказательство опустим ради лаконичиности, их, а также более детальный рассказ можно найти в [4].

Утверждение:

Пусть [math]d \gt 1[/math]. Тогда вероятность [math]p[/math], что [math]size(cc(v)) = O(\log n)[/math] ([math]cc[/math] — компонента связности, содержащая [math]v[/math]): [math]p \lt 1[/math] — константа.

[math]\triangleright[/math]

Главная идея доказательства, которую мы будем использовать в дальнейшем — изменение алгоритма БФС таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает БФС в ветвящийся процесс.

[math]\triangleleft[/math]

Теорема:

Пусть [math]p = \frac{d}{n}, d \gt 1[/math]. Найдутся такие [math]c_1, c_2[/math], что с [math]p \leq \frac{1}{n}[/math] [math]\exists cc: size(cc) \in (c_1\log n; c_2n)[/math]. Число вершин в компонентах размера [math]O(\ln n)[/math] а.п.н. [math]\leq cn, c \lt 1[/math]. Тогда с [math]p = 1 - o(1)[/math] существует компонента связности размера [math]\Omega (n)[/math].

Обход в ширину

Воспользуемся полученными знаниями.
Рассмотрим граф [math]G(n, p)[/math]. Проанализируем его структуру по мере роста [math]p[/math]. При [math]p = 0[/math], граф состоит только из изолированных вершин. С ростом [math]p[/math] в нем появляются ребра, компоненты связности получающегося леса объединяются. При достижении [math]p = o\left(\frac{1}{n}\right)[/math] граф а.п.н. является лесом. Когда [math]p = \frac{d}{n}[/math], появляются циклы. При [math]d \lt 1[/math], размер каждой из компонент связности [math]= \Omega(\log n)[/math]. Число компонент связности, содержащих только один цикл — константа, зависящая от [math]n[/math]. Таким образом, граф состоит из леса и компонент, содержащих единственный цикл без компонент размера [math]\Omega(\log n)[/math].
Когда [math]p = \frac{1}{n}[/math] начинает образовываться гигантская компонента. Этот процесс происходит в два этапа: при [math]p = \frac{1}{n}[/math] возникают компоненты из [math]n^{\frac{2}{3}}[/math] вершин, а.п.н. являющиеся деревьями. При [math]p = \frac{d}{n}, d \gt 1[/math], появляется гигантская компонента размером, пропорциональным количеству вершин во всем графе.
После превышения [math]p[/math] значения [math]\frac{d}{n}[/math], все неизолированные вершины оказываются в гигантской компоненте. При достижении [math]\frac{\ln n}{2n}[/math], в графе остаются только изолированные плюс гигантская компонента. Когда [math]p[/math] становится равной[math]\frac{\ln n}{n}[/math]граф становится связным. При [math]p = \frac{1}{2}[/math] верно: [math]\forall \varepsilon \gt 0[/math] в [math]G[/math] существует клика размером [math](2 - \varepsilon )\log n[/math].

Чтобы вычислить размер компоненты связности, пройдемся с помощью БФС по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью [math]p = \frac{d}{n}[/math]). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.

Проблема БФС

На данном изображении представлены результаты работы БФС, начавшемся в вершине [math]1[/math] на двух графах: в первом у всех ребер [math]p = 1[/math], во втором же факт существования ребра определялся по ходу работы алгоритма — ребра, отмеченные пунктиром, не существуют. Возникающая проблема состоит в том, что, к примеру, Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине [math]2[/math], алгоритм не делал запрос о ребре [math](2, 3)[/math], так как у этому моменту вершина [math]3[/math] уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.

Неоткрытые вершины

Будем считать шагом алгоритма поиска открытие новой вершины. После первых [math]i[/math] шагов алгоритма, любая из вершин, кроме стартовой, может быть неоткрытой с вероятностью [math]p = (1 - \frac{d}{n})^i[/math]. Пусть [math]z_i[/math] — число вершин, открытых за первые [math]i[/math] шагов алгоритма поиска. [math]z_i[/math] распределены как [math]Binomial(n − 1,1 − (1 - \frac{d}{n})^i)[/math].

Ветвящийся процесс

Пользуясь идеями, изложенными в доказательстве леммы, переходим от модифицированного БФС к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.
Рассмотрим натуральное случайное число [math]y[/math], обозначающее количество детей у очередной исследованной вершины. Каждый раз это значение выбирется случайно и независимо.
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее "дети". Данный процесс может продолжаться бесконечно.
Пусть [math]y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})[/math]. Пусть [math]p′[/math] — вероятность того, что [math]size(cc(v)) = O(\log n)[/math] в модицированном БФС. Пусть [math]q[/math] — вероятность окончания процесса. Тогда [math]q \geq p′[/math], поскольку БФС, заканчивающийся с [math] \le c_1\log n[/math] вершинами, приводит к окончанию построения дерева.
Пусть [math]p_i = \binom{s}{i}(\frac{d}{n})^i(1 − \frac{d}{n})^{s − i}[/math] — вероятность, что [math]y[/math] производит [math]i[/math] детей. Тогда:
[math]\sum_{i = 0..s}p_i = 1[/math] и [math]\sum_{i = 0..s}ip_i = E(y) = \frac{ds}{n} \gt 1[/math].
Глубина дерева [math]\geq[/math] количеству вершин. Пусть [math]a_i[/math] — вероятность того, что процесс закончится с деревом глубины [math]t[/math]. Имеем:
[math]a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}[/math]

Вероятность исчезновения

Определение:

Вероятность исчезновения (extinction probability) — вероятность, того, что дерево ветвящегося процесса будет конечным, то есть данный процесс завершится через конечное время.

Утверждение:

Пусть [math]m \gt 1[/math]. Пусть [math]q[/math] — единственный корень [math]f(x) = x[/math] на [math][0, 1)[/math]. Тогда [math]f_j(x) = \lim_{j \to \infty}p(j) = q[/math] для [math]x\in [0,1)[/math].

Теорема:

Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть [math]f(x)[/math] — производящая функция числа детей каждой вершины. Тогда: Если ожидаемое количество детей в каждой вершине [math]\le 1[/math], тогда вероятность исчезновения — 1, если вероятность появления ровно одного ребенка равна [math]1[/math]. Если ожидаемое количество детей в каждой вершине [math]\gt 1[/math], тогда вероятность исчезновения — единственное решение [math]f(x) = x[/math] на [math][0, 1)[/math].

В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины.
Для того, чтобы вычислить вероятность исчезновения, воспользуемся производящей функцией:
[math]f(x) = \sum_{i = 0..\infty}p_ix^i,[/math] где [math]p_i[/math] — вероятность того, что [math]y = i[/math]

Эта статья находится в разработке!

Вывод

Сделайем вывод о вероятности исчезновения рассматриваемой версии ветвящегося процесса:

1. [math]m \lt 1[/math] [math]||[/math] [math]m = 1[/math] & [math]p_1 \lt 1[/math] — вероятность исчезновения [math] = 1[/math];
   
2. [math]m = 1[/math] [math]&[/math] [math]p_1 = 1[/math] — вероятность исчезновения [math] = 0[/math];
   
3. [math]m \gt 1[/math] — вероятность исчезновения [math] \lt 0[/math], но, если [math]p_0 = 0[/math], процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;
   

Литература

1. Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.— М.: МЦНМО, 2013 — C.330-339 — ISBN 978-5-4439-0040-7
2. Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.
3. Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.
4. Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf

См. также

• Случайная величина
• Центральная предельная теорема
• Случайные графы
• Обход в ширину
• Производящая функция
• Ветвящийся процесс