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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (links)
м (links)
Строка 70: Строка 70:
  
 
В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что почти наверняка хотя
 
В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что почти наверняка хотя
бы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref>Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.</ref>[3], мы же лишь поясним, откуда в текущей ситуации появляется константа <tex>\gamma</tex> из формулировки предыдущей теоремы и почему она совпадает с одноименной константой из той же теоремы.
+
бы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref name="trueproof" />[3], мы же лишь поясним, откуда в текущей ситуации появляется константа <tex>\gamma</tex> из формулировки предыдущей теоремы и почему она совпадает с одноименной константой из той же теоремы.
  
 
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
 
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже

Версия 21:40, 24 мая 2020

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

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

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

Определение:
Простейший ветвящийся процесс. Пусть [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] новых частиц, а сама перестает быть активной. И так далее. Как это связано с формальным определением? Что здесь Y, что Z? Данный процесс может как завершиться (частицы перестанут быть активными), так и продолжаться бесконечно.

Теорема:
Пусть [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]. Что такое b, его же нет в определении?
Доказательство:
[math]\triangleright[/math]

Приведем здесь идеи[1], изложенные А.М. Райгородским [1], основанные на доказательстве[2] Р. Карпа[2]. Данное доказательство не настолько строгое, как приведенное в [3][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][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] [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].
  1. Найдутся такие [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].
  2. Число вершин в компонентах размера [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] — производящая функция числа детей каждой вершины. Тогда:
  1. Если ожидаемое количество детей в каждой вершине [math]\le 1[/math], тогда вероятность исчезновения — 1, если вероятность появления ровно одного ребенка равна [math]1[/math].
  2. Если ожидаемое количество детей в каждой вершине [math]\gt 1[/math], тогда вероятность исчезновения — единственное решение [math]f(x) = x[/math] на [math][0, 1)[/math].


В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины.
Обозначим:

  • [math]q[/math] - вероятность исчезновения;
  • [math]y \thicksim Binomial(s = n−c_1\log n, \frac{d}{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]f(x) = \sum_{i = 0..\infty}p_ix^i,[/math] где [math]p_i[/math] — вероятность того, что [math]y = i[/math]

Так как [math]q[/math] — вероятность конечности алгоритма, то, если у корневой вершины [math]i[/math] потомков, то построение каждого из поддеревьев должно завршиться, и это произойдет с вероятностью [math]q^i[/math]. Таким образом:
[math]q = \sum_{i = 0..\infty}p_iq^i[/math]
Таким образом, [math]q[/math] является корнем уравнения:
[math]x = \sum_{i = 0..\infty}p_ix^i \Leftrightarrow f(x) = x[/math]

Рассмотрим решение данного уравнения на [math][0; 1][/math] [math]x = 1[/math] — всегда решение данного уравнения, так как [math]\sum_{i = 0..\infty}p_i1^i = \sum_{i = 0..\infty}p_i = 1 = x[/math].
В поисках другого, меньшего корня, рассмотрим [math]m = f'(1) = \sum_{i = 1..\infty}ip_i[/math], другими словами [math]m = E([/math]количество потомков вершины[math])[/math] Кажется, что при [math]m \gt 1[/math] дерево будет расти вечно, так как каждая вершина в момент времени [math]j[/math] должна иметь потомков, однако при [math]p_0 \gt 0[/math] с положительной вероятность у корня может вообще не быть потомков. Вспоминая об исходном [math]G(n,\frac{d}{n})[/math]б ввиду того, что [math]d[/math] — ожидаемое количество потомков, [math]m[/math] играет роль [math]d[/math].

Решение уравнения f(x)=x

Далее, пользуясь описанными выше утверждениями, можно доказать, что:

  1. [math]m \lt 1[/math] [math]||[/math] [math]m = 1[/math] [math]\&[/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 1[/math], но, если [math]p_0 = 0[/math], процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;

Подробное описание доказательств данного факта, а также самих утверждений можно найти в [5][4].

Вывод

Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе [math]G(n, \frac{d}{n})[/math]. Рассчитав [math]p_0[/math] и [math]p_1[/math], можно сделать следующие выводы:

  1. [math]d \lt 1[/math] [math]||[/math] [math]d = 1[/math] [math]\&[/math] [math]p_1 \lt 1[/math] — вероятность завершения[math] = 1[/math];
  2. [math]d = 1[/math] [math]\&[/math] [math]p_1 = 1[/math] — вероятность завершения[math] = 0[/math];
  3. [math]d \gt 1[/math] — вероятность исчезновения [math] \lt 1[/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

Примечания

  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. 3,0 3,1 Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.
  4. Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf
  5. Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf