Локальные свойства веб-графов в моделях предпочтительного присоединения тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Крот Александр Викторович

• Крот Александр Викторович
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Крот Александр Викторович

Введение

Актуальность темы исследования

Степень разработанности темы

Цели и задачи

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

Теоретическая и практическая значимость работы

Методология и методы исследования

Положения, выносимые на защиту

Степень достоверности результатов

Апробация результатов

Публикации автора по теме диссертации

Личный вклад автора в публикациях с соавторами

Структура диссертации

1 Обобщенное предпочтительное присоединение

1.1 Модели, основанные на предпочтительном присоединении

1.1.1 Модель Боллобаша—Риордана

Динамическая модификация

Статическая модификация (ЬСЭ-модель)

1.1.2 Модель Бакли-Остхуса

1.1.3 Модель Мори

1.1.4 Модель Холм-Кима

1.1.5 Модель копирования

1.1.6 ИЛ^модель

1.1.7 Полиномиальная модель

1.2 Определение РЛ-класса

1.3 Степенной закон распределения степеней вершин

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

2 Анализ локального кластерного коэффициента

2.1 Средний локальный кластерный коэффициент среди вершин степени ё

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

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

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

2.3 Эксперименты

2.3.1 Средний локальный кластерный коэффициент С2(п,ё)

2.3.2 Средний локальный кластерный коэффициент С2(п)

2.4 Выводы

3 Анализ ассортативности

3.1 Средняя степень соседа среди вершин степени ё

3.2 Доказательства теорем для случая А < 1/2

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

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

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

3.3 Гипотезы для случая А ^ 1/2

3.4 Эксперименты

3.4.1 А < 1/2

3.4.2 А ^ 1/2

3.5 Выводы

Заключение

Список сокращений и условных обозначений

Список литературы

Введение

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

Актуальность темы исследования

Диссертация посвящена изучению локальных свойств моделей сложных сетей. Под сложными сетями обычно имеют в виду сети, встречающиеся в природе — биологические, транспортные, или, например, сеть Интернет, вершинами в которой являются веб-страницы, а ребрами — ссылки между ними. Именно рост сети Интернет был одним из главных стимулов изучения сложных сетей. Изучение свойств таких сетей позволяет более точно описать их структуру, проверять гипотезы, искать спам, улучшать качество информационного поиска. Анализ сетей активно используется в термодинамической, статистической физике, где часто решаются задачи анализа фазовых переходов. В математике к изучению сложных сетей подходят более формально — сети представляют собой случайные графы, для анализа свойств которых используется аппарат случайных процессов, теории вероятностей и дискретной математики. С практической точки зрения задачи анализа сложных сетей больше всего встречаются в информационном поиске — например, эффективное вычисление Ра§еКапк, поиск сообществ и кластерных структур, оптимизация обхода сетей и др.

Степень разработанности темы

Эмпирическое исследование свойств веб-графов началось с работы А.-Л. Барабаши и Р. Альберт в 1999 году [23], где было показано, что граф сети Интернет, как и большинство других сетей, обладает следующими свойствами: малый диаметр, степенной закон распределения степеней вершин, кластерная

структура и другие [2, 3, 4]. Идея теоретического анализа таких сетей заключается в том, чтобы рассмотреть сеть как результат некоторого случайного процесса, построенного таким образом, чтобы получившиеся графы с высокой вероятностью обладали перечисленными свойствами.

В своей работе А.-Л. Барабаши и Р. Альберт [23, 1] предложили общий подход к моделированию таких сетей, получивший название предпочтительное присоединение. Основная идея состоит в том, что новые страницы, появляющиеся в Интернете, скорее будут ссылаться на уже популярные страницы. С помощью этой идеи удалось впоследствии объяснить многие свойства реальных сетей, такие, как малый диаметр, степенной закон распределения степеней вершин, а также фазовый переход в размерах компонент связности.

