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

• Прохоренкова, Людмила Александровна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Прохоренкова, Людмила Александровна

Оглавление

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

Введение

Актуальность темы

Характеристики сложных сетей

Предпочтительное присоединение

Глава 1 Анализ модели Боллобаша-Риордана

1.1 Определение модели и известные результаты

1.2 Распределение вторых степеней вершин

1.2.1 Введение обозначений и формулировка результатов

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

1.3 к-е степени вершин

1.3.1 Введение обозначений и формулировка результатов

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

1.4 г-диаметр

1.4.1 Введение обозначений и формулировка результатов

1.4.2 Оценка снизу

1.4.3 Оценка сверху

Глава 2 Анализ модели Бакли-Остхуса

2.1 Определение модели и известные результаты

2.2 Введение обозначений и формулировка результатов

2.2.1 Определения

2.2.2 Математическое ожидание

2.2.3 Концентрация

2.3 Доказательство концентрации

2.3.1 Интерпретация модели Бакли Остхуса в терминах независимых случайных величин

2.3.2 Уменьшение количества /с-вершин

2.3.3 Построение подходящей системы множеств /С

2.3.4 Применение неравенства Талаграна

2.3.5 Концентрация для Хп(к)

2.3.6 Обобщение на случай произвольного т

2.4 Оценка ЕУп{к)

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

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

2.4.3 Доказательство леммы 15

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

Глава 3 Предпочтительное присоединение с устареванием

3.1 Классические модели и свойство устаревания

3.2 Модель с устареванием

3.3 Функция привлекательности д(г)/[г > £ — А^]

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

3.3.2 Свойство устаревания

3.4 Функция привлекательности

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

3.4.2 Свойство устаревания

3.5 Доказательства вспомогательных лемм

3.5.1 Доказательство леммы 23

3.5.2 Доказательство леммы 24

Заключение

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

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

V{G) — множество вершин графа G;

E(G) — множество ребер графа G;

— ребро ij принадлежит графу G;

t € G — вершина t принадлежит графу G;

f(n) = о(д(п)) — для любого числа с > 0 существует такое число по, что для любого п > по выполнено неравенство |/(n)| ^ с\д(п)\;

f(n) = 0(д(п)) — существуют такие числа С > 0 и по, что для любого п > по выполнено неравенство |/(n)| < C|g(n)|;

f(n) = Q(g(n)) — существуют такие числа Ci > О, С2 > 0 и щ, что для любого п > щ выполнено неравенство С\ • д(п) ^ f(n) ^ С2 • д{п)\

/(') = ®{q{')) выполнено неравенство |/(-)| ^ |<7(-)Ь

f(x) ~ д{х) — функции асимптотически равны при х —» сю, то есть f{x)=g(x) ■ (1 + о(1));

1{Х) — индикатор события X. То есть I(X) = 1 в случае, если X выполняется, и 0 иначе;

С* число сочетаний из п элементов по /с;

\А\ - мощность множества А.

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

Введение

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

Актуальность темы

Диссертация посвящена изучению моделей сложных сетей и их свойств. Под сложными сетями понимают всевозможные сети, которые встречаются в природе: компьютерные, биологические, социальные, экономические, транспортные и так далее. Классический пример такой сети — граф сети Интернет. Вершины графа — это веб-страницы, а ребра — ссылки между ними. С появлением сети Интернет началось интенсивное изучение сложных сетей. Было замечено, что все эти сети обладают некоторыми общими свойствами: малый диаметр, степенной закон распределения степеней вершин, кластерная структура и другие [28, 32, 33, 42, 43, 44, 47, 50]. Возник естественный вопрос: почему сети столь различной природы обладают схожими свойствами? Возможно, в основе всех этих сетей лежит какой-то общий принцип формирования? Так стали появляться первые модели сложных сетей, в том числе вероятностные модели [8, 17, 18, 19, 25, 26, 30, 33, 36, 37, 38, 44, 48]. Вероятностная модель — это случайный элемент со значениями в множестве графов и некоторым вероятностным распределением на этом множестве.

В 1999 году А.-Л. Барабаши и Р. Альберт [9] предложили моделировать сложные сети с помощью так называемого принципа предпочтительного присоединения. Основная идея их подхода состоит в том, что новые страницы, появляющиеся в Интернете, скорее предпочтут сослаться па уже популярные страницы (то есть на те, на которые ведет много ссылок). Работа Барабаши и Альберт послужила толчком к развитию области вероятностного моделирования сложных сетей. Например, Р. Кумар, П. Рагхаван, С. Раджагопалан, Д. Спвакумар, А. Томкинс и Э. Упфал предложили так называемую модель копирования [39], в которой некоторые ребра, проведенные из новой вершины, "копируют" ребра одной из предшествующих страниц. Еще изучалась конфигурационная модель [1, 2, 41], которая позволяет построить граф с заданным распределением степеней вершин. Эта модель может применяться для моделирования графа Интернета, если взять подходящее распределение степеней. Обзор перечисленных и многих других моделей можно найти, па-

пример, в работах [3, 4, 5, 17, 18]. Модели сложных сетей применяются в различных областях: в математике, физике, биологии, области информационных технологий.

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

Характеристики сложных сетей

Наиболее распространенная характеристика сложных сетей — это распределение степеней вершин. А именно, если выбрать случайную вершину в сети и посмотреть на ее степень (количество примыкающих ребер), то получим случайную величину, распределение которой интересно изучать. Для большинства наблюдаемых сетей оказалось, что доля вершин степени с1 убывает как с некоторым параметром 7, который обычно лежит в интервале (2, 3) [14, 17, 22, 24, 31]. Таким образом, принято говорить, что в сложных сетях распределение степеней вершин подчиняется (асимптотически) степенному закону [43].

В данной работе вводится обобщение понятия степени вершины — рассматривается вторая степень. Вторая степень вершины — это количество путей длины два, ведущих в данную вершину. Распределение вторых степеней представляет практический интерес, поскольку вторые степени являются хорошим приближением PageRank [12, 45, 46]. PageRank - это мера важности (популярности, качества) веб-страниц, он активно используется в информационном поиске. Основная идея PagoRank заключается в том, что важность вершины определяется важностью (степенью, популярностью) ее соседей. Оказалось, что в классических моделях предпочтительного присоединения распределение вторых степеней тоже подчиняется степенному закону. Кроме того, в работе исследуются /с-е входящие степени вершин.

