Случайные графы и их некоторые асимптотические свойства тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Миронов Максим Сергеевич

• Миронов Максим Сергеевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Миронов Максим Сергеевич

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

1.2 Пороговая вероятность

1.3 Дистанционный граф

1.4 Модель пространственного предпочтительного соединения SPA

1.5 Разбиение графа на кластеры желаемых размеров

1.6 Научная новизна

1.7 Апробация полученных результатов

Список иллюстраций

2 Диаметр случайного дистанционного графа

2.1 Формулировки результатов

2.2 Доказательства результатов

2.2.1 Доказательство теоремы

2.2.2 Доказательство теоремы

2.2.3 Доказательство теоремы

2.3 Заключение

3 Кластерный коэффициент в модели SPA

3.1 Определения и свойства

3.2 Формулировка основного результата

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

3.4 Заключение

4 Разбиение графа на кластеры желаемого размера

4.1 Алгоритм и его практическое применение

4.1.1 Определения и постановка задачи

4.1.2 Описание алгоритмов

4.1.3 Вычислительная сложность для mean-field SBM графов

4.1.4 Численные эксперименты

4.2 Марковские цепи

4.2.1 Определения и базовые утверждения

4.2.2 Быстрое смешивание при высокой температуре

4.3 Исследование стационарного распределения

4.3.1 Эффективность стационарного распределения для усредненной энергии

4.3.2 Эффективность стационарного распределения в модели ББМ

4.4 Заключение

Публикации

Литература

Глава

Введение диссертации (часть автореферата) на тему «Случайные графы и их некоторые асимптотические свойства»

Введение

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

Теория случайных графов зародилась на рубеже 50-х и 60-х годов XX века и стала одной из многих важнейших прикладных и фундаментальных направлений классической теории графов. Впервые термин случайный граф был предложен совместно П.Эрдешем и А.Реньи в 1959г [31] и с тех пор эта наука активно развивалась, результатом чего стало множество замечательных исследований, появление множества различных моделей случайного графа и их разнообразные применения в тех или иных исследованиях (см. [32, 33, 21, 37, 30]).

Когда мы говорим "случайный граф", мы, конечно, подразумеваем наличие некоторого вероятностного распределения на некотором множестве элементарных исходов. Соответственно, свойства случайного графа как случайного объекта будут интересовать нас с вероятностной точки зрения. В общих словах можно сказать, что изучение свойств случайного графа сводится к тому, чтобы понять, при каких условиях на параметры графа и на вероятностное распределение то или иное свойство имеет место с достаточно большой вероятностью.

Задание множества элементарных исходов и соответствующего распределения и определяет ту или иную модель случайного графа. Классическая модель случайного графа, введенная Эрдешем и Реньи, представляет собой следующее. Пусть у нас имеется полный граф на п вершинах Кп = (Уп, Еп), где множество вершин мы представляем себе как Уп = {1, 2,... , п}. Тогда, в сответствии с коломогоровским определением вероятностного пространства, зададим , —a, Рп ):

= {Н | Н остовный подграф графа Кп}

~р _ 2^п

- п 2

Рп(Н = (Уп, Е))= р|Е|(1 - р)|Еп|-|Е|,

где р Е [0,1] ив дальнейшем для краткости мы вместо Рп (•) будем писать Р(-). Смысл этого определения в том, что каждое ребро графа Кп присутствует в случайном графе независимо от

других с вероятностью р. Перефразируя, можно сказать, что случайных граф — это результат серии испытаний Бурнулли, где над каждым ребром подбрасывается монетка с, возможно, смещенным центром тяжести. Случайный элемент, полученный из такого распределения, мы будем обозначать 0(п,р).

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

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

Существует разнообразное множество моделей случайных графов, какие-то из них будут рассмотрены в данной работе. Ключевым объектов для изучения случайных графов является понятие пороговой вероятности, которое будет рассмотрено далее (см, например, [23]).

1.2 Пороговая вероятность.

Пусть имеется множество Г, состоящее из N элементов. Для р Е [0,1] случайным элементом Г(р) называется элемент, который принимает значение в множестве всех подмножеств Г и имеет распределение

Р(Г(р) = 0) = р1°1(1 — р)м-14

Данная модель называется биномиальной. Очевидно, случайный граф в модели Эрдеша-Реньи попадает под данное определение, если под вложением одного графа в другой понимать вложение их множества ребер при общем множестве вершин. Свойство Q множества Г отождествим с соответствующим множеством подмножеств Г. Так, для Г = Кп в свойство "быть связным" попадают связные остовные подграфы графа Кп. Отметим, что для всякой системы подмножеств Q выполнено