Стоит отметить, что сама идея предпочтительного присоединения не описывает конкретную модель. Различным образом формализуя понятие популярности, можно получить большое разнообразие моделей. Например, в 2001 году Б. Боллобаш и О. Риордан формализовали идею, предложенную Барабаши и Альберт [5]. На каждом шаге в граф добавляется вершина и т ребер. При этом ребра добавляются по очереди. Вероятность того, что ребро будет проведено в какую-то предыдущую вершину г, пропорциональна степени этой вершины. Другой пример — модель копирования [6], в которой некоторые ребра, проведенные из новой вершины, "копируют" ребра одной из предшествующих страниц. Если в Интернете появляется некий сайт заданной тематики (скажем, про машинное обучение), то, как правило, сперва он "скопирует" на свою страницу ссылки по аналогичной тематике с одного из предыдущих сайтов. Стоит отметить, что в модели Боллобаша и Риордана графы имеют степенное распределение степеней вершин с параметром 3, то есть доля вершин

степени d в этой модели убывает как d-3. В свою очередь, реальные сети могут обладать различными параметрами степенного распределения степеней вершин, которые обычно лежат в интервале (2,3). Эта проблема решается в модели, предложенной П. Бакли и Д. Остхусом [7, 8, 9]. В данной модели появляется еще один параметр — начальная привлекательность вершины (константа, не зависящая от степени вершины). Этот параметр делает модель более гибкой и позволяет получить более широкий класс распределений степеней вершин.

На сегодяшний момент существует большое количество моделей сложных сетей [2, 3, 10, 11, 12, 13, 14, 15], замечательное свойство большинства которых заключается в том, что они допускают параметризацию, что позволяет настроить конкретную модель на нужные свойства. Так, например, конфигурационная модель [16, 17, 18] позволяет построить граф с заданным распределением степеней вершин. На сегодняшний день существует также множество других моделей сложных сетей, по-разному формализующих понятие предпочтительного присоединения. Примеры можно найти в работах [10, 11, 19, 20, 21].

Любой анализ очередной модели сложных сетей обычно начинается с проверки эмпирических свойств Барабаши—Альберт, т.е. с подсчета вполне конкретных характеристик.

В данной работе мы изучаем локальные свойства в новом классе моделей сложных сетей — Generalized Preferential Attachment (обобщенное предпочтительное присоединение), впервые рассмотренном в [22]. Особенность данного подхода заключается в том, что, во-первых, как мы покажем далее, большинство известных моделей предпочтительного присоединения принадлежат

данному семейству, и, как следствие, доказанные нами результаты верны сразу для большинства моделей.

Наиболее широко изучаемая характеристика сложных сетей — это распределение степеней вершин. В реальных сетях доля вершин степени ё убывает как ё-7 с некоторым параметром 7, который обычно лежит в интервале (2,3) [10, 23, 24, 25, 26]. В таком случае обычно говорят, что в сложных сетях распределение степеней вершин подчиняется степенному закону.

Следующей широко изученной характеристикой сети является ее диаметр, то есть максимальная по всем парам вершин длина кратчайшего пути между двумя вершинами. Как уже было отмечено, реальные сети имеют малый диаметр (так называемая теория 6 рукопожатий) [4]. В работе [27] Б. Бол-лобаш и О. Риордан доказали, что диаметр графов в классической модели предпочтительного присоединения ведет себя асимптотически как щ^П, где п — количество вершин в графе.

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

С2(о) = ПЕ П =1С(г) где С(г) — локальный кластерный коэффициент для

вершины г: С (г) = р-, где Тг — количество ребер между соседями вершины г и Р2г — общее число различных пар соседей. Локальный кластерный коэффициент принимает значения от 0 до 1. Отметим, что обычно локальный кластерный коэффициент рассматривается для простых графов. В нашей работе мы будем рассматривать графы, допускающие кратные ребра и петли,

поэтому в главе 2 мы дополнительно дадим формальное определение для этого случая.

В данной работе мы также рассматриваем средний локальный кластерный коэффициент С2(п,ё) среди вершин заданной степени ё. Известно, что для многих реальных сетей оба коэффициента стремятся к нулю при росте размера сети. В реальных сетях С2(п, ё) обычно убывает как ё— для некоторого параметра ф > 0 [28, 29, 30]. Для некоторых сетей ф = 1 [31, 32].

