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

В теории случайных графов имеется точный ответ на этот вопрос (Bollobas 1985). Рассмотрим случайный граф G = G(N, p). Дополнительно рассмотрим небольшой граф F, состоящий из k вершин и l ребер. В принципе, случайный граф G может содержать несколько таких подграфов. Во-первых, определим, сколько таких подграфов существует. k вершин могут быть выбраны из общего числа N вершин   способами, а l ребер могут быть образованы с вероятностью p^l. К тому же, мы можем переставлять k вершин и в итоге получить k! новых графов (точное значение равно  , где a — количество взаимно изоморфных графов). Таким образом, ожидаемое количество подграфов F графа G составит   Подразумеваем, что реальное число таких подграфов может отличаться от E(X), но в большинстве случаев оно будет соответствовать данному выражению. Заметим, что подграфы не должны быть изолированными, то есть могут существовать вершины, имеющие свое начало в подграфе, а конец — вне его. Уравнение показывает, что если p(N) таково, что   при N → ∞, ожидаемое количество подграфов E(X) → 0, то есть, практически ни один из случайных графов не содержит подграфа F. С другой стороны, если  , количество подграфов будет конечным числом, определяемым  , что говорит о том, что эта функция может быть критической вероятностью. Правильность этого утверждения может быть проверена расчетами распределения количества подграфов P_p(X = r), что дает (согласно Боллобашу 1995):

Вероятность того, что  граф G содержит, по крайней мере, один подграф F, составляет в таком случае

что стремится к 1 при  увеличении c. Для значений p, удовлетворяющих   вероятность   стремится к 1, тем не менее, критическая вероятность того, что практически каждый граф содержит подграф с k вершинами и l ребрами, составляет P_p(X = r)

Некоторые важные свойства:

1. Критическая вероятность наличия дерева порядка k составляет 
2. Критическая вероятность наличия цикла порядка k составляет 
3. Критическая вероятность наличия полного подграфа порядка k составляет 

2.3 Распределение степеней

Эрдёш и Реньи (1959) были первыми, кто изучил распределение максимальных и минимальных степеней в случайном графе, полное распределение степеней было получено позднее Боллобашом (1981). В случайном графе с вероятностью связности p степень k_i вершины i следует биномиальному распределению с параметрами N−1 и p:

   (*)

Эта вероятность представляет количество способов, которыми k ребер могут быть проведены из определенной вершины: вероятность для k ребер составляет p^k, вероятность отсутствия дополнительных ребер составляет (1−p)^N−1−k и существует   эквивалентных способов выбора k конечных точек для этих ребер. Тем более, если вершины i и j являются различными, P(k_i = k) и P(k_j = k) близки к тому, чтобы быть независимыми случайными переменными. Для нахождения распределения степеней графа, необходимо изучить количество вершин со степенью k (обозначим X_k). Нашей основной целью будет определить вероятность того, что X_k принимает заданное значение P(X_k = r)

Согласно (*), ожидаемое количество вершин со cтепенью k составит  , где  . C хорошим приближением для распределения степеней в случайном графе подходит биномиальное распределение  , которое для больших N может быть заменено распределением Пуассона:

2.4 Связность и диаметр

Диаметр графа — наибольшее расстояние между двумя любыми его  вершинами. Точно выражаясь, диаметр несвязного графа (например, образованного несколькими изолированными кластерами) бесконечен, но может быть определен, как максимальный из диаметров его кластеров. Случайные графы имеют малый диаметр, при условии, что p мало. Причина этого в том, что случайный граф кажется расширяющимся: с большой вероятностью количество вершин с расстоянием l от выбранной вершины пропорционально ln(N) ⁄ ln(<k>), то есть, оно логарифмически зависит только от количества вершин. Диаметр случайных графов изучался многими людьми (Chang, Lu 2001). Общий вывод состоит в том, что для большинства значений p, практически все графы имеют один и тот же диаметр. Это значит, что, когда мы рассматриваем все графы с N вершинами и вероятностью связности p, диаметры могут лишь незначительно отличаться, обычно находясь около значения

2.5 Кластерный коэффициент

Если мы рассмотрим вершину  случайного графа и ее ближние  соседние вершины, вероятность того, что две соседние вершины соединены, равна вероятности того, что две  случайно выбранных вершины соединены. В итоге, кластерный коэффициент случайного графа составляет:

 

3. Модель Эрдеша-Реньи

Этот раздел мы посвятим описанию модели случайного графа, которая  возникла исторически первой. На рубеже 50-ых и 60-ых годов ХХ века эту модель предложили классики современной комбинаторики и теории вероятностей П. Эрдеш и А. Реньи (см. [1], [2], [3]). Отметим, что Эрдеш –