Другой важной характеристикой сети является ее диаметр, то есть максимальная по всем парам вершин длина кратчайшего пути между двумя вершинами. Сложные сети, встречающиеся в природе, имеют малый диаметр (теория 6 рукопожатий) [10, 50]. В работе [20] Б. Боллобаш и О. Рпордан доказали, что диаметр графов в классической модели предпочтительного присоединения ведет себя асимптотически как , где п — количество вершин в графе. В данной работе вводится обобщение понятия диаметра — г-диаметр. Теперь мы рассматриваем не пары вершин, а подмножества мощности г. В каждом таком подмножестве мы находим две вершины на наименьшем расстоянии друг от друга. И нас интересует максимум этого расстояния по всем

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

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

Предпочтительное присоединение

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

Классические модели сложных сетей основаны па идее предпочтительного присоединения (preferential attachment), которая была предложена в 1999 году A.-JT. Барабаши и Р. Альберт [14, 15]. Идея состоит в том, что в Интернете новые страницы предпочитают цитировать те страницы, которые в настоящий момент более популярны. С помощью идеи предпочтительного присоединения удалось объяснить малый диаметр Интернета, а также степенной закон распределения степеней вершин в нем.

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

Благодарности. Автор признателен профессору Андрею Михайловичу Райгородскому за неоценимую помощь в работе.

Глава 1

Анализ модели Боллобаша—Риордана

Наиболее известная модель сложных сетей — это модель Боллобаша и Риордана [21], которые формализовали идею, предложенную Барабаши и Альберт в работе [14]. Некоторые свойства модели Боллобаша-Риордана будут обсуждаться в этой главе. А именно, в разделе 1.1 дано определение модели и перечислены основные классические результаты; в разделе 1.2 обсуждается распределение вторых степеней в модели; к-е степени проанализированы в разделе 1.3; раздел 1.4 посвящен изучению г-диаметра.

Данная глава основана на работах автора [52, 53, 56].

1.1 Определение модели и известные результаты

Опишем, как строится граф в модели Боллобаша и Риордана. Обычно для графов этой модели используется обозначение где п — число вершин, т — фиксированное натуральное число. Сначала индуктивно строится С". Граф С] состоит из одной вершины и одной петли. Граф С\ получается из С^-1 посредством добавления вершины t и одного ребра между вершинами £ и г, где г выбирается случайно следующим образом:

{dQt-l(s)/(2t — 1) если 1 ^ б ^ £ — 1, 1

1 /(2£ - 1) если я = г.

Здесь (¿д^в) — степень вершины й в графе С*. В дальнейшем мы будем использовать обозначение (¿(в) := ^»(й). Иными словами, чем больше степень вершины в графе С^-1, тем больше вероятность того, что следующая вершина будет соединена с ней. Граф (га > 1) получается из графа С{1п следующим образом. Первые т вершин С"71 объединяются в первую вершину нового графа, следующие га — во вторую, и так далее. Ребра в некотором смысле сохраняются, а именно: если в С,1шг ребро соединяло вершины г и j} то в полученном графе С?^ это ребро соединяет те группы вершин, в которые

попали i и j. Тем самым в графе могут возникнуть кратные ребра и кратные петли. Построенные таким образом графы G]ln образуют вероятностное пространство &\1п.

Тот факт, что граф G™n обладает степенным распределением степеней вершин, был доказан в работе [21].

Теорема 1. Пусть т ^ 1. Тогда существует такая функция tp аргумента п, что ip(n) = о(п) при п —> оо, и для любой такой степени d, что т ^ d п1/15, мы имеем

lim Р

71—>00

2пт(т + 1)

>__)=о

d{d + l){d + 2)J

d(d+l){d + 2)

Здесь - количество вершин степени d в графе G\ln.

В 2011 году в работе [34] Е.А. Гречников значительно улучшил теорему 1.

1.2 Распределение вторых степеней вершин

В этом разделе рассматриваются вторые степени вершин в графе G". Сначала оценивается математическое ожидание количества вершин со второй степенью <i, затем доказывается концентрация. Случай m ^ 2 обсуждается в главе 2 данной работы.

1.2.1 Введение обозначений и формулировка результатов

Мы рассматриваем граф G". Второй степенью вершины t € G" назовем

d2{t) = |{ij : i ф t,j Фьне GTi,ij g G\l}\.

Другими словами, вторая степень вершины t — это количество ребер, соединенных с соседями вершины t, кроме.тех, которые ведут в саму вершину t.

Через Nn(d) обозначим количество вершин степени d в графе G™, а через Xn(d) — количество вершин второй степени d в G™.

В данном разделе доказываются следующие новые результаты.

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

Теорема 3. Для любого £ > 0 существует такая функция (р аргумента п, что <р(п) — о(п) при п —> оо, и

lim Р (\Хп(к) - ЕХп(к)\ > = 0

п-> оо у Кг J

для любого такого к, что 1 ^ к ^ п1/6-5.

Эта теорема показывает, что для любого к, 1 ^ к ^ п1//6-£, с вероятностью, стремящейся к 1, количество вершин второй степени к отличается от своего математического ожидания на что-то малое в сравнении с математическим ожиданием. Таким образом, получена концентрация. Итак, распределение вторых степеней тоже подчиняется (асимптотически) степенному закону.

Для доказательства теоремы 2 нам потребуется следующее определение. Через Nn(l, к) обозначим количество вершин в графе G™ без петель, со степенью I и со второй степенью к:

Nn(l,k) = \{t е Gnx : d{t) = l,d2(t) = k,tt<£ G?}|.

Докажем следующую вспомогательную теорему.

Теорема 4. В графе G"

ЕNn(l, к) = пс(1, к) (1 + 9(п, I, /с)),

где \в(п,1,к)\ < (21-\-к — 1)2/п. Константы с(1, к) определяются следующим образом:

с(1, 0) = с(0, к) = 0, / > 0, к > 0,

_2 к2 + 14 к_

С{ , ) ~ (fc + l)(fc + 2)(fc + 3)(fc + 4)' к> '

с(1, к) = с(1, к - 1)1+ к~\+ с(1 - 1, к)п, 1 ~ 1 , v' ' v' J2l + k + 2 v ' 21 + к + 2 '

Чтобы доказать теоремы, мы будем использовать следующие леммы. Лемма 1. Пусть d ^ 1 — натуральное число. Тогда

EN'^ = é(é + l)(d + 2) ММ-

где \9{n,d)\ < d2/n.

Через Рп(1,к) обозначим количество вершин в графе с петлей, со степенью I и со второй степенью к.

Лемма 2. Для любого п имеем

Е Рп(1,к)^р(1,к),

где

Р( 2,0) = 1,

р(1,к) = р(1, к - +Р(1 ~ 1, к)21 2, ^3,^0.

Для всех других значений I и к имеем р{1, к) = 0.

В следующем параграфе приведены доказательства. Сначала будут доказаны теорема 4 и теорема 2; затем будут доказаны леммы. После этого будет доказана теорема 3 о концентрации.

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

Из определения графа С/ следует, что 0) = ЛГп(0, к) = 0. Действительно, в графе нет вершин степени 0, поэтому А/"п(0, к) = 0. Поскольку вершины с петлями не входят в Мп(1,к), то в Агп(1,к) не учитываются вершины второй степени 0 и, следовательно, УУп(/,0) = 0. В итоге ЕЛ^(/,0) = ЕЛ/^0, к) = 0.

Докажем, что Е7УП(1, к) = пс(1, к) (1 + в(п, 1, к)). Докажем это утверждение индукцией по к. Для к = 0 утверждение верно. Предположим, что для всех ^ < к

где

2.72 + 14.7

и +1)0" + 2)0' + 3)0- + 4)"

Очевидно, ЕЛ7-! (1, к) = 0. Для г ^ 1 имеем Е(ЛГт(1, к)\Щ1, к), ^(1, ^ — 1), Щк)) =