Наконец, еще одной важной характеристикой сложных сетей, отражающей локальные свойства, является средняя степень ёпп(ё) соседа вершины заданной степени ё. Данная величина тесно связана с понятием ассортативности. Граф называется ассортативным, если ёпп(ё) — возрастающая по ё функция, и дисассортативным, если ёпп(ё) — убывающая по ё функция. В данной главе мы проанализируем ёпп(ё) вместо подсчета корреляции Пирсона, т.к. полученная функция дает более глубокое представление об устройстве сети. В некоторых реальных сетях ёпп(ё) ведет себя как ё^ для некоторого V, которое может быть положительно (для ассортативных сетей) или отрицательно (для дисассортативных сетей) [10, 33]. Как мы покажем далее, в широком классе моделей предпочтительного присоединения ёпп(ё) ~ ^(ё) при ё ^ то.

Ассортативность имеет несколько приложений, например, в эпидемиологии. В социальных сетях мы обычно наблюдаем ассортативность, в то время как, например, биологические сети обычно дисассортативны.

Цели и задачи

1. Исследование локальных свойств в моделях предпочтительного присоединения посредством получения оценок для локального кластерного коэффициента и средней степени соседа вершин среди вершин степени ё.

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

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

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

Теоретическая и практическая значимость работы

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

Методология и методы исследования

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

Положения, выносимые на защиту

1. Оценка математического ожидания среднего локального кластерного коэффициента среди вершин степени ё в графах обобщенного предпочти-

тельного присоединения. Доказательство концентрации.

2. Оценка математического ожидания средней степени соседа вершин степени d в графах обобщенного предпочтительного присоединения (Generalized Preferential Attachment).

3. Гипотеза об оценке среднего локального кластерного коэффициента в моделях предпочтительного присоединения.

Степень достоверности результатов

Все результаты обоснованы в виде строгих математических доказательств.

Апробация результатов

Результаты диссертации докладывались на следующих научно-исследовательских семинарах:

— Кафедральный семинар кафедры дискретной математики под руководством А.М. Райгородского (ФИВТ МФТИ, 2013-2016 гг.).

А также на следующих международных научных конференциях:

— Международная конференция "The 12th Workshop on Algorithms and Models for the Web Graph" (Эйндховен, Нидерланды, декабрь 2015 г.),

— Международная конференция "The 13th Workshop on Algorithms and Models for the Web Graph" (Монреаль, Канада, декабрь 2016 г.),

— Международная конференция "Workshop on Extremal graph theory" (Москва, Россия, июнь 2014 г.),

— Международная конференция "The 5th International Conference on Networks Analysis" (Нижний Новгород, Россия, май 2015 г.).

Публикации автора по теме диссертации

Результаты диссертации опубликованы в 4 работах автора [38, 39, 40, 41] (3 из них [38, 40, 41] входят в перечень ВАК), список которых приведен в конце диссертации.

Личный вклад автора в публикациях с соавторами заключается в следующем:

[38, 39, 41] - доказательство теорем о математическом ожидании и концентрации количества треугольников на вершинах заданной степени. Доказательство теоремы о среднем кластерном коэффициенте среди вершин заданной степени; [40] - доказательство теорем о математическом ожидании суммы степеней вершин среди вершин заданной степени. Отыскание математического ожидания средней степени вершин.

Структура диссертации

Данная работа состоит из трех глав, заключения и списка литературы. Первая глава посвящена обзору современных моделей сложных сетей, основанных на идее предпочтительного присоединения. В ней также мы рассмотрим понятие обобщенного предпочтительного присоединения (Generalized Preferential Attachment), впервые рассмотренного в [22]. Вторая и третья главы посвящены, соответственно, анализу локального кластерного коэффициента и средней степени соседа в моделях предпочтительного присоединения семейсва GPA. В ней мы сформулируем полученные теоретические результаты и докажем их. А также сформулируем некоторые гипотезы, которые впоследствии проверим с помощью моделирования.

Общий объем диссертации составляет 78 страниц.

Благодарности. Автор признателен Андрею Михайловичу Райгородско-му за научное руководство, а также Людмиле Александровне Прохоренковой (Остроумовой) за неоценимую помощь в работе.

Глава 1

Обобщенное предпочтительное присоединение