это, пожалуй, одна из самых  ярких фигур в математике ХХ века. Ему принадлежат сотни статей и задач, которые оказали огромное влияние на развитие многих математических дисциплин. Реньи также сыграл значительную роль в формировании венгерской вероятностной школы, и его именем назван математический институт в Будапеште.

Зафиксируем натуральное число n и рассмотрим множество V ={1,…,n}. Таким образом мы задали множество вершин случайного графа. Зададим полный граф K_n    на множестве вершин V . Пронумеруем ребра K_n : e ₁…,e_N , где . Зададим некоторое  и будем выбирать ребра из множества e ₁…,e_N    согласно схеме Бернулли. Мы получили случайный граф G = (V,E) . Формально выражаясь, мы имеем вероятностное пространство , в котором:

 Таким образом, в модели Эрдеша-Реньи каждое ребро независимо от других ребер входит в случайный граф с вероятностью p. Модель Эрдеша-Реньи на данный момент является самой изученной моделью случайных графов. Приведем несколько наиболее значительных с нашей точки зрения фактов о ней. Будем далее говорить, что случайный граф обладает некоторым свойством почти наверное, если вероятность обладания этим свойством стремится к единице.

Треугольники в случайном графе. Обозначим через T_3,n  случайную величину на пространстве G(n, p) , равную количеству треугольников в случайном графе G . Тогда верны следующие три теоремы:

Теорема 1 Пусть при . Если , то почти

наверное T_3,n = 0 (т.е. граф не содержит треугольников).

Теорема 2 Пусть , где c > 0 – константа. Тогда T_3,n     имеет

 

 асимптотически пуассоновское распределение с параметром .

_{Теорема 3 Пусть при . Тогда если , то}

• Связность случайного графа. Одно из самых интересных свойств модели Эрдеша-Реньи – наличие фазового перехода:

Теорема 4 Пусть . Если c >1, то почти наверное случайный граф

связен. Если c <1, то почти наверное случайный граф связным не является.

Теорема 5 Пусть  . Тогда при любом c <1 существует такая

константа b = b(c) > 0, что почти наверное каждая компонента случайного графа имеет не более blnn вершин. При любом c >1 существует такая константа g = g(c) (0,1) , что почти наверное среди компонент случайного графа есть одна ( гигантская), число вершин которой не меньше gn .

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

 

4 Наблюдения Барабаши-Альберт

 

В своих статьях [5], [6] и [7] авторы заметили следующие закономерности в веб-графе (графе, вершинами которого являются сайты, а ребра соответствуют ссылкам):

• Веб-граф разрежен (на n вершинах у него mn ребер, m N )

 

• Веб-граф подчиняется феномену «малого мира» (его диаметр 5-7 )

• Он подчиняется степенному закону:

На основании своих наблюдений авторы ввели понятие предпочтительного присоединения (preferential attachment). Рассмотрим процесс генерации

графа. На n -ом шагу мы добавляем новую вершину n с m ребрами, инцидентыми ей, причем вероятность ребра к вершине i пропорциональна степени вершины i (см. Рисунок 1):

 

 

 

 

 

 

 

 

Рис. 1:Добавление вершины на n -ом шагу.

 

Основных проблем со спецификацией модели Барабаши-Альберт две.

 

Во-первых, результирующий граф зависит от начального параметра m . Например, при m =1 модель Барабаши-Альберт описывает генерацию дерева, если начальный граф – тоже дерево. Если начальный граф несвязный, то и все последующие тоже будут таковыми.

 

Во-вторых, трудность с предпочтительным присоединением заключается в случайном выборе вершин (если m ≥2 ), к которым присоединится новая вершина. Например, верна следующая теорема:

 

Теорема 1 Пусть f (n),n≥ 2 – произвольная целочисленная функция, такая что: f (2) = 0 , f (n)≤ f (n+1)≤ f (n)+1 для любых n≥ 2 и при . Тогда существует такой процесс генерации случайного графа T⁽ⁿ⁾ , удовлетвовряющий (1), что с вероятностью 1 в T⁽ⁿ⁾ ровно f (n) треугольников для достаточно больших n .

 

Говоря менее формально, теорема 1 говорит о том, что если вы хотите иметь в графе с n вершинами logn треугольников, есть модель Барабаши-Альберт,

 

которая выдаст такой результат.

 

5 Модель Боллобаша-Риордана

 

5.1. Генерация графа

 

Боллобаш и Риордан предложили следующую спецификацию модели Барабаши-Альберта. Построим последовательность случайных графов {Gⁿ}, в которой у графа с номером n число вершин и ребер равно n . Преобразуем ее в последовательность {Gⁿ}, в которой у графа с номером n число вершин ^{равно n , а число ребер равно kn,k N}