у ' ) \ 2г + 1 / 2г + 1 2г + 1 ^ '

Поясним это равенство. Предположим, что у нас имеется некоторый граф

. Мы добавляем к нему одну вершину и одно ребро. В графе есть N¡(1, к) вершин степени 1 и второй степени к. Вероятность "испортить" одну из таких вершин равна (к + 2)/(2г + 1). Также есть — 1) вершин степени 1 и

второй степени к — 1. Вероятность того, что одна из таких вершин будет иметь степень 1 и вторую степень к в

С\+1 , равна к/{2г+1). Наконец, с вероятностью /сЛ^(/с)/(2г +1) вершина г +1 сама будет иметь нужную степень в графе .

Используя равенство (1.1), лемму 1 и предположение индукции, получаем

ЕЛМ1, *) = ЕЛ«1, к)2г:к~1 + ^(1,^-1) + в =

' ' п ' ' 2г + 1 2г + 1 2г +1

= ЕЩ1,к)2*-к~1

Введем следующие обозначения:

2г - к - 1

сч =

2г + 1 12

с(1, к — 1) к 2

т = К —— +

2 (к+1){к + 2)" Используя эти обозначения, получим

ЕЛ^+1(1, к) = ЕА^(1, к)сн+т Ъ{.

Докажем следующее равенство индукцией по п:

Отп

ЕМп{1,к) = — (1 + 0(п,1,*О).

Для п = 1 имеем Е.Л/1(1,А;) = 0. Поскольку у нас есть условие \в(1,1,к)\ < (к + I)2, мы можем взять 0(1,1, к) = —1.

Теперь положим £ = к+1 (это будет использоваться позже). Предположим, что

27777

Тогда

Шш{1,к) = Е7Уг(1,/с) сц + т 6г =

2гаг(2г — ¿) , 9 , ,ч 2гш , „ „.9 , чч

1 ; (1 + 9(^/г)) + —— (1 + 0 ((* - 1)2Л)) =

(2г + 1)(£ + 3) у 4 ' 2г + 1

¿ + 3\ 2г + 1 \ 2г + 1 ) \ 2г + 1

Если £ ^ 1 и 2г — £ ^ 0, то

1 + + (* - + 3) < ^

2г + 1 2г + 1 2г + 1

Поэтому

ЕЛМ1. = -~^ (1 + 0 (<7(* + !)))■

Что и требовалось показать.

Если £ ^ 1 и 2г — £ ^ — 2, то у нас нет достаточного количества ребер в графе и ЕЛ^_|_1 (/, к) = 0. В этом случае в (г + 1,1, к) = —1. Случай 2г — £ = —1 будет рассмотрен позже. Получили

/с + 4

Заметим, что

2т 4 2с(1,/с- 1)к _

к + 4 (к + 1)(к + 2)(к + 4) 2(к + 4)

2(к — l)2 + Ы(к — 1)

(fc+l)(fc + 2)(fc + 4) (fc+l)(fc + 2)(fc + 3)(fc + 4) 2/c2 + Uk (к + l)(k + 2){k + 3)(k + 4) ' J-

Это завершает доказательство для EiVn(l, к).

Рассмотрим случай I ^ 2. Допустим, мы уже доказали, что ЕNn(i,j) = nc(i,j) (1 + 6(n,i,j)) для всех inj таких, что г < I, j ^ к или i ^ I , j < к. Положим t — 21 + к — 1. Очевидно, EN\(l, к) = 0. Для г ^ 1 имеем

/ 9/4- к\

ЕNi+l(l, к) = ENS: к) 11 - ^-^J + , (г - 1) - 1 ,к) {l + к- 1)Е Ni(l, к- 1) _

2г + 1 2г + 1

2г + 1

+ + + (1 + в ((t _ 1)2/,)) .

Введем обозначения:

2г - t

аг = 2ГГг

(/ - 1)с(/ - 1,/с) (Z + fc-l)c(/,fc-l)

Имеем