На сегодняшний день существ ует большое количество моделей веб-графов, основанных на идее предпочтиельного присоединения, сформулированной А.-Л. Барабаши и Р. Альберт [1] еще в 1999 году. Среди известных — LCD-модель, модель Бакли-Остхуса, Холма-Кима и RAN-модели. Тем не менее, исследуя одни и те же характеристики сложных сетей, можно заметить, что часто результаты для разных моделей похожи и отличаются только константами. В связи с этим возникает идея подойти к предпочтительному присоединению шире, рассмотрев целый класс параметризуемых моделей. Обобщенное предпочтительное присоединение (Generalized Preferential Attachment) впервые было предложено в работе [22], где широкий класс моделей (PA-класс) был определен в терминах ограничений, достаточных для изучения степене-ней вершин и коэффициентов кластеризации. Там же было показано, что распределение степеней вершин в моделях PA-класса является степенным, а также были получены некоторые оценки кластерных коэффициентов. В данной главе мы сначала рассмотрим наиболее известные модели предпочтительного

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

1.1 Модели, основанные на предпочтительном присоединении

В этом разделе мы рассмотрим наиболее известные модели сложных сетей, а также покажем, что большинство из них на самом деле можно отнести к одному классу — обобщенное предпочтительное присоединение (Generalized Preferential Attachment).

1.1.1 Модель Боллобаша—Риордана

Модель Боллобаша-Риордана [5] имеет 2 основных модификации — динамическую и статистическую, разница между которыми заключается в разном подходе к описанию случайности. Тем не менее, графы, получающиеся в обоих случаях, оказываются по своим свойствам практически идентичными.

Динамическая модификация

Сперва построим последовательность графов СП, в которой у графа с номером п число вершин и ребер равно п. Затем сделаем из нее последовательность СП, в которой у графа с номером п число вершин равно п, а число ребер равно kn, где k — натуральное число:

1. Пусть О1 — граф с одной вершиной и одной петлей, и пусть граф ОП

n—1

уже построен. Его вершины образуют множество {1,... ,n — 1}, а ребер у него ровно n — 1. Добавим вершину n и ребро (n,i), у которого i Е {1,...,n}. Ребро (n,n) будет появляться с вероятностью 1/(2n — 1), а ребро (n,i) — с вероятностью dj/(2n — 1), где dj — степень вершины i в графе С'П-1. Легко проверить, что распределение вероятностей задано корректно (сумма их равна 1).

2. Граф Gn получается из графа Gfn, у которого количество вершин и ребер равно kn. Разделим множество его вершин на куски размера k: {1,..., k}, {k + 1,..., 2k},... , {k(n — 1),..., kn}. Каждый кусок будем считать "вершиной", а ребра сохраним. Ребра внутри куска образуют кратные петли, ребра же между двумя различными кусками являются кратными. Данный граф будет иметь ровно n вершин и kn ребер.

Статическая модификация (LCD-модель)

Для определения статической модификации модели Боллобаша- Риорда-на нам потребуется понятие линейной хордовой диаграммы. Зафиксируем на оси абсцисс на плоскости 2n точек: 1, 2, ..., 2n. Разобьем все эти точки на пары и элементы каждой пары соединим дугой, лежащей в верхней полуплоскости. Полученный объект называется линейной хордовой диаграммой (linearized chord diagram — LCD). Важно отметить, что дуги в ней не могут иметь общих вершин (при этом, например, могут пересекаться). Используя несложную комбинаторику, легко понять, что количество различных LCD

7 _ (2n)!

равно ln — 2nn! .

Каждой LCD мы можем поставить в соответствие граф согласно следующей процедуре: идем слева направо по оси абсцисс до первого правого конца i1

какой-либо дуги. Набор {1,..., ¿1} будем считать первой вершиной будущего графа. Снова идем от ¿1 + 1 направо до первого правого конца ¿2 какой-либо дуги. Второй вершиной графа будем считать набор {¿1 + 1,...,i2}. И так далее. Тем самым мы получим ровно n вершин, поскольку правых концов у дуг в данной диаграмме ровно n штук. Ребра же в нашем графе порождаются дугами: две вершины соединяются ребром, если между соответствующими наборами есть дуга. Ребра ориентируем справа налево. Аналогично возникают петли. Итого получается ровно n вершин и ровно n ребер.

