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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Sign fix)
(index fix)
Строка 68: Строка 68:
 
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
 
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
 
при <tex>t \thickapprox \gamma n</tex>, то есть:<br>
 
при <tex>t \thickapprox \gamma n</tex>, то есть:<br>
<tex>P_{n, p}(Y_{t_0} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty</tex>
+
<tex>P_{n, p}(Y_{t} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty</tex>
  
 
Так как по условию <tex>p = \dfrac{ c }{n}</tex>, то при  <tex>t \thicksim \alpha n</tex> выполнено:
 
Так как по условию <tex>p = \dfrac{ c }{n}</tex>, то при  <tex>t \thicksim \alpha n</tex> выполнено:
 
<tex> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</tex>
 
<tex> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</tex>
 
Применим центральную предельную теорему к
 
Применим центральную предельную теорему к
<tex>P_{n, p}(Y_{t_0} \le 0)\thickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>
+
<tex>P_{n, p}(Y_{t} \le 0)\thickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>
 
Пределы интегрирования в данном случае: от <tex>-\infty</tex> до <tex>\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}</tex>.
 
Пределы интегрирования в данном случае: от <tex>-\infty</tex> до <tex>\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}</tex>.
  

Версия 00:03, 25 июня 2020

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

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

Определение:
Простейший ветвящийся процесс. Пусть [math]Z_1,\dotsc Z_n,\dotsc [/math] — независимые пуассоновские величины[1] с одним и тем же математическим ожиданием [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]Y_i[/math] и [math]Z_i[/math] — количество активных и порожденных частиц в момент времени [math]t[/math], соответственно.

Теорема (1):
Пусть [math]\lambda \leq 1[/math]. Тогда с вероятностью 1 процесс [math]Y_t[/math] вырождается, т.е. [math]P(\exists t: Y_t = 0) = 1[/math].
Теорема (2):
Пусть [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[/math], зависящая от [math]c[/math], что а.п.н. (асимптотически почти наверное) размер каждой связной компоненты случайного графа не превосходит [math]\beta \ln n[/math].
Если же [math]c \gt 1[/math], то найдется такая константа [math]\gamma[/math], зависящая от [math]c[/math], что а.п.н. в случайном графе есть ровно одна компонента размера [math]\geq\gamma n[/math]. Размер остальных компонент не превосходит [math]\beta \ln n[/math].
Доказательство:
[math]\triangleright[/math]

Приведем здесь идеи[2], изложенные А.М. Райгородским, основанные на доказательстве[3] Р. Карпа. Такой формат позволит понять основные идеи и логику рассуждений. Строгий вариант приведен в [4].

Здесь и далее: [math]Binomial[/math] — биномиальное распределение.

Случай [math]c \lt 1[/math].

Положим [math]t_0=[\beta \ln n][/math], где [math]\beta[/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(\frac{1}{n}\right).[/math]

[math]P_{n, p}(Y_{t_0} \gt 0) = P_{n, p}(\xi_{t_o} \geq t_0) \thickapprox P_{n, p}(Binomial(n, 1 - (1 - p)^{t_0}) \geq t_0) \thickapprox[/math]
(с учетом асимптотики [math]1 - (1 - p)^{t_0} \thicksim pt_0) [/math]
[math]\thickapprox P_{n, p}(Binomial(n, pt_0) \geq t_0) \thickapprox[/math]
(с учетом центральной предельной теоремы)
[math] \thickapprox \int\limits_{\frac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \frac{1}{\sqrt{2\pi}}e^{-\frac{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].

В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что а.п.н. хотя бы в одном запуске возникнет гигантская компонента. Подробности можно найти в [4], мы же лишь поясним, откуда в текущей ситуации появляется [math]\gamma[/math] из формулировки теоремы 2 и почему она совпадает с одноименной константой из той же теоремы.

Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже при [math]t \thickapprox \gamma n[/math], то есть:
[math]P_{n, p}(Y_{t} \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} \le 0)\thickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).[/math] Пределы интегрирования в данном случае: от [math]-\infty[/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]. А это и есть уравнение из теоремы 2, если заменить [math]\lambda[/math] на [math]c[/math].
[math]\triangleleft[/math]

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

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

Лемма (1):
Пусть [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]
Теорема (4):
Пусть [math]p = \frac{d}{n}, d \gt 1[/math].
[math] \begin{equation*} \begin{cases} &\text{Найдутся такие $c_1, c_2$, что с $p \leq \frac{1}{n}$ $\exists cc: size(cc) \in (c_1\log n; c_2n)$;} \\ &\text{Число вершин в компонентах размера $O(\ln n)$ а.п.н. $\leq cn, c \lt 1$. Тогда с $p = 1 - o(1)$ существует компонента связности размера $\Omega (n)$;} \\ \end{cases} \end{equation*} [/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 \geq \frac{d}{n}:[/math] все неизолированные вершины оказываются в гигантской компоненте;
  • [math]p \geq \frac{\ln n}{2n}:[/math] в графе остаются только изолированные плюс гигантская компонента;
  • [math]p = \frac{\ln n}{n}:[/math] граф становится связным;
  • [math]p = \frac{1}{2}:[/math] [math]\forall \varepsilon \gt 0\;\exists C\subseteq G,\quad C[/math] — клика [math]: |C| = (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].

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

От поиска в ширину к ветвящимся процессам

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

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

Рассмотрим натуральное случайное число [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]t[/math], вычисляется по следующей формуле:
[math]a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}[/math]

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

Лемма (2):
Пусть [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].
Теорема (5):
Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть [math]f(x)[/math] — производящая функция числа потомков каждой вершины, а [math]k[/math] — ожидаемое количество потомков в каждой вершине. Тогда верно следующее:
[math] \begin{equation*} \begin{cases} k \le 1 &\text{—$\;$ вероятность исчезновения равна 1, если вероятность появления ровно одного ребенка равна $1$;}\\ k \gt 1 &\text{—$\;$ вероятность исчезновения — единственное решение $f(x) = x,\; x \in [0, 1)$;} \end{cases} \end{equation*} [/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]k[/math] — количество потомков вершины, а [math]m = f'(1)[/math], тогда [math]m = f'(1) = \sum_{i = 1..\infty}ip_i = E(k)[/math].
Кажется, что при [math]m \gt 1[/math] дерево будет расти вечно, так как каждая вершина в момент времени [math]j[/math] должна иметь потомков, однако при [math]p_0 \gt 0[/math] с положительной вероятностью у корня может вообще не быть потомков. В исходном [math]G(n,\frac{d}{n})[/math] [math]m[/math] играет роль [math]d[/math], ввиду того, что [math]d = E(k)[/math].

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

Пользуясь леммой 2 и теоремой 5, можно доказать, что:

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

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

Вывод

Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе [math]G(n, \frac{d}{n})[/math]. Рассчитав [math]p_0[/math] и [math]p_1[/math], можно сделать следующие выводы:
[math] \begin{equation*} \begin{cases} d \lt 1\;\vee\; d = 1\;\wedge\; p_1 \lt 1&\text{—$\;$ процесс завершится с вероятностью один;}\\ d = 1\;\wedge\; p_1 = 1&\text{—$\;$ процесс будет протекать бесконечно;}\\ d \gt 1&\text{—$\;$ вероятность исчезновения меньше единицы, но, если $p_0 = 0$, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;}\\ \end{cases} \end{equation*} [/math]

См. также

Литература

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