ЕЛГш(г,/с) = ЕЩ1,к) аг+тЬ{. Остается доказать индукцией по п следующее утверждение:

вед к) = (1 + в (?/п)) = ^ (1 + в(пХ к)).

Доказательство похоже на доказательство в случае I — 1. В данном случае 2т (1-1)с(1-1,к) (1 + к-1)с(1,к-1)

¿ + 3 2/ + А; + 2 21 +к+ 2

Теперь нам осталось рассмотреть только случай 2г — t = —1. Требуется показать, что ЕЩ+1(1, к) = (г+1 )с(/, к)( 1+6>(г+1, /, к)). Имеем 2(г+1) = 21+к. В графе С^1 есть г + 1 ребро. Поэтому сумма всех степеней равна 21 + к. Предположим, что есть хотя бы одна вершина степени I и второй степени к. Мы не считаем вершины с петлями в поэтому I ребер выходят из

этой вершины. Есть еще к/2 ребер между соседями этой вершины, а больше ребер нет. Поэтому наша вершина соединена со всеми остальными вершинами в С1*1. Следовательно, I = г. Таким образом, А; = 2. Из этого следует, что мы рассматриваем вершину 2. И есть одно ребро из вершины 2 в вершину 1, а еще есть ребра из вершин 3,... , г + 1 в вершину 2. Таким образом, существует всего один граф с N1+1(1, к) 0. И в этом графе есть ровно одна вершина со степенью I и второй степенью к. Поэтому вероятность этого графа равна ЕN¡+,(1, 2). Получили ЕЛГШ(/, 2) =

Напомним, что I = г и к — 2. Теперь нам нужно доказать, что

2) = (I + 1 )с(1, 2)(1 + 6(1 + 1,1, 2)).

Докажем неравенство

5(21 + 4)!!' Из определения с(1, к) следует, что

<=(1.2) = ¿5,

с(1,2)>с(1- 1> 2.

Очевидно, + 1,/,2) ^ —1. Получим следующую верхнюю оценку: 0{1 + 1,1,2) + 1=;2(/ — 1)!5(2/ + 4)!! _

(I + 1 )с(/, 2) ^ (21 + 1)!!(1 + 1)24(1 - 1)! 5(2/ + 4)!! (2/ + 1)2

12(2/ + 1)!!(/ + 1) ^ (/ + 1) ' Это завершает доказательство теоремы 4.

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

В теореме 4 были получены константы с(1, Представим, что есть таблица со значениями с(1, к), где I — номер строки, а к — номер столбца. Сумма всех чисел в таблице равна 1. Сумма чисел в 1-ой строке равна щ^щ^у. Это можно легко проверить, используя определение с(/, к). Но требуется оценить ЕХп(к), поэтому нас интересует сумма чисел в к-ом столбце. А точнее,

оо оо

ЕХп(к) = ЕЗД + к)•

/=1 1=1

Для начала оценим Напомним, что

с(1,0) = 0,

(л 1Л - 2к2 + Ык Ь > 1

; " (к + 1)(/с + 2) (к + 3)(к + 4)'

/ 4- к — 1 / — 1

«1<*) = <*.*- Чат1+2+ с(< ~ ^ х -' ? 2'

Заметим, что существует функция С(&) ^ 0 такая, что для всех I ^ к ^ 0 и / ^ 1 неравенство

(1.2)

верно. Действительно, случай к = 0 очевиден с С (к) — 0. Для /с ^ 1 определим С (к) так, что С (к) ^ С(& — 1) и (1.2) выполнено для I = к. Имеем

Это доказывает (1.2).

В частности, ряд к) сходится для всех N и /с.

Сделаем некоторые преобразования:

(21 + к + 2)с(1, к) = {1 + к~ 1 )с(1, к-1) + (1- 1 )с{1 -1,к),

оо оо оо

^2(21 + к + 2)с(/, к) = + А; — 1)с(/, к - 1) + ^ /с(/, /с), г=2 г=2 г=1

оо оо

^2(1 + к + 2 )с(1, к) = + к - 1 )с(1, к- 1) + с(1, А;). /=2 г=2

Положим ж/с = £^2с(/, Тогда жо — 0 и для к ^ 1 имеем

00

(к + 2)а* = (к - 1)хк-! + с(1, к) + ^2к-1)- с(1, к)),

1=2

(,к + 2)(/с + 1 )кхк = {к- 1 )(к + 1)кхк-\ + (к + 1)кс(1, к)+

оо

+ ^21(к{к + 1 )с(/, к - 1) - к(к + 1)с(/, /с)), 1=2

к

(,к + 2){к + 1 )кхк = ^(Ф + + 2)х* ~ (А> - + =

к оо /к \

= 53Ф + 1)с(1,5) + £ м 53(ф +1 )с(1, з -1) - ф +1 )с(г, 5)) =

в=1 1=2 \ 5—1 /

к

5=1

оо / к \

+Е ч Е((з ++2) - ф + 1))с(/' *)-(* ++ ад *о =

г=2 \в=1 /

/с оо / к \

= 5(5 + 1)с(1, + 1 К] 2(5 + 1 )с(/, - (А; + 1)(к + 2)с(/, А;) , 6=1 1=2 \в=1 /

1 к

„ оо / к \ оо

+ мй ?'(?(в+1)с(г'5) Г * ? (с('! к]' (1'3)

1—2 \ 5—1 / /—2

Положим 2Д; = Тогда

1 ^ , . , , 2 . 1

Хк

Е 5(5 + 1)С(1' + к(к + 1)(к + 2) Х> + - кУк-

к(к + 1)(к + 2) Сделаем некоторые преобразования:

(2/ + к + 2)/с(/, /с) = (/ + к - 1 )/с(/, А; - 1) + /(/ - 1)с(/ - 1, /с),

оо

53(2/ + А; + 2)1с{1, к) = 53^ + ^ - 1)/с(/, к - 1) + 53 Щ + к)>

1=2 1=2 1=1

оо оо

53(/ + к + 1)/с(/, А;) = 53(/ + к — 1)1с{1, к- 1) + 2с(1, А;),

г=2 /=2

оо оо

+ Е^ + = ^ " + Е ^ + * ~ У + 2С(Х' *0>

г=2 1=2

к

к{к - 1)ук = 53(з(з - 1)2,в - (з - 1)(я - 2)з/Л_1) =

5=1

к / оо

= Е (5-1)53/(/ + 1)С(/;5-1)-6=1 \ /=2

оо

(s - 1) ^2(1 + 1 )lc(l, s) + 2(s - l)c(l, s) 1=2

к оо /с оо

= 2 - l)c(l, s) + Z(Z + 1) c(Z, s)-kJ2Kl + l)c(l, к).

s=l Z=2 s=l 1=2

Для к ^ 2 имеем

„ /с 1 оо к

* = ^зту 5> " 1WM) + щ^у gi(i + l)J>(i,s)-

1 оо

-^TïE^ + iMz,*)-