Считая каждую LCD случайной (полагая вероятность каждой диаграммы равной 1/1n), мы получаем случайные графы. Такие графы по своим вероятностным характеристикам практически не отличимы от графов Gkn, рассмотренных ранее. После этого графы с n вершинами и kn ребрами получаем тем же способом, что и в предыдущем пункте.

1.1.2 Модель Бакли—Остхуса

Модель Бакли-Остхуса [7, 8, 9] является модификацией модели Боллобаша-Риордана и более точно описывает реальные веб-графы. Процесс ее построения также итеративный. Зафиксируем некоторое положительное вещественное число а. Построим последовательность случайных графов {Hfa}. Граф Hiа совпадает с графом G из пункта 1.1.1. У графа Hn—1 вершины образуют множество {1,...,n — 1}, а ребер у него ровно n — 1 штука. Добавляем вершину n и проводим ребро (n, i), чтобы получить граф Hn а. При этом, ребро (n,n) появляется с вероятностью 1, а ребро (n,i) — с вероятностью (а+1)+—1, где di — степень вершины ¿. Легко проверить, что при таком определении задано действительно вероятностное распределение, т.к. сумма всех

n

а

вероятностей равна 1. Далее, так же, как и в модели из п. 1.1.1, граф НП получаем из графа ИкП стандартной склейкой.

Понятно, что при а — 1 мы фактически получаем модель Боллобаша-Риордана. Число а обычно интерпретируется как "начальная притягательность" каждой вершины.

1.1.3 Модель Мори

Модель Мори во многом похожа на модель Бакли-Остхуса. Будем строить последовательность случайных графов {НПк}. Граф И| 1 состоит из двух вершин и ребра между ними. Пусть граф {НП ——1} уже построен. На очередном шаге добавляем вершину n и одно ребро. При этом, вероятность провести ребро (n,n) равна нулю, а вероятность ребра (n,i), где i Е {1,...,n — 1}, равна (в+2)( +—1)—2, где di — степень вершины i. Далее, так же, как и в модели из п. 1.1.1, граф НП k получаем из графа Н^ стандартной склейкой (в нем уже петли могут присутствовать). Заметим, что при в — 0 мы получаем практически модель Боллобаша-Риордана.

1.1.4 Модель Холм—Кима

Модель Холм-Кима была предложена в 2001 году [12]. Зафиксируем 2 параметра: p Е [0,1] и натуральное m > 1. Начнем с графа G1, содержащего ровно одну вершину и петлю. Построим последовательность графов Gt. Граф Gt получается из графа Gt—1 путем добавления новой вершины и m ребер, ведущих из в вершины графа Gt—1. Сами ребра добавляются исходя из следующей логики:

• Preferenatial Attachment (PA) шаг. Первое ребро всегда добавляется в од-

ну из предыдущих вершин. Вероятность попасть в конкретную вершину i пропорциональна степени этой вершины di.

• Каждое следующее m — 1 ребро добавляется одним из двух способов:

Triad Formation (TF) шаг. Пусть ш' — вершина, в которую попало предыдущее ребро. Тогда текущее ребро попадает в ее соседа ш, причем вероятность попасть в конкретного соседа вершины ш' пропорциональна числу ребер между вершинами ш и ш'. Данный шаг происходит с вероятностью p.

С вероятностью 1 — p мы повторяем PA-шаг.

Легко видно, что при p = 0 мы получаем модель Барабаши-Альберт в чистом виде. Идея TF-шага в данном случае похожа на идею модели копирования, которую подробно мы рассмотрим далее.

1.1.5 Модель копирования

Данная модель возникла практически в одно время с моделью Барабаши-Альберт. Зафиксируем число а £ (0,1) и натуральное d ^ 1. В качестве начального графа возьмем любой d-регулярный граф (граф, у которого степень каждой вершины равна d). Пусть построен граф Gt = (Vt, Et) с номером t. Здесь Vt = {u1,...,us}, где s отличается от t на число вершин начального графа, то есть на некоторую константу, выражаемую через d. Добавим к Gt одну новую вершину us+1 и d ребер, выходящих из us+1. Для этого сперва выберем случайную вершину p £ Vt (все вершины в Vt равновероятны). Одно за другим строим ребра из us+1 в Vt. На шаге с номером i, i £ {1, ...,d}, разыгрываем случайную величину, которая с вероятностью а принимает зна-