Пусть G¹ = ({1},{(1,1)}) . Предположим, что граф уже построен. Ребер и вершин у него по n-1. Добавим вершину n и ребро (n,i), у которого

 

i {1,…,n}. Ребро (n,n) появится с вероятностью , ребро (n,i) – с вероятностью , причем deg(i) – степень вершины i в графе .

 

Распределение вероятностей задано корректно, т.к.

 

Т.о., граф Gⁿ     построен, и он удовлетворяет принципу предпочтительного присоединения. Теперь перейдем к , у которого по kn вершин и ребер.

Делим множество его вершин на последовательные куски размера k : {1,…,k}, {k+1,…,2k},…,{k(n-1)++1,…,kn}.

 

Каждый кусок примем за новую вершину, а ребра сохраним (ребра внутри куска становятся кратными петлями, ребра между разными кусками – кратными ребрами).

5.2 Основные результаты

 

Оказалось, что модель Боллобаша-Риордана довольно хорошо сходится с эмпирическими данными. За время изучения этой модели было получено огромное множество полезных результатов, мы же приведем только некоторые из них.

Теорема 1. Для любого k ≥2 и любого e > 0

 

При n:10⁷ , что соответствует Интернету образца 1999 года, имеем в (2)

,что совпадает с наблюдениями Барабаши-Альберт.

Теорема 2. Для любого k ≥1 и для любого   

 

.

где     - количество ребер, имеющих вершину i своим левым концом в графе . Т.е мы получили степенной закон . От условия смогли избавиться сравнительно недавно, а для того чтобы получить степень 2.1 (соответствующую реальной степени веб-графа несколько лет назад) вместо 3, надо отойти от модели Боллобаша-Риордана.

Пусть H – фиксированный граф. Обозначим через случайную величину, равную количеству подграфов графа , изоморфных графу H . В работе [9] приведены результаты о математическом ожидании этой величины.

Теорема 2 Пусть k≥2 . Пусть также K₃ – полный граф на трех вершинах. Тогда

 

при .

 

Теорема 3 Пусть фиксированы k ≥2 и l ≥3. Пусть также C_l – цикл на l

 

вершинах. Тогда

при , где c_k,l – положительная константа. Более того, при имеем c_k,l = (k^l ) .

А. Рябченко и Е. Самосват из Яндекса в модели, близкой к модели Боллобаша-Риордана, установили следующий факт:

Теорема 4 Пусть задан граф H , степени вершин в котором равны

d₁ ,…,d_s . Обозначим через #(d_i = m) число вершин в H , степень каждой из которых равна m . Тогда

Зависимость от k занесена в константу .

 

По (6)

что согласуется с теоремой 2. А для K₄    теорема 4 говорит, что его средняя частота в веб-графе постоянна. Т.о., «тетраэдров» в веб-графе почти нет. Следует отметить, что последнее утверждение имеет мало общего со свойствами реального веба: в нем встречаются и тетраэдры, и клики большей мощности. Это связано с действием спамеров и агентств по раскрутке сайтов (групп в социальных сетях). Спам в модели Боллобаша-Риордана не учитывается.

6. Модель LCD [10]

Выделим в пространстве ось абсцисс и зафиксируем на ней 2n точек: 1, 2, 3,…, 2n . Разобьем эти точки на пары, и элементы каждой пары соединим дугой, лежащей в верхней полуплоскости. Полученный объект назовем линейной хордовой диаграммой (LCD). Дуги в LCD могут как пересекаться, так и лежать друг под другом, но не могут иметь общих вершин. Количество различных диаграмм равно

 

_{По каждой диаграмме построим граф с} n _{вершинами и} n _{ребрами. Процесс} построения описан в алгоритме 1 и показан на рис. 2.

 

 

 

 

 

_{Рис. 2: LCD модель}

 

 

 

 

 

 

 

 

Алгоритм 1

 

Теперь считаем LCD случайной, т.е. полагаем вероятность каждой диаграммы равной 1/l_n , где l_n      – общее число диаграмм из (7). Т.о. мы получаем случайные графы. В [7] показано, что такие графы по своим вероятностным характеристикам почти неотличимы от графов   (см. предыдущий пункт). Графы с n вершинами и kn ребрами получаются так же, как и в модели Боллобаша-Риордана.

7. Модель Buckley-Osthus

 

Buckley, Osthus и другие исследователи предложили модификацию модели Барабаши-Альберт,  в которой вершины обладают «изначальной привлекательностью» («initial attractiveness»): вероятность того, что старая вершина будет выбрана соседом новой вершины пропорциональна ее входящей     степени     (in-degree)    плюс     константе,     т.е.     «изначальной привлекательности», т.е. am , где m – число ребер, входящих в новую