1=2

Положим Zk = Ф + Тогда для к ^ 2

к

Ук = Щ^Т) Х> -1)с(1's) + Mfcb) " ¡¿Г*'

Сделаем похожие преобразования

(21 + к + 2)Z(Z + l)c(Z, А;) = (Z + А; - 1)Z(Z + l)c(Z, /с - 1) + (Z + 1)1(1 - 1)с(1 -1,к),

оо оо

/=2 г=2 г=1

оо оо

53^ + к)1(1 + l)c(Z, fc) = ^2(1 + к- 1)1(1 + 1 )c(l, к-1)+ 6с( 1, А;),

г=2 1=2

к оо fc—1 оо

]T(Z + s)Z(Z + l)c(Z, s) = 53(Z + s)Z(Z + 1 )c(Z, s) + 53 6c(l, s),

s=l /=2 s=0 /=2 s=l

оо к

53(Z + A:)Z(Z + 1)C(Z,A;)=536C(1,S).

i=2 s=l

Поскольку c(l, s) = О , имеем

(К < i ¿(1 + fc)l(i + l)c(Z, fc) = о ^ £ 1 j = о g) ,

53(S-l)C(l,S) = of^i) = О (ln A;),

8=1 \S= 1 SJ

а=1 \s=l S /

1 A , , , , л Пn2k'

Xk =

ч к3

к

Наконец, с(1, s) = + О , поэтому ф + 1)с(1, s) = 2к + С(1п к) - 2 n -1 п (ы2к\

Хк~ (к + 1)(к + 2)+и{ кз к* )'

°° 4 /1п2 АЛ

Е к) = С(Х' *0 + ^ = р + ° {-¡¿г) •

Теперь мы можем оценить ЕХп(к):

оо оо

ЕXTl(k) = с(1, к) п{ 1 + 0(n, l,k)) + Y2 EPn(Z, fc). z=i i=i

Первая сумма:

Е°° /,7ч 4n /nln2 АЛ c(/,fc)n = - + 0 -p-j.

z=1 v j

Вторая сумма:

оо оо

53 с(/, /с) n |0(n, I, 53^ (2/ + =

оо оо оо

- 534/2С(/, к)++Е k2c(l>=

/=1 z=1 1=1

оо оо

= 4с(1, к) + 534/(г + - +

1=2 1=2

оо оо

+4fcc(i, /с) + 53 4lk°(liк) + Е А;2с(/' ^ =

Z=2 ¿=1

оо

(4 + 4fe)c(l, /с) + 4^ + (4/с - 4)2/л + 53 k2°(l> =

i=i

/1 1 ln/с ln2 A: Л

°U+ï+T + T + 1 =0(1)-

Третья сумма:

00 оо

1= 1 /=1

Напомним, что р( 2,0) = 1,

р(/,*0 - * -1) 21++кк~-2 + - *0211~к 1_ 2>

Для других I и к выполнено р(1, /с) = 0. Мы можем оценить /с) следующим образом:

р(1,к)^ 6

/(/ + 1)'

Действительно, несложно проверить, что функция ^щу удовлетворяет рекуррентному соотношению. Поэтому для I = 2 и /с = 0 мы используем неравенство = 1 ^ /(¿+Г) > а затем продолжаем по индукции. Таким образом, ряд Хл^К^) сходится. Другими словами, Хл^К^) = Поэтому

ЕХп(к) = ^ + 0 ] + 0(1) + 0(1) = ^ (1 + О ] + О ] ^ .

Это завершает доказательство теоремы 2. Осталось доказать леммы 1 и 2.

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

В работе [21] Боллобаш и Риодан вычислили математическое ожидание количества вершин степени в,. Однако они рассматривали только вершины степени <1 ^ п1//15 и доказали, что

4п

Еад ^ ^ + 1)^ + 2)-

А нам требуется оценка ЕЛ^(^) для всех с1. Кроме того, требуется оцепить остаточный член. Именно поэтому в этой работе заново оценивается ЕАгп(с1).

Доказательство проводится индукцией по Сначала отдельно рассмотрим два случая: <1 = 1 и (I = 2.

Рассмотрим случай с1 = 1. Очевидно, ЕАо(1) = 0. Пусть

ЕЛад = |(1 + <9(г,1)).

Тогда

ЕЛЫ1) = Е*(1) (1 - ¿Л + ^ = | (1 + 1)) ^ + ^ =

= - г + 1 -

3 V 2г + 1 2г + 1

2(г + 1)

1 -

1

+

2г2

3 V" (2г + 1)(г + 1) (2г + 1)(г + 1)

ПОЛОЖИМ 0(г + 1, 1) = (2г+1)(г+1)

0(г, 1) ~ (2г+1)(г+1)- Заметим, что 2г 1

0~(г, 1) . (1.4)

|в(г +1,1)1 ^

+

^1/(г + 1).

(2г + 1)(г + 1) (2г + 1)(г + 1)

Это завершает доказательство для <1 = 1.

Случай <1 = 2 немного отличается от с1 = 1. Очевидно, ЕЩ(2) = 0. Пусть

Е^(2) = | (1 + ^,2)). Тогда

+ ЕЛ^(1)—г + 1

Е^+1(2) = Е^(2) 1

2г + 1

« Л я/. лЛ 2i — 1 2г

= - ( 1 + 0(г, 2) )-+ -т

6 V ^ ' V 2г + 1 3(2г + 1)