чение 1 и с вероятностью 1 — а принимает значение 0. Если выпала единица, то выпускаем ребро из в случайную вершину из V (все вершины в V равновероятны). Если же выпал ноль, то берем ¿-го по номеру соседа вершины р (данное действие всегда возможно, поскольку по построению у каждой вершины не менее ё соседей).

1.1.6 ИЛ^модель

В контексте сложных сетей также рассматривают интересные по своим свойствам графы Аполлония, которые могут быть получены из треугольного графа, вложенного в евклидову плоскость, путём неоднократного выбора треугольной грани вложения, добавления новой вершины в эту треугольную грань и соединения новой вершины с каждой вершиной внутри грани. В результате грань делится на три меньших треугольника, которые, в свою очередь, могут быть поделены тем же самым образом. Несложно заметить, что в этом описании также прослеживается прямая связь с идеей продпочтитель-ного присоединения.

1.1.7 Полиномиальная модель

В нашей работе мы также будем рассматривать предложенную авторами [22] полиномиальную модель. Процесс построения графа в модели также основан на последовательном добавлении вершин. На (п + 1)-ом шаге граф Ст+1 получается путем добавления вершины п + 1 и последовательного проведения т ребер из этой вершины в прыдущие вершины графа С^. При этом кратные ребра и петли разрешаются.

Для определенности будем считать, что ребро направлено от г к 7, если

i ^ j. В данном случае исходящая степень каждой вершины равна m. Будем говорить, что i и j — соответственно начало и конец ребра ij. Выберем в графе Gvm случайно ребро равномерно и независимо, далее возможны 3 правила:

• Preferential Attachment (PA): провести ребро из вершины n + 1 в конец выбранного ребра

• Uniform (U): провести ребро из вершины n +1 в начало выбранного ребра

• Triangle Formation (TF): провести 2 ребра из вершины n + 1 в начало и конец выбранного ребра

Остается определить, как провести m ребер из вершины n + 1. Рассмотрим набор таких неотрицательных параметров {ak,i} для 0 ^ k ^ m/2 и 0 ^ l ^ m — 2k, что £k l ak,i — 1. В начале (n + 1)-го шага с вероятностью ak, i мы выбираем некоторые k — k0,l — lo, затем проводим l0 ребер по правилу PA, 2k0 ребер по правилу TF и (m — l0 — 2k0) ребер по правилу U. Получившийся при такой процедуре граф будем называть графом из полиномиальной модели. Легко заметить, что граф из такой модели может быть построен алгоритмически за линейное время.

Модель называется полиномиальной не случайно. Обозначим dn — dn — m входящую степень вершины i в графе Gm. Обозначим eij количество ребер между вершинами i и j. Для любых k, l, таких, что 0 ^ k ^ m/2 и 0 ^ l ^ m — 2k, положим

1 k 2k+l dn

Mn,m — 1 TT ei2x ei2x-1 1 T k ;l nm—l—2k 11 2mn 11

k'1 nm—1—2k 2mn mn

x=1 y=2k+1

Это моном, зависящий от dn и ei2xei2x_ 1. Легко видеть, что:

Р(ребра б1,..., ет идут в вершины ¿1,..., ¿т, соответственно) =

т/2 т—2к

ак,IМк)т(г1,...,гп).

к=0 1=0

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

1.2 Определение РЛ-класса

В этом разделе мы определим понятие РА-класса моделей, которое было впервые предложено в [22]. Пусть Ст (п ^ п0) — граф с п вершинами {1,..., п} и тп ребрами, полученный в результате следующего процесса. Мы начинаем в момент времени п0 с произвольного графа Ст0 с п0 вершинами и тп0 ребрами. На (п + 1)-ом шаге (п ^ п0), мы получаем граф Ст+1 из Ст добавлением вершины п + 1 и т ребер, соединяющих эту вершину с некоторыми т вершинами из множества {1,..., п, п +1}. Отметим, что в графе допускаются петли и кратные ребра, с учетом которых считается степень вершины. Однако, как и в модели Боллобаша-Риордана, их количество незначительно [5].

Обозначим ¿П степень вершины V в Ст. Пусть для некоторых констант А

и В выполнены следующие условия:

р = < | Спт) = 1 - Л— - вП + О ( Щ- ) , 1 ^ V ^ п, (1.1)

