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

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

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

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

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

Простейший ветвящийся процесс. Пусть [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]

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

Воспользуемся полученными в предыдущем разделе знаниями.
Рассмотрим граф [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]). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.
[Файл:bfs_problem.png|500px|center|Проблема БФС]]
На данном изображении представлены результаты работы БФС, начавшемся в вершине [math]1[/math] на двух графах: в первом у всех ребер [math]p = 1[/math], во втором же факт существования ребра определялся по ходу работы алгоритма — ребра, отмеченные пунктиром, не существуют. Возникающая проблема состоит в том, что, к примеру, Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине [math]2[/math], алгоритм не делал запрос о ребре [math](2, 3)[/math], так как у этому моменту вершина [math]3[/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

См. также

• Случайные графы