2г + 1 2% + 1 1

И'

(2г - 1)г

4г

г + 1

1 +

+ 1 +-+ ---вП, 2) +-0(г, 1)

2г + 1 2г + 1 V ' } 2г + 1 ^ ' \

5 (2г — 1)г 4г

(2г - 1)г я/ \ + .ч0(г, 2) +

Положим 0(г + 1, 2)

(2г + 1)(г + 1) (2г + 1)(г + 1) 5 (2г - 1)?;

+

(2г + 1)(г + 1) (2г + 1)(г + 1) Заметим, что 0(г, 1) < 0. Поэтому

(2г - 1)г

0(г, 2) +

(2г + 1)(г + 1) 4г

(2г + 1)(г + 1)

¿(г, 1) •

0~(г,1).

4- тах

|0(г + 1,2)| ^ 5

(2г + 1)(г + 1)

(2г + 1)(г + 1) 4г

0(4/г) 0(1/г)

+

<

г + 1

(2г + 1)(г + 1) Это завершает доказательство для в, = 2.

Пусть с1 ^ 3 и мы уже доказали теорему для всех меньших степеней. Будем использовать индукцию по г. Для г = 0 имеем ЕЩ(<1) = 0. Пусть

4г

с1(с1 + 1)(с£ + 2)

1 + 0(г, (Г)) .

Тогда

ЕЛ^^) = ЕЛЭД - + ЕЛ^ - 1)^1 =

4г(2г + 1 - d) ^ + . ч + 4t х + ^

d(d + l){d + 2)(2i + l) V ') d(d+l)(2i + l)

4(г + 1) 1

d(d+l)(d + 2) V (2г + 1)(г + 1)

г(2г + 1 — d) + 2) , 1Чч

v ! в(г, d) + v ' 0{i,d- 1)

(2г + 1)(г + 1) v ' y (2г + 1)(г+1)

Если 2г -f 1 — d ^ 0, то можем взять

Л/- , л 1 i(2i + l-d) Л/. л i{d + 2) я,. , _

0(г +1, d) = -т-гт-т + т^-Г7-тг6>(г,б0+^ „w. , ч ^(г, rf— 1).

V ' ; (2г + 1)(г + 1) (2г + 1)(г + 1) У (2г + 1)(г + 1) 7

Получили следующую оценку:

^ + ^ < (2г + 1)(г + 1) + +

■ + -fcd-DK d2

(2г + 1)(г + 1) 4 ' л г + 1"

Если 2г + 2 — й ^ 0, то вершин степени d нет в графе б^"1"1. Действительно, в С^1 сумма всех степеней равна 2г + 2. Если d > 2i + 2, то ребер очевидно не хватает. Если й = 2г + 2, то легко проверить, что не может быть вершин степени d (d > 2). Поэтому можем взять в (г + 1,с£) = —1. Это завершает доказательство.

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

Очевидно, ЕРп(0, к) = ЕРП(1, к) = 0. Для всех А; > 0 имеем ЕР„(2, /с) = 0. Для /с = 0 имеем

г=1 j=i+l J i=1

Далее доказываем по индукции. Рассмотрим I ^ 3, к ^ 0. Пусть уже доказано, что EPn(z,j) ^ p{i,j) для всех г и j таких, что г < I, j ^ к или г ^ Z , j < к.

Очевидно, Pi(7, к) — 0. Легко показать, что Ei^+i(Z, к) = 0 если 2% + 4 < 2/ + к.

Если 2i + 4 = 21 + к и Pj+i(Z, fc) 0, то / = г + 2 и к = 0. И есть всего один граф с Pi+i(l, к) ф 0. Рассуждая как в конце параграфа 1.2.2, получаем, что вероятность этого графа равна ^zijtt- Из рекуррентного соотношения имеем р(1,0) = В этом случае получаем

Если 2i + 3 ^ 21 + к, то

EPi+1(Z, к) = ЕЩ, к) (l - 21 + к+1 2) + +EPi(l, к - l)ltk'i3 + EPS - 1. 1

2г + 1 v ' '2г + 1

Используя рекуррентное соотношение для р(1, к) и индукцию по г, легко показать, что ЕРП(/, &) ^ р(1, /г). Это завершает доказательство леммы 2.

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

Для доказательства этой теоремы нам потребуется неравенство Азумы (см. [13]).

Лемма 3. Пусть (Xj)"=0 - мартингал, причем \Х{ — ^ с для всех г,

1 ^ ъ ^ п. Тогда

Р(\Хп-Х0\^х)

для любого х > 0.

Зафиксируем произвольное £ > 0. Фиксируем n ^ 3 и такое к, что 1 ^ к ^ п1/6-£. Рассмотрим последовательность случайных величин Хг(к) = E(Xn(k)\G\), i = 0,...,п. Поясним обозначение E(Xn(/c)|G\). Мы строим граф Gri е 65" индуктивно. Для любого t ^ п существует и единственный граф Gi е такой, что G" получен из G\. Таким образом, E(Xn(k)\G[) -математическое ожидание количества вершин второй степени к в графе G", если на шаге t мы имеем граф G\.

Заметим, что Х°(к) = ЕХп(к) и Хп(к) = Хп(к). Нетрудно понять, что Хг(к) — мартингал.

Далее будет доказано, что для любого г = 1,..., п

\Х\к) - Х1~\к)\ ^ 10 к In п.

Теорема 3 сразу же следует из этого утверждения. Положим с = 10 fc In п. Тогда из неравенства Азумы следует, что

Р (|Хп(к) - ЕХп(к)\ 2 к v^ ln2n) ^ 2exp(-on^2?1!1i4^ I = о(1).

200 п кL In п )

Если к ^ п1//6_£, то величина п/к2 растет быстрее, чем к In2пу/п. Поэтому (к у/п In2 п) / (п/к2) = о(1). Что и требовалось доказать. Остается оценить \Хг(к) — Хг_1(А;)|.

Фиксируем г, 1 % ^ п, и некоторый граф G^-1. Заметим, что

|E(Xn(/c)|Gi) -E(Xn(k)\G[-l)\ ^

< max (EfXnWIG1;))- min {e (xn(fc)|Gi)) .