п п \ п

р ^ = < + 1 | Спт) = Л— + В— + о( ^ ) , 1 ^ V ^ п , (1.2)

2

р «+1 = < + э | су = о ( ^ ) , 2 ^ э ^ т, 1 ^ V ^ п , (1.3)

V 1 ^ I т/ I п2

р(^п+1 = т + э) = О ^ , 1 < э < т (1.4)

Тогда будем говорить, что граф Су принадлежит РА-классу моделей предпочтительного присоединения. Здесь, как и в [22], должны быть выполнены условия нормировки 2тЛ + В = т и 0 ^ Л ^ 1.

Отметим, что фиксация параметров Л и т не определяет конкретную процедуру для построения графа.

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

Список литературы диссертационного исследования кандидат наук Крот Александр Викторович, 2017 год

Список литературы

[1] Albert R., Barabasi A. L. Statistical mechanics of complex networks //Reviews of modern physics. - 2002. - T. 74. - №. 1. - C. 47.

[2] Girvan M., Newman M. E. J. Community structure in social and biological networks //Proceedings of the national academy of sciences. - 2002. - T. 99. - №. 12. - C. 7821-7826.

[3] Newman M. E. J. The structure and function of complex networks //SIAM review. - 2003. - T. 45. - №. 2. - C. 167-256.

[4] Watts D. J., Strogatz S. H. Collective dynamics of'small-world'networks //nature. - 1998. - T. 393. - №. 6684. - C. 440.

[5] Bollobas B. et al. The degree sequence of a scale-free random graph process //Random Structures Algorithms. - 2001. - T. 18. - №. 3. - C. 279-290.

[6] Kumar R. et al. Stochastic models for the web graph //Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on. - IEEE, 2000. - C. 57-65.

[7] Buckley P. G., Osthus D. Popularity based random graph models leading to a scale-free degree sequence //Discrete Mathematics. - 2004. - T. 282. - №. 1. - C. 53-68.

[8] Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Structure of growing networks with preferential linking //Physical review letters. - 2000. - T. 85.

- №. 21. - C. 4633.

[9] Drinea E., Enachescu M., Mitzenmacher M. D. Variations on random graph models for the web. - 2001.

[10] Boccaletti S. et al. Complex networks: Structure and dynamics //Physics reports. - 2006. - T. 424. - №. 4. - C. 175-308.

[11] Bollobas B., Riordan O. M. Mathematical results on scale-free random graphs //Handbook of graphs and networks: from the genome to the internet. - 2003.

- C. 1-34.

[12] Holme P., Kim B. J. Growing scale-free networks with tunable clustering //Physical review E. - 2002. - T. 65. - №. 2. - C. 026107.

[13] Jackson M. O. Social and economic networks. - Princeton university press, 2010.

[14] Jackson M. O., Watts A. The evolution of social and economic networks //Journal of Economic Theory. - 2002. - T. 106. - №. 2. - C. 265-295.

[15] Strogatz S. H. Exploring complex networks //nature. - 2001. - T. 410. - №. 6825. - C. 268.

[16] Molloy M., Reed B. A critical point for random graphs with a given degree sequence // Random structures algorithms. - 1995. - T. 6. - №. 2-3. - C. 161-180.

[17] Павлов Ю. Л., Степанов М. М. Предельные распределения числа петель случайного конфигурационного графа //Труды Математического института им. ВА Стеклова РАН. - 2013. - Т. 282. - С. 212-212.

[18] Павлов Ю. Л. О предельных распределениях степеней вершин условного конфигурационного случайного графа //Труды Карельского научного центра Российской академии наук. - 2012. - №. 5.

[19] Райгородский А. Модели случайных графов. - Litres, 2017.

[20] Райгородский А. М. Модели случайных графов . - МЦНМО, 2011.

[21] Райгородский А. М. Модели интернета //Долгопрудный: Издательский дом "Интеллект. - 2013.

[22] Ostroumova L., Ryabchenko A., Samosvat E. Generalized Preferential Attachment: Tunable Power-Law Degree Distribution and Clustering Coefficient //WAW. - 2013. - С. 185-202.

[23] Barabasi A. L., Albert R. Emergence of scaling in random networks //science. - 1999. - Т. 286. - №. 5439. - С. 509-512.