Р^) = Р(Г(р) ЕQ) = £ Р(0).

сея

Свойство Q назовем монотонно возрастающим, если для всякого А Е Q и А С В следует, что В € Г. Свойство Q называется монотонно убывающим, если, соответственно, из того, что А Е Q и А 3 В следует, что В Е Q. Очевидно, что если Q — монотонно возрастающее свойство, то 2Г \ Q является монотонно убывающим.

Объектом исследования в данной ситуации является не одно отдельно взятое множество Г со своим случайным элементом, а последовательность таких множеств. Пусть для каждого п задано множество Гп мощности N(п), N(п) ^ то при п ^ то. В такой постановке естественно рассмотреть р = рп Е [0,1] как функцию от п (далее иногда мы будем писать просто р, если

будет понятно, что речь идет именно о функции от п). Таким образом, мы получаем последовательность случайных элементов {Гп(р),п Е М}. Пусть теперь помимо этого нам дана последовательность {2п,п Е М}, <2п Е 2Гп, где <2^ является монотонно возрастающим свойством для каждого к. Функция р*п Е [0,1] называется пороговой вероятностью для {2п,п Е М}, если выполнено:

1. для любой функции р = рп, такой что рп ^ р*п, верно, что

Р(Гп(р) Е 2п) ^ 0 при п ^ то;

2. для любой функции р = рп, такой что рп ^ р*п, верно, что

Р(Гп(р) Е 2п) ^ 1 при п ^ то

В случае, если для последовательности свойств {2п,п Е М} выполнено

Р(Гп(р) Е 2п) ^ 1 при п ^ то,

будем говорить, что это свойство выполняется асимптотически почти наверное или а.п.н.. Все результаты, которые будут представлены в этой работе, носят асимптотический характер. Для множества Б мы говорим, что почти все элементы из Б обладают некоторым свойством Р, если число элементов Б, не удовлетворяющих свойству Р, есть о(|Б|). Под ш = ш(п) будем подразумевать некоторую функцию, сколь угодно медленно стремящуюся к бесконечности. Как правило, неравенства будут рассматриваться при п ^ то, то есть будет полагаться, что они выполнены начиная с некоторого момента.

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

Теорема (Б. Баллобаш, Э. Томассон [21]). Пусть для каждого п задано множество Гп мощности N(п),Ы(п) ^ то при п ^ то, а также монотонная система <2п подмножеств Гп. Тогда для последовательности {2п,п Е М} существует пороговая вероятность р = рп

Для исследования случая, когда рп по порядку совпадает с рп, естественно ввести понятие точной пороговой вероятности. Функция р*п называется точной пороговой вероятностью для последовательности монотонно возрастающих свойств {2п,п Е М}, если

1. для любой функции р = рп, такой что при достаточно больших п выполнено рп < ср*п для некоторого с < 1, верно, что

Р(Гп(р) Е 2п) ^ о при п ^ то;

2. для любой функции р = рп, такой что при достаточно больших п выполнено рп > срП для некоторого с > 1, верно, что

Р(Гп(р) е Я,п) ^ 1 при п ^ ТО

Вернемся теперь к задаче. Очевидно, свойство связности является монотонно возрастающим. Оказывается, для задачи связности графа С(п,р) существует точная пороговая вероятность, этот результат можно сформулировать в следующей теореме.

Теорема (Б. Баллобаш, [21]). Точная пороговая вероятность для свойства связности в графе С(п,р) равна

* 1п п

рп = "V

1.3 Дистанционный граф.

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

С(п, г, в) = (V(п, г), Е(п, г, в)).

Дадим определения:

V(п, г) = < х = (хь • • •, Хп) | V х е {0,1}, ^

п

Хг = Г

г=1

Е(п, Г, в) =

п

(VI, ^2) | VI = • • ,<), = (V1,. • . X), VI, ^2 е V(п,г), ^ VIV

г=1

Здесь, разумеется, 0 ^ в < г < п, и данное определение равносильно следующему: вершины графа — г-элементные подмножества множества {1,- • • ,п}, а ребра — пары множеств, пересекающихся по в элементам. Очевидно, что данный граф является дистанционным. Отметим также, что С(п, 1, 0) — полный граф, а С(п, г, 0) — Кнезеровский граф. Приведенный выше граф играет важную роль в комбинаторной геометрии (см. [54]) и теории кодирования (см. [16]). Мы же приведем здесь лишь одно из его применений для большей наглядности.

в

Задача о хроматическом числе пространства является одной из наиболее популярных и известных задач комбинаторики. Заметим сразу очевидное неравенство

Х(Еп) ^ х(О),