Положим G\ = argmaxE(Xri(fc)|Gi), G\ = arg min E(Xn(k)\G\). Нам нужно оценить разность E(Xn(k)\G\) — E(Xn(/c)|Gi).

Используя обозначения Nn(l,k) и Pn(l,k), введенные в параграфе 1.2.1, мы получаем

оо оо

E(X„(fc)|Gi) = + 53E(Pn(/,/c)|Gi),

1=1 i=i

оо оо

1=1 i=i

Для i ^ t ^ п, положим

- Е(^(/,/с)|01) ¿¡(Z,fc) = St{l,k)I(St(l,k) > 0),

€t(Z,fc) - E(Pt(Z,/c)|Gi) - E(Pt(Z,/c)|Gi), fc) - et{l,k)I{et(l,k) > 0),

= - Е(^(А;)|0*)), 5[{k) = ¿г(А;)/(ад > 0).

Заметим, что

оо оо

E(Xn(k)\G[) - E(Xn(k)\G\) = + <

z=i /=1

оо оо оо к

< ад, /с) + X) £ (Ü(z>я + Я) •

1=1 1=1 1= 1 7=0

Оценим полученную двойную сумму.

Сначала предположим, что п = г. Фиксируем граф Gl{~1. Графы G\ и Gj получены из графа Gl±l. Мы добавляем вершину г и одно ребро iq или iq соответственно. Новое ребро меняет только степень q или q и вторую степень соседей q или q соответственно. Рассмотрим граф G\. Фиксируем I и j ^ к. Нас интересует, насколько может вырасти количество вершин степени I и второй степени j на шаге г. Во-первых, вершина % может стать вершиной второй степени j с j ^ к. Во-вторых, вершина q может стать вершиной второй степени j с j ^ к. В-третьих, вторая степень соседа вершины q выросла. Если вершина q имеет хотя бы к + 1 соседей в графе G]~l, то после шага г эти вершины имеют вторую степень больше чем и мы не учитываем их. Если у вершины q более чем к соседей в G\~l, то не более к вершин меняют свою вторую степень па шаге г. Рассуждая аналогично, рассмотрим G\. Хотим оценить, насколько могут уменьшиться величины Ni_i(l,j) и Pi~\(l,j). Во-первых, вершина q меняет степень на шаге г. Во-вторых, некоторые соседи

д могут иметь вторую степень 1 ^ к в 0\ 1 (поэтому количество соседей д в 1 не превосходит к + 1). Просуммируем все полученные числа. Имеем

оо к 1=1 .у=0

Случай п = г разобран. Теперь рассмотрим — 1. Заметим, что

Е (ЛГт(1)|С1) - Е (М(1)|С1) - -М + 2Ь

2Ь + 1) 21 +Г

Е (МШ(2)\С\) = Е - ^^ + Е (М(1)|С?1) ¿у + ¿¿ТТ