[24] Broder A. et al. Graph structure in the web //Computer networks. - 2000. -Т. 33. - №. 1. - С. 309-320.

[25] Cooper C. Distribution of vertex degree in web-graphs //Combinatorics, Probability and Computing. - 2006. - Т. 15. - №. 5. - С. 637-661.

[26] Faloutsos M., Faloutsos P., Faloutsos Ch. On power-law relationships of the internet topology. - 1999. - SIGCOMM Conference

[27] Bollobas B., Riordan O. The diameter of a scale-free random graph //Combinatorica. - 2004. - T. 24. - №. 1. - C. 5-34.

[28] Catanzaro M., Caldarelli G., Pietronero L. Assortative model for social networks //Physical Review E. - 2004. - T. 70. - №. 3. - C. 037101.

[29] Serrano M. A., Boguna M. Clustering in complex networks. I. General formalism //Physical Review E. - 2006. - T. 74. - №. 5. - C. 056114.

[30] Vazquez A., Pastor-Satorras R., Vespignani A. Large-scale topological and dynamical properties of the Internet //Physical Review E. - 2002. - T. 65. -№. 6. - C. 066130.

[31] Leskovec J. Dynamics of large networks. - Carnegie Mellon University, 2008.

[32] Ravasz E., Barabasi A. L. Hierarchical organization in complex networks //Physical Review E. - 2003. - T. 67. - №. 2. - C. 026112.

[33] Echenique P. et al. Distance-d covering problems in scale-free networks with degree correlations //Physical Review E. - 2005. - T. 71. - №. 3. - C. 035102.

[34] Serrano M. A., Boguna M. Clustering in complex networks. II. Percolation properties //Physical Review E. - 2006. - T. 74. - №. 5. - C. 056115.

[35] Newman M. E. J. Assortative mixing in networks //Physical review letters.

- 2002. - T. 89. - №. 20. - C. 208701.

[36] van der Hofstad R., Litvak N. Degree-degree dependencies in random graphs with heavy-tailed degrees //Internet mathematics. - 2014. - T. 10. - №. 3-4.

- C. 287-334.

[37] van der Hoorn P., Litvak N. Degree-degree dependencies in directed networks with heavy-tailed degrees //Internet mathematics. - 2015. - Т. 11. - №. 2. -С. 155-179.

Публикации автора по теме диссертации

[38] [Входит в перечень ВАК] Krot A., Ostroumova Prokhorenkova L., Local Clustering Coefficient in Generalized Preferential Attachment Models // 12th Workshop on Algorithms and Models for the Web Graph, Eindhoven, Netherlands, 10-11 December, 2015, Proceedings. - Lecture Notes in Computer Science, 2015. - P. 15-28.

[39] Krot A., Ostroumova Prokhorenkova L. Local Clustering Coefficient in Generalized Preferential Attachment Models [Электронный ресурс] / Krot A., Ostroumova Prokhorenkova L. // Internet Mathematics. - Special Issue for 15th Workshop on Algorithms and Models for the Web Graph. - 2017. - 18 р.

- Режим доступа: http://www.internetmathematicsjournal.com/article/1253

- (Дата обращения: 11.01.2017).

[40] [Входит в перечень ВАК] Krot A., Ostroumova Prokhorenkova L. Assortativity in Generalized Preferential Attachment Models // 13th Workshop on Algorithms and Models for the Web Graph, Montreal, Canada, 14-15 December, 2016, Proceedings. - Lecture Notes in Computer Science, 2016. - P. 9-21.

[41] [Входит в перечень ВАК] Прохоренкова Л.А., Крот А.В. Локальный кластерный коэффициент в моделях предпочтительного присоединения // Доклады Академии Наук - 2016. - том 471. - №1. - C. 19-22.

Личный вклад Крота А.В. в работах с соавторами заключается в следующем:

[38, 39, 41] - доказательство теорем о математическом ожидании и концентрации количества треугольников на вершинах заданной степени. Доказательство теоремы о среднем кластерном коэффициенте среди вершин заданной степени; [40] - доказательство теорем о математическом ожидании суммы степеней вершин среди вершин заданной степени. Отыскание математического ожидания средней степени вершин.