где О — дистанционный граф в пространстве Кп. Более того, справедлива теорема

Теорема (П.Эрдеш, Н.Де Брейн, [28]). Существует такой конечный дистанционный граф О = (V, Е), V С Еп, что справедливо

Х(Еп) = х(О).

Отметим также очевидное соотношение для графа О = (V, Е):

IV |

х(О) ^

а(О)

где а(О) — число независимости графа О, равное наибольшему числу вершин, попарно несоединенных ребрами. Таким образом, для получения нижней оценки на хроматическое число пространства достаточно оценить число независимости дистанционного графа. Сперва в 1972г. Ж.Надь доказал следующую теорему:

Теорема (Ж.Надь, [45]).

п - 2, п = 4к + 2 а(О(п, 3,1)) = <( п - 1, п = 4к + 1 . п, п = 4к

Таким образом, была получена полиномилальная нижняя оценка на хроматическое число пространства Кп:

п

хОП > -¡О^ = ~(1 + 0(1)) = ¥(! + о'1».

а(О(п,г, в)) п 6

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

Теорема (Франкл, Уилсон, [35]).

х(Еп) ^ (1.207... + о(1))п

Теорема (А.Райгородский, [64]).

x(Rn) ^ (1.239...o(1))n

Если теперь положить Гп = G(n, r, s), то случайный элемент Гп(р) будем называть случайным дистанционным графом, который в дальнейшем будем обозначать Gp(n, r, s). Будем также считать, что r = rn, s = sn,p = p(n) — параметры графа являются функциями от n. В настоящей работе мы будем исследовать случайный дистанционный граф с точки зрения его диаметра и дадим практически исчерпывающее описание случаев, в которых граф Gp(n, rn, sn) а.п.н. имеет диаметр больше двух, и случаев, в которых граф Gp(n, rn, sn) а.п.н. имеет диаметр один или два. Подобная задача полностью решена в модели Эрдеша-Реньи, и справедлива следующая теорема.

Теорема (Б. Боллобаш). Пусть c > 0, d = dn ^ 2. Определим p = p(n, c, d), 0 < p < 1 как

pV-1 = ln (n2

Предположим также, что щрпп ^ Тогда для графа G(n,p) справедливо:

lim P(Diam(G) = d) = e-2, lim P(Diam(G) = d + 1) = e-2.

1.4 Модель пространственного предпочтительного соединения SPA

В целом, эволюция сложных сетей привлекает большое внимание в последние годы. Исследования сетей из реального мира показали, что такие сети обладают некоторыми типичными свойствами: небольшой диаметр, особое распределение степеней вершин, кластерная структура и другие [27, 47, 59]. Большое количество различных моделей графов было предложено для того, чтобы учесть и предсказать подобные количественные и топологические особенности растущих сетей в реальном мире [20, 22].

Наиболее изученное свойство сложных сетей это распределение степеней вершин в них. Для большинства изученных примеров такое распределение подчиняется степенному закону с параметром y, который обычно находится в промежутке (2, 3) [15, 34, 48].

Другим важным свойстом сетей из реального мира является их кластерная структура. Наличие такой структуры сущесственно влияет на многие процессы, протекающие в таких сетях, например распространение комьютерных и человеческих вирусов [53]. Одной из способов измерить и оценить кластерную структуру является кластерный коэффициент, который в первом

приближении представляет собой вероятность того, что два соседа некоторой вершины соединены между собой. Существует два хорошо известных определения кластерного коэффициента: глобальный и средний локальный коэффициенты (в дальнейшем мы введем формальные определения).

Мы изучим кластерные свойства модели предпочтительного пространственного присоединения SPA (Spatial Preferential Attachment), которая оказывается хорошим приближением некоторых реальных сетей. Эта модель ествественным образом сочетает в себе геометрические свойства и предпочтительное присоединение. Впервые данная модель была предложена в работе [11]. Мотивация к созданию этой модели понятна, а именно, она отражает три основных принципа:

• Вершины с большим влиянием (с большой степенью) со временем имеют больше шансов стать еще влиятельнее, чем вершины меньшей степени.

• Со временем все вершины теряют свое влияние на другие вершины, поскольку становятся нерелевантны и устаревают.

• Вершина, которая оказалась близко к некоторой другой вершине v в смысле определенной метрики, имеет шанс попасть под влияние v; вершина, оказавшаяся далеко от вершины v, не может попасть под ее влияние.

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

Было показано, что графы в SPA модели во многом схожи с графами из реальных сетей. Например, в [11] было доказано, что степени вершин подчиняются степенному закону. Однако, кластерный коэффициент как функция от степени вершины, который является очень важной характеристикой, не был ранее изучен. В данной работе представлены теоретические результаты о поведении среднего локального кластерного коэффициента как функции от степени вершины.

1.5 Разбиение графа на кластеры желаемых размеров

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

Говоря о возможных подходах к задаче кластеризации графа, необходимо упомянуть следующие. Первый большой класс алгоритмов основан на спектральных свойствах матрицы смежности графа и его лапласиане (см. [7, 62] и упомянутые там ссылки). Второй класс методов основывается на случайных блужданиях по графу (см. [13, 12, 24, 46, 52] как примеры наиболее репрезантивных работ в этом направлении). Наконец, третий класс методов основан на оптимизации некоторой целевой функции, такой как вероятность [50, 42], модулярность [49] или энергия [17, 56]. Отдельно отметим подходы, описанные в работах [18, 60], как наиболее продвинутые алгоритмы для обнаружения сообществ. Интересно, что многие из подходов могут быть рассмотрены как примеры гедонистической игры [14]. Подход, рассмотренный нами ниже, основан на оптимизации функции энергии графа.

В этой главе мы рассматриваем задачу кластеризации графа с заданным количеством кластеров и их желаемыми размерами. Одной из мотиваций для данной постановки может быть задача алокации серверов в нескольких больших вычислительных кластерах, где мы хотим связанные друг с другом объекты расположить в одном кластере для минимизации издержек при обмене сообщениями. Эта задача отличается от стандартной задачи нахождения сообществ в графе. Для решения нашей задачи мы применяем некоторые идеи, позаимствованные из метода Glauber Dynamics (см. [41]). В то же время мы не требуем никакой дополнительной информации о вершинах, кроме их ребер, поэтому задача носит характер обучения без учителя. Мы предлагаем алгоритм для решения задачи и оцениваем время его работы для достижения почти полного восстановления кластеров в модели mean-field SBM. Достоинством алгоритма является то, что он имеет локальную природу, что значит, что он может быть эффективно распределен без необходимости синхронизации. Предложенный алгоритм имеет сравнимое качество работы на модельных графах с алгоритмом спектральной кластеризации, однако значительно превосходит его в скорости работы: (O(nln(n)degav(G)) вместо O(n3)), а также, как было отмечено, может быть распределен на произвольное количество машин, что на практике существенно ускоряет время работы.

Помимо предложенного алгоритма, также будет показано, что ассоциированная с алгоритмом марковская цепь обладает интересными свойствами. Будет показано, что само по себе стационарное распределение данной марковской цепи при некоторых ограничениях почти наверное дает конфигурации, доставляющие хорошую кластеризацию для случайного графа с блоками (SBM). Однако, пространство состояний цепи экспоненциально по размеру исходного графа, поэтому сэмплирование из стационарного распределения затруднительно. Мы покажем некоторые достаточные условия, при которых можно осуществить сэмплирование из распределения, близкого к стационарному. К сожалению, режим, при котором мы можем показать эффективность распределения с точки зрения решения задачи, и режим быстрого смешивания не пересекаются. Однако, эти результаты носят красивый теоретический характер, позволяют продемонстрировать мотивацию для применения предложенного метода и апробированы на практике.

1.6 Научная новизна

Все результаты новы, ниже представлено их краткое описание

• Предложена точная пороговая вероятность для случайного дистанционного графа Gp(n,r, s) и свойства "иметь диаметр не более двух".

• Для модели предпочтительного пространственного присоединения показано, что локальный кластерный коэффициент как функция от степени вершины k ведет себя как 0(1/k) для k из широкого промежутка.

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

• Для марковской цепи, ассоциированной с предложенным алгоритмом, показаны достаточные условия для быстрого смешивания, то есть представлен режим, в котором стационарное распределение хорошо аппроксимируется за O(n2 log n) шагов алгоритма, где n - размер графа и где каждый шаг имеет амортизированную сложность равную средней степени вершины в графе O(degav(G)).

• Для марковской цепи, ассоциированной с предложенным алгоритмом, показано, при каких достаточных условиях на параметры выполнено, что для конфигураций, доставляющих почти полное восстановление кластеров в случайном графе с блоками, их вероятностная мера равна 1 — o(1) в стационарном распределении исследуемой марковской цепи.

1.7 Апробация полученных результатов

Результаты этой работы были представлены на следующих семинарах и конференциях

• 17th Random Structures & Algorithms conference. "Diameter of random distance graph", Питсбург, США, 2015.

• 13th Workshop on Algorithms and Models for the Web Graph. "On mixing in pairwise Markov random fields with application to social networks ", Монреаль, Канада, 2016.

• Graph seminar at Ryerson University. "On Mixing in Pairwise Markov Random Fields with Application to Social Networks", Торонто, Канада, 2017.

• 15th Workshop on Algorithms and Models for the Web Graph. "Clustering Properties of Spatial Preferential Attachment Model", Долгопрудный, Россия, 2018.

• 25th International Conference on Pattern Recognition (ICPR). "Cluster-size constrained network partitioning", Милан, Италия, 2021.

Список иллюстраций

4.1 Алгоритм для выявления кластеров ......................................................58

4.2 Количество шагов первого раунда Алгоритма 4.1 для SBM и mean-field SBM ... 65

4.3 Траектории доли черных вершин в первом кластере ..................................66

4.4 Сравнение первого раунда (Algorithm 1) и обоих раундов (Algorithm 2) ............67

4.5 Точность Алгоритма 4.1 в различных режимах при n = 10000, а =1................68

4.6 Точность спектрального алгоритма в различных режимах при n = 10000, а =1 . 68

4.7 Разница в точности для спектрального и предложенного двухфазового алгоритма 69

4.8 Точность Алгоритма 4.1 в различных режимах при n = 10000, а = 3................69

4.9 Траектории с разбалансированными размерами кластеров............................70

4.10 Алгоритм для марковской цепи X........................................................72

Глава 2

Диаметр случайного дистанционного графа

Результаты данной главы были опубликованы в работе [6].

2.1 Формулировки результатов

Отметим прежде всего, что случай гга < тривиален, поскольку тогда в графе С(п, гга, зга) найдутся две несмежные вершины, у которых нет общего соседа, и, как следствие, диаметр случайного графа СРп (п,гга,зга) будет заведомо больше двух. Мы представим три теоремы: первая описывает случай гга > 2зга, две другие посвящены случаю гга = 2зга.

Теорема 2.1. Пусть дана последовательность случайных элементов СРп(п, гп, зга), где гга : N ^ N и зга : N ^ N — такие функции натурального аргумента п, что гга > 2^га и гга = о (-^п) при п ^ то. Тогда свойство "Б1аш (СРп(п,гга,зга)) ^ 2" имеет точную пороговую вероятность

*

-Рга

\

2г„, 1п ^

(2.1)

гга\ V п - 2г„

^га/ \гга 2^га

Иными словами:

1. если при всех достаточно больших п выполнено ^ срП для некоторого с > 1, то диаметр случайного графа СРп(п,гга,зга) а.п.н. не больше двух;

2. если при всех достаточно больших п выполнено ^ срП для некоторого с < 1, то диаметр случайного графа СРп(п,гга,зга) а.п.н. больше двух.

Далее мы убедимся в том, что рП ^ 0 при п ^ то. Заметим также, что при гга = 1, зга = 0 выполнено

* / 21п п

—,

и это отлично согласуется с классическими результатами для модели Эрдеша-Реньи (см. [21]).

Теорема 2.2. Пусть дана последовательность случайных элементов СРп(п,г*,г*/2), где гга : N ^ N — такая функция натурального аргумента п, принимающая только четные значения, что гга = о (д/П) при п ^ то и для некоторой стремящейся к бесконечности функции /„, выполнено неравенство

Гга -- 1п1п п + —— 1п1п1п п + /га. (2.2)

1п 4 1п 2

Тогда свойство "Б1аш (СРп (п,г*,г*/2)) ^ 2" имеет точную пороговую вероятность

/пг2 1п Р* = А/ПГ" г" .

Отметим, что пороговая вероятность, заявленная в теореме 2.2, асимптотически эквивалентна пороговой вероятности из теоремы 2.1 при г* = 2зга. В разделе 2.2.2 мы также убедимся в том, что р* ^ 0 при п ^ то, и это не будет, конечно, прямым следствием аналогичного факта из раздела 2.2.1, да и условия теоремы 2.2 слабее условий теоремы 2.1: г* = о (у^) против г* = о (л^п) .

Следующий результат дает нам понимание того, что происходит при г*, меньших, чем те, о которых шла речь в теореме 2.2.

Теорема 2.3. Пусть дана последовательность случайных элементов СРп (п,г*,г*/2), где г* : N ^ N — такая функция натурального аргумента п, принимающая только четные значения, что для некоторой стремящейся к бесконечности функции /* выполнено неравенство

г* ^ -—- 1п 1п п + -— 1п 1п 1п п — /„. 1п 4 1п 2

Тогда свойство "Б1аш(СРп(п,г*,г*/2)) ^ 2" имеет точную пороговую вероятность

* 1 р* = 1.

Иными словами: если при всех достаточно больших п выполнено рга ^ с для некоторого с < 1, то диаметр случайного графа СРп (п, г*,г*/2) а.п.н. больше двух.

2.2 Доказательства результатов

Дабы не нагромождать выражения, далее везде будем писать просто г, в и р вместо г*, в* и

Р*.

2.2.1 Доказательство теоремы 2.1

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

Пусть — множество всех пар вершин из V(п, г). Тогда 1= 1 ^ ^ (^ ^ — 1). Для ] Е