Е (М1+1(3)\С[) = Е (ВД!^) - (МО' - 1)^1) 3 > 3,

Е (Ъ+1(и)\С\) = Е {^(и)\С\) - +

21+1 2* + 1

Е - Е (адлр» (1 _

2Ь + 1

Е(РШ(2,0)|С1) =Е(Р,(2,0)|С1) (1-^) + 1

+ 1 / 2£ + 1 Е = Е (Рг(/,з)\С\) (1 - 21 +

+Е (Р,(и - 1)\С[) + Е (Рг(/ - 1,з)\С\) / ^ 3.

Мы получали похожие равенства в доказательствах теоремы 4, леммы 1 и леммы 2. Заменим граф С\ графом (3\ или 0\ в этих равенствах Вычитая равенства с 0\ из равенств с 0\ и используя неравенство (а + Ъ)1(а + Ь > 0) ^ а1(а > 0) + Ы(Ъ > 0), мы получаем

ЪЛиХбЦи) (1-|±£) +

2/ +Л , (1-1)51(1- 1,з)

21+1

(1 + 1-1Шо-1)

24 + 1

1^2,

е[+1(2,0)^ 4(2,0)

24 + 1 ) 24 + 1

(1 + з- ъуь(1,з-1)

24 + 1

Теперь мы можем оценить сумму

Список литературы диссертационного исследования кандидат наук Прохоренкова, Людмила Александровна, 2014 год

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

Ю. Л. Павлов и М. М. Степанов. Предельные распределения числа петель случайного конфигурационного графа. Тр. МИАН, 283:212-230, 2013.

Ю. JT. Павлов. О предельных распределениях степеней вершин условного конфигурационного случайного графа. Труды Карельского научного центра РА Я, 5, 2012.

А. М. Райгородский. Модели случайных графов и их применение. Труды МФТИ, 2(4): 130—140, 2010.

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

А. М. Райгородский. Модели Интернета. Интеллект, 2013.

Е. А. Самосват. Моделирование интернета с помощью случайных графов. Диссертация на соискание ученой степени кандидата физико-математических наук, 2014.

Ф. Харари. Теория графов. Москва, "Мир", 1973.

W. Aiello, F. Chung, L. Lu. A random graph model for power law graphs. Experiment. Math., 10, 53-66, 2001.

R. Albert and A.-L. Barabasi. Statistical mechanics of complex networks. Reviews of modern physics, 74:47-97, 2002.

R. Albert, H. Jeong, and L.-A. Barabasi. Diameter of the world-wide web. Nature, 401, 130-131, 1999.

N. Alon and J. H. Spencer. Probabilistic method. Wiley-Interscience, New York, 2002.

K. Avrachenkov, D. Lebedev. PageRank of Scale-Free Growing Networks. Internet Math., 3, N2, 207-232, 2006.

K. Azuma. Weighted sums of certain dependent variables. Tohoku Math. J., 19:357-367, 1967.

A.-L. Barabasi and R. Albert. Emergence of scaling in random network. Science, 286(5439):509-512, 1999.

L.-A. Barabasi, R. Albert, II. Jeong. Scale-free characteristics of random networks: the topology of the world-wide web. Physica, A281, 69-77, 2000.

G. Bianconi and A.-L. Barabasi. Bose-Einstcin condensation in complex networks. Physical Review Letters, 86(24):5632-5635, 2001.

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

B. Bollobas. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks, pages 1-34, 2003.

B. Bollobas, Ch. Borgs, J. Chayes, O. Riordan. Directed scale-free graphs. ACM-SIAM Symposium on Discrete Algorithms, 132-139, 2003.

B. Bollobas and O. M. Riordan. The diameter of a scale-free random graph. Combinatorica, 24(l):5-34, 2004.

B. Bollobas, O. M. Riordan, J. Spencer, and G. Tusnady. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 18(3):279-290, 2001.

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Computer Networks, 33(16):309-320, 2000.

P. G. Buckley and D. Osthus. Popularity based random graph models leading to a scale-free degree sequence. Discrete Mathematics, 282:53-63, 2004.

C. Cooper. Distribution of vertex degree in web-graphs. Combinatorics, Probability and Computing, 15:637 661, 2006.

C. Cooper and A. Frieze. A general model of web graphs. Random Structures and Algorithms, 22(3):311-335, 2003.

M. Deijfen, H. van den Esker, R. van der Hofstad, and G. Hooghiemstra. A preferential attachment model with random initial degrees. Ark. Mat., 47:41-72, 2009.

S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin. Structure of growing networks with preferential linking. Phys. Rev. Lett., 85, 4633, 2000.

N. Durak, A. Pinar, T.G. Kolda, C. Seshadhri. Degree Relations of Triangles in Real-world Networks and Graph Models. In Proceedings of CIKM, 2012.

E. Drinea, M. Enachescu, and M. Mitzenmacher. Variations on random graph models for the web. Technical report, Harvard University, Department of Computer Science, 2001.

N. Eggemann and S. D. Noble. The clustering coefficient of a scale-free random graph. Discrete Applied Mathematics, 159(10):953-965, 2011.

M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. SIGCOMM Conference, 1999.

D. Gibson, R. Kumar, A. Tomkins. Discovering Large Dense Subgraphs in Massive Graphs. In Proceedings of the 31st VLDB Conference, 2005.

M. Girvan and M. E. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12) :7821-7826, 2002.

E. A. Grechnikov. An estimate for the number of edges between vertices of given degrees in random graphs in the Bollobas-Riordan model. Moscow Journal of Combinatorics and Number Theory, l(2):40-73, 2011.

E. A. Grechnikov. The degree distribution and the number of edges between nodes of given degrees in the Buckley-Osthus model of a random web graph. Internet Mathematics, 8(3), 2012.

P. Holme and B. Kirn. Growing scale-free networks with tunable clustering. Physical Review E, 65(2), 2002.

M. O. Jackson. Social and economic networks. Princeton University Press, 2010.

M. O. Jackson and A. Watts. The evolution of social and economic networks. Journal of Economic Theory, 106(2):265-295, 2002.

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. Proc. 41st Symposium on Foundations of Computer Science, 2000.

D. Lefortier, L. Ostroumova, and E. Samosvat. Evolution of the media web. In Algorithms and Models for the Web Graph, pages 80-92. Springer International Publishing, 2013.

M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random structures and algorithms, 1995.

M.E.J. Newman. Assortative mixing in networks. Phys. Rev. Letter, 89, 208701, 2002.

M.E.J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics, 46, N5, 323 351, 2005.

M. E. Newman. The structure and function of complex networks. SI AM review, 45(2): 167-256, 2003.

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. Technical report, Stanford University Database Group, 1998.

G. Pandurangan, P. Raghavan, E. Upfal. Using PageRank to Characterize Web Structure. Internet Math., 3, N1, 1-20, 2006.

R. Pastor-Satorras, A. Vázquez, A. Vespignani. Dynamical and Correlation Properties of the Internet. Phys. Rev. Lett., 87, N25, 258701, 2001.

S. H. Strogatz. Exploring complex networks. Nature, 410(6825):268-276, 2001.

M. Talagrand. Concentration of measures and isoperimetric inequalities in product spaces. Publications Mathématiques de Pl.H.E.S., 81:73-205, 1996.

D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature 393, pages 440-442, 1998.

M. Zhukovskiy, D. Vinogradov, Y. Pritykin, L. Ostroumova, E. Grechnikov, G. Gusev, P. Serdyukov, and A. Raigorodskii. Empirical validation of the Buckley Osthus model for the web host graph: degree and edge distributions. Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pages 1577 1581, 2012.

Публикации автора

[52] Jl. А. Остроумова. Математические ожидания к-х входящих степеней вершин в случайных графах в модели Боллобаша-Риордана. Труды МФТИ, 13:29-40, 2012.

[53] Л. А. Остроумова. Об r-диаметрах случайных графов в модели Боллобаша-Риордана. Труды МФТИ, 13:41-59, 2012.

[54] JI. А. Прохоренкова и Е. А. Самосват. Модели предпочтительного присоединения с устареванием. Деп. в ВИНИТИ 20.11. Ц, №319, 2014. Расширенная версия статьи находится в печати в журнале Internet Mathematics. [Е. Самосват предложил идею устаревания. J1. Прохоренковой была формализована модель, а также сформулированы и доказаны теоремы.].

[55] A. Kupavskii, L. Ostroumova, D. Shabanov, and P. Tetali. The distribution of second degrees in the Buckley-Osthus random graph model. Internet Mathematics, 9(4):297-335, 2013. [А. Купавский доказал лемму 5 в теореме о концентрации. Д. Шабанов и П. Тетали помогали в редактировании текста. Все основные результаты получены JI. Остроумовой.].

[56] L. Ostroumova and Е. Grechnikov. The distribution of second degrees in the Bollobas-Riordan random graph model. Moscow Journal of Combinatorics and Number Theory, 2(2):85-110, 2012. [JT. Остроумовой были сформулированы и доказаны основные результаты работы. А именно, введено понятие второй степени вершины и получено распределение вторых степеней в модели. Вычислено математическое ожидание количества вершин второй степени d и доказана концентрация этой величины около своего математического ожидания. Е. Гречников помог свернуть сумму в доказательстве теоремы 2.].