обозначим и вершины из V(п, г), соответствующие . Пусть ( — количество общих соседей для и ^2.

Лемма 2.1. Для любого ] Е верно, что

/г\ 2 /п — 2г

(3 £ (шт := — 2в

Кроме 'того, если в = 0 и ^ П = 0, то существует такая стремящаяся к бесконечности функция ш, что

( > (1)^п — 2г)ш*

Доказательство. Пусть Ц1 П ^'2| = Ь. Тогда

( = УМ Л (г — Л ( п — 2г + Ь 3 = ¿0 ^Дв — V \г — 2в + ^

Если в = 0, то, очевидно,

п — 2г 3 V г )

и все в порядке. Поэтому будем считать ниже, что в > 0. Рассмотрим три случая.

/г\ 2 (п — 2г\

1. Если Ь = 0, то = ( I ( I = (ш;п.

\в/ \г — 2в/

2. Пусть 0 < £ < в. Рассмотрим слагаемое при г = Ь. Тогда

2

, , г — Ь\ /п — 2г + А /А п — 2г

^ ■ I ■ ....

1в — Ь/ \г — 2в + Ь/ \в/ \г — 2в

//г —

в - Ь

п — 2г + Ь г — 2в + Ь

п 2г

\ \в/ / \г — 2в

п — 2г + Ь

( , (г — Ь)! в!(г — в)!\2 ^ г — 2в + Ь

(в — Ь)!(г — в)! г! ) (п — 2г

г — 2в

, .'(г — Ь)! в! )2 пг-2*+ (г — 2в)!

■ (в—(г — 2в + Ь)! + о(1)) ^

1 \ 2 * 1 \ п

^ 4ш1п ( ) ~ (1 + 0(1)) = ^т1п ( — ) (1 + 0(1)) = 4ш1пШ ^

гп г*

3. Пусть в ^ £ < г. Рассмотрим слагаемое при г = в. Получаем

. А /г — А Vп — 2г + А п — 2г +

4 > 1.в)( 0 ) ( г-в ) Н г — в ) = ^ п-2г

п — 2г + £ г — в

п'

в / \ г — 2в

(г _ 2я)' 1 п

( )! —(1 + 0(1)) ^ 4ш1п^(1 + 0(1)) ^

(г — в)! п'-25 г25

35

^ 4ш1п - (1 + о(1)) = 4ш1пШ ^

Так как 0 ^ £ < г, мы рассмотрели все случаи. Из пунктов 2 и 3 следует, что 4 ^ 4т1пш при

П ^2 = 0. Отсюда и из пункта 1 мы получаем, что ф ^ 4ш1п при достаточно больших п, и

□

лемма доказана.

Замечание 2.1. Условие г = о(-^п) нужно только для доказательства этой леммы. В дальнейших рассуждениях везде будет достаточно требовать г = о(у/п), этим мы воспользуемся при доказательстве теорем 2.2 и 2.3.

Далее нам потребуется стремление р* к 0, покажем это. Действительно,

*

рга

\

2г 1п * -'- <

п — 2г г — 2в

\

2г 1п п I л/п 1п п

^ </---► 0.

п — 2г г — 2в

п — 2г

Замечание 2.2. Здесь мы воспользовались тем, что г > 2в, и это единственное место в данной теореме, где это используется. Таким образом, дальнейшие рассуждения верны и для г = 2в, при условии, что р* стремится к 0. Как будет показано в доказательстве теоремы 2.2, это условие есть не что иное, как условие (2.1) из формулировки теоремы 2.2.

Вернемся к нашей последовательности случайных графов СР(п, г, в). Зафиксируем конкретное достаточно большое п. Пусть — случайная величина, равная числу пар вершин, между которыми нет ребра и цепи длины 2. Тогда

Р(Б1аш(СР(п, г, в)) ^ 2) = Р(£„ = 0).

Пусть р(^1,^2) — кратчайшее расстояние в графе между вершинами и Тогда

С™ ^ ] !з,

з'е^

где 13 — индикатор события

А = |р(л,^2) > 2}.

Если вершины ^ и несмежны в графе С(п, г, в), то

р(А ) = (1 — р2)^,

иначе

Р(Аз ) = (1 — р2)^ (1 — р).

Следовательно,

Р(Аз) ^ (1 — р2)^'.

В силу леммы 1 получаем, что для любого ] Е выполнено неравенство

Р(А,-) ^ (1 — р2)<1п.

Пусть Е£га — математическое ожидание случайной величины Сп. Тогда

ЕС™ = £ Е1з = £ Р(Аз) ^ £ (1 — р2)^п = |Л|(1 — р2)^п. з'е^ з'е^п з'е^п

Пусть

Л = О Е Л | Л П ^ = 0}.

/ п \ / п — г \

Список литературы диссертационного исследования кандидат наук Миронов Максим Сергеевич, 2022 год

Литература

[7] Abbe, E. (2018). Community detection and stochastic block models. Foundations and Trends in Communications and Information Theory, 14(1-2):1-170.

[8] Abbe, E., Bandeira, A. S., and Hall, G. (2016). Exact recovery in the stochastic block model. IEEE: Transactions on Information Theory, 62(1).

[9] Abbe, E., Bandeira, A. S., and Hall, G. (2016). Exact recovery in the stochastic block model. IEEE Transactions on Information Theory, 62(1):471-487.

[10] Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670-688.

[11] Aiello, W., Bonato, A., Cooper, C., Janssen, J., and Pralat, P. (2009). A spatial web graph model with local influence regions. Internet Mathematics, 5:175-196.

[12] Avrachenkov, K., Chamie, M., and Neglia, G. (2014). Graph clustering based on mixing time of random walks. IEEE International Conference on Communications, ICC 2014, pages 4089-4094.

[13] Avrachenkov, K., Dobrynin, V., Nemirovsky, D., Pham, S., and Smirnova, E. (2008). Pagerank based clustering of hypertext document collections. Proceedings of the 31st International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2008, Singapore, July 20-24.

[14] Avrachenkov, K. E., Kondratev, A. Y., Mazalov, V. V., and Rubanov, D. G. (2018). Network partitioning algorithms as cooperative games. Computational social networks, 5(1):1-28.

[15] Barabâsi, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439):509-512.

[16] Bassalygo, L., Cohen, G., and Zemor, G. (2000). Codes with forbidden distances. Discrete Mathematics, 213(1-3):3-11.

[17] Blatt, M., Wiseman, S., and Domany, E. (1996). Clustering data through an analogy to the Potts model. In Advances in neural information processing systems, pages 416-422.

[18] Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008.

[19] Bloznelis, M. and Petuchovas, J. (2017). Correlation between clustering and degree in affiliation networks. In International Workshop on Algorithms and Models for the Web-Graph, pages 90-104. Springer.

[20] Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., and Hwang, D.-U. (2006). Complex networks: Structure and dynamics. Physics reports, 424(4):175-308.

[21] Bollobas, B. (2001). Random Graphs, Second Edition. Cambridge Univ.

[22] Bollobas, B. and Riordan, O. M. (2003). Mathematical results on scale-free random graphs. Handbook of graphs and networks: from the genome to the internet, pages 1-34.

[23] Bollobas, B. and Thomason, A. (1987). Threshold functions. Combinatorica 7, page 35-38.

[24] Chen, M., Liu, J., and Tang, X. (2008). Clustering via random walk hitting time on directed graphs. In AAAI, volume 8, pages 616-621.

[25] Chung, F. and Lu, L. (2006). Complex Graphs and Networks. American Mathematical Society, Providence, Rhode Island, USA.

[26] Cooper, C., Frieze, A., and Pralat, P. (2014). Some typical properties of the spatial preferred attachment model. Internet Mathematics, 10:27-47.

[27] Costa, L. d. F., Rodrigues, F. A., Travieso, G., and Villas Boas, P. R. (2007). Characterization of complex networks: A survey of measurements. Advances in physics, 56(1):167-242.

[28] de Bruijn, N. and Erdos, P. (1951). A colour problem for infinite graphs and a problem in the theory of relations. Proc. Koninkl. Nederl. Acad. Wet. Series A, mathematical sciences, 54(5):371-373.

[29] Demmel, J. W., Marques, O. A., Parlett, B. N., and Vomel, C. (2008). Performance and accuracy of lapack's symmetric tridiagonal eigensolvers. SIAM Journal on Scientific Computing, 30(3):1508-1526.

[30] Durrett, R. (2006). Random Graph Dynamics. Cambridge Univ. Press.

[31] Erdos, P. and Renyi, A. (1959). On random graphs i. Publ. Math. Debrecen, pages 290 - 297.

[32] Erdos, P. and Renyi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., pages 17-61.

[33] Erdos, P. and Rnnyi, A. (1961). On the evolution of random graphs. Bull. Inst. Int. Statist. Tokyo, pages 343 - 347.

[34] Faloutsos, M., Faloutsos, P., and Faloutsos, C. (1999). On power-law relationships of the internet topology. In ACM SIGCOMM computer communication review, volume 29, pages 251-262. ACM.

[35] Frankl, P. and Wilson, R. (1981). Intersection theorems with geometric consequences. Combinatorica, 1:357-368.

[36] Jacob, E., Morters, P., et al. (2015). Spatial preferential attachment networks: Power laws and clustering coefficients. The Annals of Applied Probability, 25(2):632-662.

[37] Janson, S., Luczak, T., and Rucinski, A. (2000). Random Graphs. Wiley, New York, USA.

[38] Janssen, J., Pralat, P., and Wilson, R. (2013). Geometric graph properties of the spatial preferred attachment model. Advances in Applied Mathematics, 50:243-267.

[39] Janssen, J., Pralat, P., and Wilson, R. (2016). Non-uniform distribution of nodes in the spatial preferential attachment model. Internet Mathematics, 12(1-2):121-144.

[40] Krot, A. and Ostroumova Prokhorenkova, L. (2017). Local clustering coefficient in generalized preferential attachment models. Internet Mathematics.

[41] Levin, D., Peres, Y., and Wilmer, E. (2009). Markov Chains and Mixing Times. American Mathematical Society.

[42] Mazalov, V. V. (2018). Comparing game-theoretic and maximum likelihood approaches for network partitioning. In Transactions on Computational Collective Intelligence XXXI, pages 3746. Springer.

[43] Mitzenmacher, M. and Upfal, E. (2017). Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge Univ. Press.

[44] Mossel, E., Neeman, J., and Sly, A. (2016). Consistency thresholds for the planted bisection model. Electronic Journal of Probability, 21(none):1 - 24.

[45] Nagy, Z. (1972). A certain constructive estimate of the ramsey number. Matematikai Lapok.

[46] Newman, M. (2005). A measure of betweenness centrality based on random walks. Social Networks, 27(1):39-54.

[47] Newman, M. E. (2003). The structure and function of complex networks. SIAM review, 45(2):167-256.

[48] Newman, M. E. (2005). Power laws, pareto distributions and zipf's law. Contemporary physics, 46(5):323-351.

[49] Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577-8582.

[50] Newman, M. E. (2016). Equivalence between modularity optimization and maximum likelihood methods for community detection. Physical Review E, 94(5):052315.

[51] Ostroumova Prokhorenkova, L., Pralat, P., and Raigorodskii, A. (2017). Modularity of complex networks models, preprint. Internet Mathematics.

[52] Pons, P. and Latapy, M. (2005). Computing communities in large networks using random walks. ISCIS, 3733:284-293.

[53] Prokhorenkova, L., Tikhonov, A., and Litvak, N. (2019). Learning clusters through information diffusion. Proceedings of the 2019 World Wide Web Conference (WWW '19), page 3151-3157.

[54] Raigorodskii, A. (2013). Coloring distance graphs and graphs of diameters. Thirty Essays on Geometric Graph Theory.

[55] Ravasz, E. and Barabasi, A.-L. (2003). Hierarchical organization in complex networks. Physical Review E, 67(2):026112.

[56] Reichardt, J. and Bornholdt, S. (2006). Statistical mechanics of community detection. Physical review E, 74(1):016110.

[57] Serrano, M. A. and Boguna, M. (2006). Clustering in complex networks. ii. percolation properties. Physical Review E, 74(5):056115.

[58] Su, L., Wang, W., and Zhang, Y. (2020). Strong consistency of spectral clustering for stochastic block models. IEEE Transactions on Information Theory, 66(1):324-338.

[59] Thadakamalla, H. P., Kumara, S. R. T., and Albert, R. (2008). Complexity and large scale networks. In Operations Research and Management Science Handbook. CRC Press.

[60] Traag, V., Waltman, L., and van Eck, N. (2019). From louvain to leiden: guaranteeing well-connected communities. Sci Rep, 9(5233).

[61] Vázquez, A., Pastor-Satorras, R., and Vespignani, A. (2002). Large-scale topological and dynamical properties of the internet. Physical Review E, 65(6):066130.

[62] von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17:395-416.

[63] Wormald, N. (1999). The differential equation method for random graph processes and greedy algorithms. Lectures on Approximation and Randomized Algorithms, pages 73-155.

[64] А.М. Райгородский (2000). О хроматическом числе пространства. Успехи матем. наук, 55(2):332.