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

• Малышкин Юрий Андреевич
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Малышкин Юрий Андреевич

1.1 Описание модели

1.2 Сходимость эмпирического распределения степенейвершин

1.3 Доказательство основной теоремы

2 Исследование числа вершин заданной степени

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

2.2 Доказательство закона бол ЪIII их чисел

2.3 Доказательство центральной предельной теоремы

2.4 Доказательство закона повторного логарифма

3 Асимптотический анализ максимальных степеней вершин

3.1 Основные обозначения и вспомагательные результаты

3.2 Доказательство существования выд^ел^еннои ве ттт и и ы

3.3 Доказательство основной теоремы для к=1

3.4 Доказательство основной теоремы для к>1

Заключение

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

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

N — множество натуральных чисел; Ъ — множество целых чисел; Q — множество рациональных чисел; К — множество действительных чисел;

— множество действительных неотрицательных чисел; [а\ — нижняя целая часть числа а; \а] — верхняя целая часть числа а; 1{Е} — индикатор события Е;

ЕХ — математическое ожидание случайной величины X;

ЮХ — дисперсия случайной величины X;

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

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

degG V — степень вершины V € V(С);

deg С — максимальная степень вершины в графе С;

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

/(X) = 0(д(X)) — найдется такое число С > 0, что для любого N € N выполнено неравенство \/(X)\ < С\д(X)\;

/(X) = 0(д^)) — найдутся такие числа с, С > 0, что для любого N € N выполнены неравенства с\д(^\ < \/(X) < С)\;

/ (X) ~ д^) — для люб ого £ > 0 и любого достаточно бо льшого N € N выполнены неравенства (1 — £)д^) < /(X) < (1 + £)д^); п.н. — почти наверное; Ас - дополнение к событию А; □ - конец доказательства.

Введение

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

Актуальность

Случайные графы - важный математический объект, введеный Эрдешем и Ре-ньи в работе [45]. Исследованию свойств случайных графов посвящен ряд монографий (см., например, [48, 50, 52]). Случайные графы также имеют широкое практическое применение ([32, 40, 82]). Граф Эрдеша-Реньи С(п,р)7 р € [0,1], п € N строится следующим образом. Вводится множество вершин V = \у\,.., уп} и независимые случайные величины 1 < г < ] < п, имеющие распределение Бернулли с параметром р. Если = 1, то вершины ^ и соединяются ребром.

п р р п

этой модели близка модель случайного графа С(п,т)7 п,т € N которая представляет собой равномерную выборку из всех графов с п вершинами и т ребрами. Указанные модели являются классическими и всесторонне исследованы ([31, 53]). Для них были выявлены различные асимптотические свойства (т.е. свойства, выполненные с вероятностью, стремящейся к 1 при п ^ то, см., например, [4, 5, 6]), в частности• были найдены размеры наибольшей связанной компоненты, распределение степеней вершин и диаметр полученного графа. Модель Эрдеша-Реньи является статической моделью, т.е. модель для (п + 1)-ой вершины строится без

п

мических моделях граф на (п + 1)-ой вершине определяется с помощью графа,

п

граф предпочтительного присоединения, введенный в [21].

С развитием моделей сложных сетей (таких как интернет или социальные сети) возникла необходимость в моделях, обладающих свойствами, отличными от свойств модели Эрдеша-Реньи ([17, 46, 67]). Несмотря на большое разнообразие практических приложений, в которых используются сложные сети ([14, 34, 72, 79]), они имеют ряд общих свойств. Одним из основных является степенное распределение степеней1 вершин ([16, 21, 22]). Существуют различные модели, описывающие свойства сложных сетей. В частности, стоит упомянуть конфигураци-

1 Здесь и далее приходится использовать слово степень в разных смыслах. Степень вершины - это число ее соседей (вершин, соединенных с ней ребром). Определение степенного закона распределения см., например, в 152], с. 7

онные графы (см., например, [12, 38]), графы пересечения ([29], [39]), графы с удалением ребер ([80]) и прочие модели ([76]). Отметим TBjKj)K6 Н6Д0)В н líe работы ([59, 69, 70]), в которых исследуются локальные свойства графов предпочтительного присоединения.

Графы предпочтительного присоединения достаточно хорошо описывают поведение сложных сетей ([36, 40, 43, 82]). Простейшая модель предпочтительного присоединения строится следующим образом. Имеется начальный граф P1 (для простоты обычно рассматривается граф, состоящий из двух вершин и ребра между ними, начальный граф не влияет на асимптотические свойства распределения стбпбнби вврттт -И,н ). Затем на каждом шаге построения добавляется ОДНcL верXXIИНcL«i из которой проводится одно ребро (в общем случае независимо друг от друга нап-ом шаге проводится mn ребер). Вершина, в которую проводится ребро, выбирается из уже имеющихся вершин с вероятностями, пропорциональными их степеням.

В дальнейшем были предложены различные вариации этой модели, использующие дополнительные параметры. Это позволяет строить более гибкие модели со свойствами, отличными от тех, которые присущи классическим моделям. В частности, стоит упомянуть предпочтительное присоединение (т.е. процедуру добавления вершины и ребра) с весовой функцией ([18]), последовательное предпочтительное присоединение ([28, 73]), предпочтительное присоединение с весом вершин ([41, 42, 71]) и геометрическое предпочтительное присоединение ([55]).

В диссертации исследуется новый вариант модели графов предпочтительного присоединения. На каждом шаге рассматривается набор из d вершин, выбираемых последовательно с возвращением из уже имеющихся вершин с вероятностями, пропорциональными их степеням. Затем из этих вершин по определенному правилу выбирается вершина, в которую проводится ребро из новой вершины. В диссертации это правило будет основано на учете степеней вершин в упомянутой выборке. Мы рассмотрим два случая - выбор тз(3ххтТигнTh)T ^Тигз выделенных вершин) с наименьшей степенью и с наибольшей степен ю« Предложенная модель представ ляет интерес, поскольку демонстрирует новые асимптотические свойства распре-делния степеней вершин графов, отличающиеся от тех, которые хорошо известны для классической модели предпочтительного присоединения. При этом, в отличии от известной модели Мори ([64, 65]), установлены три принципиально различных

Pn

п ^ ж>.

d

сматриваться как развитие модели с выбором наименее заполненной шарами урны ([19]). В урновой модели2 добавление должной процедуры выбора позволило

2Об урновых моделях, см., например, [63]

уменьшить порядок числа шаров в наиболее заполненной урне с ln n до lnln n. В диссертации показано, что асимптотические свойства урновой модели проявляются и в графе предпочтительного присоединения с указанным выбором вершины с наименьшей степенью. При этом порядок роста (при n ^ ж) степени вершины, имеющей максимальную степень, уменьшается с n1/2 ([21]) до lnln n ([85]). Схожий эффект был обнаружен автором работы [18], где с помощью использования сублинейной весовой функции 3 порядок максимальной степени вершины в графе был понижен с n1/2 до (log n)9, q > 1.

В отличие от главы 1, в которой величина d G N была фиксированной (и неслучайной), далее мы рассматриваем последовательность (dn)nGN независимых

N

d

d1 d d > 1). При этом вели чина dn, используемая для построен ия графа Pn+1 из графа Pn, не зависит от набора случайных величин, применяемых для построения графа Pn. Этот набор будет описан в главе 2. Теперь вместо степеней вершин графа Pn мы будем использовать в процессе пост роения графа Pn+i эти степени, измененные на некоторый параметр в > —1. Таким образом, вместо degpn v, где v G V(Pn), мы рассматриваем degpn v + в- Ограничение в > —1 обеспечивает то, что degPn v + в > 0.

В случае выбора вершины с наибольшей степенью в зависимости от параметров модели (число в > —1 и распределение случайной величины d) возможны три варианта асимптотического поведения максимальной степени вершины в графе. При Ed < 2 + в максимальная степень вершины имеет порядок nEd/(2+e\ что соответствует стардантным моделям предпочтительного присоединения ([65]). При Ed > 2+в максимальная степень вершины растет линейно non. Похожий эффект возникает при рассмотрении суперлинейной 4 весовой функции ([18]). При этом если в случае суперлинейной весовой функции предел эмпирического распределения степеней вершин вырожден (т.е. число вершин любой степени, отличной

1n рожденное эмпирическое распределение степеней вершин. Также в диссертации исследован переходный случай Ed = 2 + в, в котором максимальная степень вершины имеет порядок n/ ln n. Таким образом, удалось получить полное описание возможного асимптотического поведения максимальной степени вершины в предложенной нами модели случайных графов.

Действительная функция f (n), n G N называется сублинейной, если f (n) ~ np при n ^ œ, 0 < p < 1, см., например, [18], с. 404

Действительная функция f (n), n G N называется суперлинейной, если выполнено условие ущ <

см., например, [18], с. 403

Результаты и методы работы [85] получили продолжение в работе [51], в которой был рассмотрен выбор й-ой та величине степени вершины из г вершин для постоянных й и г. При этом новых эффектов в поведении максимальной степени вершины не наблюдается, в завсимости от соотношения между й и г максимальная степень вершины имеет либо порядок 1п1п п, либо линейный порядок.

Цели и задачи

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

При этом использовались следующие две процедуры предпочтительного при-

с о ед и н е н и я ^в е р ттт и н«

)

)

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

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

В первой главе рассматривается присоединение новой вершины к вершине с минимальной степенью среди d (определенным образом) выделенных вершин. Доказано, что в рамках предложенной модели максимальная степень вершины в графе с п вершинами растет п.н. как 1п1п п/ 1п d. Для урновой модели схожий по смыслу результат был получен в работе [19]. При этом если в урновой модели добавление

1п п 1п 1п п

нашей модели предпочтительного присоединения порядок максимальной степени вершины в графе уменьшается с п1/2 до 1п1п п.

Во второй и третьей главах рассматривается присоединение новой вершины к вершине с максимальной степенью среди d выделенных вершин (для случайного d, как было отмечено Нсь странице ). Данная модель обобщает модель, рассмотренную в [65]. При этом в случае Р^ = 1) = 1 получается модель дерева предпочтительного присоединения из [65]. Основное внимание нами уделяется исследованию максимальной степени вершины в графе в зависимости от параметров модели. Доказано, что если Ed < 2 + в, то максимальная степень вершины имеет порядок пш/(2+в (п - число вершин в графе), что соответствует степенному распределению степеней вершин, которое широко используется для моделирования сложных сетей. Если Ed > 2 + в, то в графе найдется вершина,

п

почтительного присоединения исследовался в работе [18]. В случае Ed = 2 + в

п/ 1п п

наблюдался в других моделях.

Для случаных величин Z\,Zn+1.! п € N рассмотрим порядковые статистики Z(1) < ... < Z(n+l) (порядок нумерации совпадающих величин объяснен в главе 1 на с. 12). Назовем к-ым максимумом, где к = 1,...,п + 1, величину Z(n+2-k)^ т.е. шах!<^<п+1 Zi = Z(n+1). В главе 3 при широких условиях на величину d для случаев Ed > 2 + в и Ed < 2 + в найдено для любого фиксированного к € N асимптотическое поведение (при п ^ то) величины Mk(п), являющейся к-ым максимумом для набора случайных величин degpn г = 1, ...,п + 1. Граничный случай Ed = 2 + в также рассмотрен на примере поведения первого минимума М1 (п). Удалось ДОКйЗ9)ТЬ ЧТО ДЛЯ должным образом нормированных величин М1(п) имеет место п.н. сходимость к единице, когда п ^ то.

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

Диссертация состоит из введения, трех глав, заключения, библиографии и списка обозначений.

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

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

1. Установлено, что максимальная степень вершины в графе П 1ОЧ Л' И Л' 6 л ь ного присоединения с выбором вершины наименьшей степени из d выделенных вершин имеет п.н. порядок 1п п/ 1п1п где d - произвольное фиксированное натуральное число, большее единицы.

2. Доказаны закон больших чисел, многомерные центральная предельная теорема и закон повторного логарифма для числа вершин фиксированной степени в модели предпочтительного присоединения с выбором вершины с наибольшей степенью из выделенных ^ ^^^шнн {й - случайное).

3. Для каждого к € N найдено асимптотическое поведение к-ого максимума величин degpn г = 1, ...,п + 1. Обнаружен новый эффект роста максимальной степени вершины исследуемого случайного графа при п ^ то.

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

Диссертация носит теоретический характер. Рассматриваемая модель обобщает стандартную модель предпочтительного присоединения. Она имеет дополнительные параметры, что позволяет варьировать свойства изучаемых случайных графов. Полученные результаты 11 редставляют интерес для специалистов (МГУ им. М.В. Ломоносова, СПбГУ, Математического института им. В.А. Стеклова РАН, Московского физико-технического института, Института проблем передачи информации имени А.А. Харкевича РАН, Карельского Научного центра РАН и др.), работающих в области теории случайных графов.

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

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

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

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

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

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

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

• Международная конференция студентов, аспирантов и молодых ученых "Ломоносов-2014", секция "Математика и механика" ([87], с. 1).

(АСМРТ-2017), [89], с. 55.

По теме диссертации были сделаны доклады на следующих семинарах механико-математического факультета МГУ имени М.В. Ломоносова:

• Большом

семинаре кафедры теории вероятностей под руководством академика РАН, профессора А.Н. Ширяева (2018 г.).

ководством профессора А.В. Булинского (2015-2017 гг., неоднократно).

КОВОДСТВОМ д.

ф.-м.н. Д.А. Шабанова (2016 г.).

Публикации

Основное содержание работы опубликовано ([83, 84, 85, 86]) , ИЗ них

3 включены в международные базы да] иных (Web of Science и Scopus). Имеются также опубликованные тезисы докладов международных конференциях [87, 88, 89].

Личный вклад автора

Диссертантом совместно с научным руководителем проводились выбор темы, планирование работы, постановка задачи и обсуждение полученных результатов. Результаты, изложенные в первой главе, установлены совместно с профессором Е. Paquette. При этом автором диссертации доказаны лемма 3 (сходимость эмпирического распределения степеней вершин), лемма4, лемма 5 и нижняя оценка в теореме 1. Результаты второй и третьей глав получены лично автором диссертации.

Работа по завершению диссертации проводилась в соответствии с тематическими планами НИР Тверского государственного университета в рамках проектной (№11.1937-2014-К, 2014-2016) и базовой (№3.8032.2017-БЧ) частей государственного задания

Министерства образования и науки Российской Федерации.

Благодарности

Автор признателен своему научному руководителю профессору Александру Вадимовичу Булинскому за полезные обсуждения и ценные замечания.

Глава 1

Новая модель графов предпочтительного присоединения

1.1 Описание модели

В данной главе мы рассматриваем новую модель случайных графов предпочтительного присоединения с выбором вершины, имеющей наименьшую степень среди d выделенных вершин. Опишем эту модель. Зафиксируем d Е N d > 1, и множество вершин V = {v,;}®^. Определим последовательность случайных деревьев {Pn}, n Е N, по индукции. Пусть дерево P\ состоит из вер шин v\, v2 и ребра между ними. Дерево Pn содержит вершины vi,..., vn+i. Дерево Pn+1 получается из дерева Pn добавлением вер шины vn+2 и проведением одного ребра. Обозначим V(P) - множество вершин дерева P. Тогда V(Pn+i) = V(Pn) U {vn+2}. Заметим, что сумма степеней вершин дерева Pn равнa 2n при каждом n Е N. Проведем ребро, соединяющее вершину vn+2 с некоторой верш иной Yn Е V (Pn), выбор ко-

Pn

ребер E(Pn). Точнее говоря, если имеется множество вершин V(Pn), то каждой паре вершин vi и vj сопоставляется случайная величина со значения ми 0 и 1. Если ^fj = 1 то это означает, что вершины vi и vj будут соединены ребром. Если ^i'j = 0, то ребро, соединяющее vi и vj7 не проводится. При этом мы будем считать, что = j (ребра не ориентированы). Поскольку новое ребро проводится из добавленной вершины, то Qj1 = ^j для всех i,j < n + 2. При этом степени

Pn

vi Pn обозначим degp vi) являются

борелевскими функциями от (^ij), 1 < i,j < n + 1, и

degp„ vi = £ Q. (1.1)

j=i,1<j <n+1

Упорядочим множество вершин V(Pn) по величинам их степеней. Другими словами, V(Pn) = {v(i),...,v(nn+1)}, degpn v(i-) < degpn vfi+1), i = 1, ...,n. Пусть в упоря-

доченной выборке [г^,гпп+1)} величина Ф-(п) обозначает позицию вершины г- т.е. г- = гпг& п))-> 3 = 1, ■■■,п + 1- Если степени двух вершин равны, то вершина с меньшим индексом в неупорядоченной выборке получит меньший индекс в упорядоченной выборке, т.е. если degpn гп = degpn г- и г < 3, то Фп(п) < Ф-(п). Рассмотрим независимые случайные величины [ип}пт,1<п<д7 распределенные равномерно на [0,1]. Все рассматриваемые случайные величины считаются заданными на некотором вероятностном прострастве (П, Т, Р). Построим по ним случайные величины X1,... , Хд со значениям и в V (Рп), заданные по формулам (для п € N и 1 < г < (I)

Хгп := г-), 1 < 3 < п + 1, если ^-2; < Ц* -2! ^ ^

1=1 п 1=1 п

Будем всюду считать, что сумма по пустому множеству равна нулю. Таким образом, промежуток (0,1] разбивается при каждом и € П на (случайные) полуинтервалы

IX1 г(1) — ^Рп " (I)

(Г degPn "(I) — \ 1=1 1=1

- := . , , ,

- \ ^ 2п ^ 2п

Р

построенных промежутков не убывают когда мы рассматриваем их, двигаясь от нуля к единице. Добавим точку 0 к промежутку Г™■ Промежутку — соответствует

1-|-< А тттттттттт

1 (п)

равной вершине, которая отвечает промежутку, в который попала величина и

вершина г—а вершине V- графа Рп соответствует (п). Величи на Хъп полагается

П1

т.е. Х; = V- если и\ € {,пу

Пусть Уп - вершина с наименьшей степенью из множества [X... ,Х3п} (если наименьшую степень имеют несколько вершин, выбираем вершину с наименьшим номером, указанный выбор не влияет на распределение степеней рассматриваемых вершин). Другими словами, если Х1 = г-^, Х^ = г-^, то Уп = где ,1п = ш1п[31, ...^Зд}• Поскольку для п € N и г = 1, ...^ имеем Хгп = ) тогда и только тогда, когда и П € получаем, что

,,„ „1 - degPn "т . „п^- degPn "т!

= "м} = 11Е< ,шт„1[ип} <

(1.3)

При этом 1{Уп = гп}7 г = 1,...,п + 1, для каждого п € N является борелевской функцией величин ип и degpn г^у I = 1,...,п + 1, и, следовательно, борелевской функцией величин игп1 г = 1,...,^и г,3 = 1,...,п + 1. Для завершения построения дерева Рп +1 проведем ребро из гпв Уп.

При построении дерева Рп+1 мы использовали случайные величины ип, п Е М, 1 < г < (. Для описания структуры дерева (то есть множества его ребер) Рп+1 применяются величины г] = 1, ...,п + 1. Опишем связь между указанными величинами. По построению

Е(Рп+1) = Е(Рп^ < ^п+2, Уп > . (1.4)

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

^ = &= 1, ...,п + 1, и ^++2) = ЧУп = V*},г = 1, ...,п + 2. По определению V* = ^пг&(п))- Поэтому ввиду формул (1.1) и (1.3) имеем

(п))-

^Ф+2) = 1{Уп = = 1{Уп = ^(п))}

^М-1 degp„ V» .

1 = 1 1 = 1

(п)-1 п+1 £п (п) п+1 £п

=11 Е Е^<ЕЕ

У 1=1 *=1 1=1 *=1

где $-1(п) - функция, восстанавливающая номер вершины по ее номеру в упорядоченной выборке. Таким образом, величины ^гп+1+2), п Е М, г = 1,...,п + 1, являются борелевскими функциями величин и%ю г = 1,...,( и г] = 1, ...,п + 1. Поскольку = , п Е < п + 1, ^ = 0 п,г Е N то величины ^гп+1+2),

п Е М,г = 1, ...,п + 1 п р ед с т сЬ в л я ю т собой борелевские функции от Щ*, г = 1,..., ( и С?г+1 г,] < п + 1 для всех п. Учитывая, что = <^2 = 1, по индукции получим, что величины г] < п + 2, являются борелевскими функция ми величин и

г = 1, ...,(,п Е N.

Определим последовательность сигма-алгебр п Е N. Пусть

Тх := П}, Тп := а{Щ, 1 < к < п - 1,1 < г < (}, п> 1.

Замечание 1. Как было показано выше, величины , г] = 1, ...,п + 2, п Е М, являются борелевскими функциями величин Щ, 1 < к < п, 1 < г < (, и, следовательно, Тп+1 - измеримы. Поскольку величины^п+\ г,] = 1, ...,п + 2, полностью определяют дерево Рп+1, то будут Тп+1-измеримы степени его вершин.

Лемма 1. При каждомп Е N величи ны X..., являют сяТп - независимыми и Тп-одинакого распределенными1.

хОб условных предельных теоремах, см., например, [2]

Доказательство. Введем вектор

Сп = {и1,и*;...; и^-!,и3п-1).

Положим апб = 2п^У1=1 „(I), п е N,3 = 1,...,п + 1.

Тогда в силу замечания 1 имеем апб = апб (£п). Воспользуемся следующим известным результатом (см., например, [1], гл. VI, §6). Если С и п - независимые случайные векторы со значениями соответственно то для любой огра-

ниченной борелевской функции д : ^ М верна формула

Е(д(С,п)|С = х) = Ед(х,п), х е Кт

Применим данную формулу для независимых векторов С = Сп

и п — Пп ^ где

пп = (и1,и*). Заметим, что

р X = „(',),...,Х* = = р (X = = „УС») .

Следовательно, согласно (1.2) получим

р X = ^...Х* = ^(?й)|Сп = х)

= Р (ап,Л-1(х) <и1 < ащП (х), ...,апЛ-1(х) <и* < апМ (х))

п< ап,]г (х))=[[(ап,3г - ап ,зг-1) = Ц ёР" Ьг)( )

Г=1 Г=1 Г=1

ПР (ап^г-1 (х) <ип < ап^г (х))=П(апЛг - ап^г-1) = П

2п

С

распределены на [0,1].

Подставляя теперь Сп вместо х в последнюю формулу, в частности, при d = 1 получаем, что

¿её „п

Р(ХП = у(г)1^п)= Рп (п)

2п

(п) = (^еёр„

где принято во внимание, что ¿еёр „(г) = (¿еёр ^^))(Сп)• Таким образом,

г X = „Б,,,= ) = Пр(х = „(Б).

Учитывая, что „ = „($.(п)), п е М, г = 1,...,п + 1, приходим к формулам

рX = „Г,,...,Х* = „? 1Тп) = ПрX = „г),

п=1

Р(хп = „\Тп) = , г = 1, ...,п + 1,Г = 1, ...^.

□

В силу (1.3), видим, что степень вершины Уп может быть представлена следующим образом:

п+1 п+1

аеёР„ Уп = ^ к1{аеёрп Уп = к} = ^ к £ 1{Уп = „Б)}

к=1 к=1 З'ЛвдРп ^(П/)=к

n+1 n+1

.п

v

n

k=1 j=1

J2 iideg^n vj) = k}1{Yn = vj}

degPn vm r„.j degPn v(

= £ ^ l{degPn vj) = k}l £ < i^m {un } < £ .

k=i j=i К 1=1 1=1 )

Пусть

ji = ji(n, к) = min{rn : degpn vnm) > к - 1}

и

j2 = j2(n, k) = max{m : degpn vnm) <k + 1}.

Поскольку в выборке (v«),..,vnn+1)) вершины упорядочены по возрастанию степеней, то вершинам со степенями, равными к, будут соответствовать индексы от j1 до j2 включительно (если вершины со степенями, равными к, отсутствуют, то j1 > j2)- Таким образом 1{degPn v«) = к} = 1{j1 < j < j2}} т.е. в сумме по индексу j от 1 до n + 1 ненулевыми будут только члены, соответствующие j таким, j1 < j < j2

л V {j-1 degPn г'т . ÍIr¡ x^j degPn «rn }

degp„ Yn = £ к £11 £ —^ < ^t{un} < £ —^

k=1 j=j1 Kí=1 l=1 )

V1 ы { V1 degPn «n) . m, w j degP„ «n }

= £к1 £ < ,mm/un} < £

k=1 l í=1 í=1 )

ní£d.gP.i <K) v£df^í^ví! <u«

E "{ Ó{ £ ^ <u;¡ n ni £

k=1 l=1 ) i=1 l l=1

где во второй строке учтено, что 1{и^=1АБ} = Хб=1 1{А}, если Аб П А{ = 0 при г = ¿.Для к е N и п е N рассмотрим функцию

п+1

Рп(к) :^(аеёРп „¿)1{^еёРп « > к}. (1.5)

i=1

Иначе говоря, Рп(к) равно сумме степеней вершин графа Рп, имеющих степень не менее к. В упорядоченной выборке такие вершины имеют индексы от ]1(п, к) до п + 1. При этом Рп(1) = ^П=+11 degPn «%(п) = 2п, откуда

. 1 2п р (к)

2п £ ^ «"'> = 1 - 2П £ ^ «8) = 1 - ^•

1=1 1=]1(п,к)

Заметим, что ^1(п, к) = ]2(п, к — 1) + 1. Действительно,

]1(п, к) = тт{т : degpn > к — 1} = тт{т : ^рп ^т) > к}

= тах{т : degPn «пт) < к} + 1 = ]2(п, к — 1) + 1

Поэтому

1 к(п,к) 1 2п

2п Е ^ «п) =1 — 2п Е ^ «о

1=1 1=к2(п,к)+1

.1 ^ , п Л Рп(к +1)

= 1 — ^ У degP «П) = 1----•

2п ^ ЬРп (1) 2п

1=к1(п,к+1)

Тогда имеем

<^Рп щ =£ кх{ 1 - ^ <и^\р({

к—1 \%—1 %—1

Описанная модель тесно связана с урновой моделью из [19], где рассматрива-пп При отсутствии выбора (д = 1 в наших обозначениях) новый шар попадает в урну, номер которой определяется с помощью равномерного закона, заданного на множестве индексов всех имеющихся урн. Тогда, согласно [19], самая загруженная урна содержит порядка 1пп/ 1п1пп шаров (п ^ то). Добавление в процедуру размещения шаров выбора урны (из некоторых д) с наименьшим количеством шаров существенно уменьшает этот порядок. Строго говоря, на каждом шаге мы независимо друг от друга выбираем д урн (каждую в соответствии с равномерным распределением) и кладем шар в одну из наименее загруженных урн (принцип выбора урны из наименее загруженных с равным числом шаров не играет роли). В результате в наиболее загруженной урне будет 1п1пп/ 1пд + 0(1) шаров, см. [19].

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

модели для всех урн вероятности их выбора равны. Во-вторых, в урновой модели на n-ом шаге может быть выбрана пустая урна (вероятность этого особенно велика на начальной стадии процесса), в то время как в нашей модели мы всегда увеличиваем степень вершины Ynj степень которой больше нуля (Yn Е V(Pn)). Указанные отличия ведут к появлению вершин (урн) с большими степенями. Стоит отметить, что в моделях без выбора вершины (урны) предпочтительное присоединение изменяет максимальную степень вершины (загруженность урны) einn до n1/2 (см., например, [19, 65]).

Пусть deg Pn - максимальная степень вершины в дереве Pn.

Теорема 1. В рамках описанной модели случайных графов существует случайная величина C = C(ш) такая, что

P

(

deg Pn -

in in n in d

< C для всех n > 1 = 1.

)

(1.7)

Замечание 2. Мы докажем, что существует неслучайная величина С1 > 0 такая, что

P

(

deg Pn -

in in n in d

< C1 для всex n > щ) ^ 1, n0 ^ ж.

)

(1.8)

При этом утверждение теоремы (формула (1.7)) следует из формулы (1.8). Покажем, как формула (1.8) влечет (1.7). Введем события

Ao(Ci) = {0}, Am(Ci) = |

deg Pn -

in in n in d

< C1,n > m

}

и Вт{С\) = Ат{С\)\Ат-1 (С1), т > 1. Заметим, что Ат-1(С\) С Ат(С\)} т > 1, и, следовательно, события Вт(С1) т Е М, попарно не пересекаются. Согласно (1.6) существует (неслучайная) постоянная С1 > 0 такая, что Р(А^(С1)) ^ 1 при к ^ ж. Поскольку А0(С1) = {0}, получим

P(Ak (Ci))= ^ U {Am(Cl )\Am-l(Ci)} ) ^У^ P(Bm (Ci)).

\m=1

Переходя к пределу при к ^ ж, имеем

ж

^P(Bm(Ci)) = 1.

m=1

)=^

m=1

Поэтому 1{Вт(С!)} = 1- Тогда п.н. получаем справедливость следующих

соотношении

тах

п>1

deg Рп -

1п 1п п 1п ((

оо

Е1{Вт(С\)} тах

п>1

т=1

deg Рп -

1п 1п п

1п (

ж ,

< 1{Бт(С1)} тах I С1: тах

' ^ у 1<п<т

т=1 4

deg Рп -

1п 1п п 1п (

У

= С.

С

поскольку последний ряд п.н. сходится, так как события {Бт} не пересекаются).

Вначале опишем схему доказательства теоремы 1. Заметим, что если Бп(к) > 0 для некоторого к, то в дереве Рп найдется вершина со степенью не меньшей к, а если Бп(к) < к, то степени всех вершин Рп меньше к. Действительно, согласно определению Бп(к)7 каждое слагаемое суммы, фигурируещей в формуле (1.5), равно нулю или не меньше к. Поэтому, если Бп(к) < к, то сумма равна нулю, т.е. 1{degРп VI > к} = 0, Я = 1,---,п + 1. Если deg Рп = ш, то в графе Рп есть вершина степени ш и нет вершин со степенями, большими ш. Поэтому Бп(ш) > ш и Бп(1) = 0 для I > ш. Следовательно, deg Рп = тах{ш : Бп(ш) > ш}. Таким образом, оценку deg Рп можно получить, исследуя динамику (по переменным п и к) величин Бп(к). Конкретнее, для доказательства теоремы 1 мы будем изучать поведение величин

Хп(к) := Бп+1(к) - Бп(к) (1.9)

по индексу п > 1 при каждом фиксированном к > 1. Пусть к > 1 (для к = 1 выполнено ^п(1) = 2п, поэтому Хп(1) = 2 для всех п £ М). Заметим, что

Список литературы диссертационного исследования кандидат наук Малышкин Юрий Андреевич, 2018 год

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

[1] A.B. Булинский, А.Н. Ширяев. Теория случайных процессов. Москва, ФИЗ-МАТЛИТ, 2005. - 408 с.

[2] A.B. Булинский. Условная центральная предельная теорема// Теория перо-яти. и ее примен. - 2016. - Т. 61. - №4. - С. 686—708.

[3] В.Ф. Гапошкпн, Т.П. Красулпна. О законе повторного логарифма в процессах стохастической аппроксимации// Теория вероятн. и ее примен.- 1974. - Т. 19

- №4. - С. 844-850.

[4] М. Е. Жуковский. О вероятности вхождения копии фиксированного графа в случайный дистанционный граф// Матем. заметки. - 2012. - Т. 92. - №6. -С. 844-855.

[5] М.Е. Жуковский, A.M. Райгородский. Случайные графы: модели и предельные характеристики// УМН. - 2015. - Т. 70. - №1(421). - С. 35—88.

[6] М.Е. Жуковский, А.Д. Матушкин. Универсальный k-закон нуля или единицы/ / Матем. заметки. - 2016. - Т. 99. - №4. - С. 511—525.

[7] В.М. Круглов. О неравенствах для вероятностей больших уклонений в схеме Бернулли// Теория вероятн. и ее примен.- 2004. - Т. 49. - №4. - С. 785-790.

[8] В.М. Круглов. О сходимости субмартингалов// Теория вероятн. и ее примен.

- 2008. - Т. 53. - №2. - С. 364-373.

[9] В.И. Лотов. Предельные теоремы в одной граничной задаче для случайных блужданий// Сибирский математический журнал. - 1999. - Т. 40. - №5. С. 1095-1108.

[10] В.И. Лотов. О достижении высокого уровня случайным блужданием с задержкой в нуле// Сибирский математический журнал. - 1999. - Т. 40. - №6. С. 1306-1318.

[11] М.Б. Невельсон, Р.З. Хасьминский. Стохастическая аппроксимация и рекуррентное оценивание// М.: Наука, 1972. - 307 с.

[12] Ю.Л. Павлов, Е.В. Феклистова. О предельном поведении максимальной степени вершины условного конфигурационного графа// Дискретная математика. - 2016. - Т. 28. - №2. С. 58-70.

[13] А.Н. Ширяев. Вероятность. МЦНМО, Москва, Издание ч., 2007. - 967 с.

[14] М.А. Abdullah, М. Bode, N. Foimtoulakis. Local majority dynamics on preferential attachment graphs// WAW 2015 Proceedings of the 12th International Workshop on Algorithms and Models for the Web Graph. - 2015. -Vol. 9479 - P. 95-106.

[15] R. Albert, A.-L. Barabasi. Statistical mechanics of complex networks// Rev. Modern Phys. - 2002. - Vol. 74. - №1. - P. 47-97.

[16] R. Albert, H. Jeong, and A.-L. Barabasi. Internet: diameter of the world-wide web// Nature. - 1999. - Vol. 401. - P. 130-131.

[17] R. Albert, H. Jeong, and A.-L. Barabasi. Error and attack tolerance of complex networks// Nature. - 2001. - Vol. 406. - P. 378-382.

[18] K.B. Athreya. Preferential attachment random graphs with general weight function// Internet Math. - 2008. - Vol. 4. - №4. - P. 401-418.

[19] Y. Azar, A.Z. Broder, A.R. Karlin, E. Upfal. Balanced allocations// SIAM J. Comput. - 1999. - Vol. 29. - №1. - P. 180-200.

[20] A.-L. Barabasi. Linked: The New Science of Networks. Perseus Publishing, Cambridge, Massachusetts, 2002. - 280 p.

[21] A.-L. Barabasi, R. Albert. Emergence of scaling in random networks// Science. -1999. - Vol. 286. - №5439. - P. 509-512.

[22] A.-L. Barabasi, R. Albert, H. Jeong. Scale-free characteristics of random networks: the topology of the world-wide web// Physica A. - 2000. - Vol. 311 - P. 69-77,

[23] G. Bianconi, A.-L. Barabasi. Competition and multiscaling in evolving networks// Europhys. Lett. - 2001. - Vol. 54. - P. 436-442.

[24] M. Benami. Vertex-reinforced random walks and a conjecture of Pemantle// Ann. Probab. - 1997. - Vol. 25. - P. 361-392.

[25] M. Bena'im. Dynamics of stochastic approximation algorithms// In Seminaire de probabilites XXXIII, Springer. 1999 - P. 1-68.

[26] A. Benveniste, M. Metivier, P. Priouret. Adaptive Algorithms and Stochastic Approximation. Springer, Berlin, 1990. - 365 p.

[27] E. Berger. Asymptotic behavior of a class of stochastic approximation procedures// Probab. Theoret. Fields. - 1986. - Vol. 71. - P. 517-552.

[28] N. Berger, C. Borgs, J.T. Chayes, A. Saberi. Asymptotic behavior and distributional limits of preferential attachment graphs// Ann. Probab. - 2014. -Vol. 12. AH. - P. 1-40.

[29] M. Bloznelis. Degree-degree distribution in a power law random intersection graph with clustering// WAW 2015 Proceedings of the 12th International Workshop on Algorithms and Models for the Web Graph. - 2015. - Vol. 9479. - 42-53.

[30] J.R. Blum. Multidimentional stochastic approximation methods// Ann. Math. Statist. - 1954. - Vol. 25. - №4. - P. 737-744.

[31] B. Bollobas. Random Graphs. Second edn. Cambridge Studies in Advanced Mathematics, vol. 73. Cambridge: Cambridge University Press, 2001. - 498 p.

[32] A. Bonato, N. Hadi, P. Horn, P. Pralat, C. Wang. Models of online social networks// Internet Math. - 2011. - Vol. 6. - №3. - P. 285-313.

[33] C. Borgs, J. Chayes, C. Daskalakis, S. Roch. First to market is not everything: an analysis of preferential attachment with fitness// STOC '07, June 11-13, San Diego, California, USA, 2007.

[34] P. Brach, M. Cygan, J. Lacki, P. Sankowski. Algorithmic complexity of power law networks// Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, 2016. - P. 1306-1325.

[35] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener. Graph structure in the web// Comput. Netw. - 2000. - Vol. 33. P. 309 320.

[36] P.G. Buckley, D. Osthus. Popularity based random graph models leading to a scale-free degree sequence// Discrete Math. - 2004. - Vol. 282. - №1-3 - P. 53 68.

[37] H.F. Chen. Stochastic Approximation and its Applications. Nonconvex Optimization and its Applications, Springer, 64, 2002. - 360 p.

[38] M. Deijfen, R. van der Hofstad. The winner takes it all// Ann. Appl. Probab. -2016. - Vol. 26. - №4. - P. 2419-2453.

[39] M. Deijfen, W. Kets. Random intersection graphs with tunable degree distribution and clustering// Probability in the Engineering and Informational Sciences. -

2009. - Vol. 23. - №4. - P. 661-674.

[40] S. Dereich, P. Morters. Random networks with sublinear preferential attachment: Degree evolutions// Electron. J. Probab. - 2009. - Vol. 14. - P. 1222-1267.

[41] S. Dereich, M. Ortgiese. Robust analysis of preferential attachment models with fitness// Combin. Probab. Comput. - 2014. - Vol. 23. - №3. - P. 386-411.

[42] K. Doku-Amponsah, F. Mettle, E. Nortey. Large deviation principle for the empirical degree measure of preferential attachment random graphs// International Journal of Statistics and Probability. - 2015. - Vol. 4. - №1. - P. 76-86.

[43] S.N. Dorogovtsev, J.F.F. Mendes. Evolution of networks// Adv. Phys. - 2002. -Vol. 51. - P. 1079-1187.

[44] M. Duflo. Random Iterative Models. Springer, 1997. - 385 p.

[45] P. Erdos, A. Renyi. On random graphs I// Publ. Math. (Debrecen). 1959. - Vol. 6. - P. 290-297.

[46] M. Faloutsos, P. Faloutsos, C. Faloutsos. On power-law relationships of the internet topology// ACM SIGCOMM Comput. Commun. Rev. - 1999. - Vol. 29. - №4. - P. 251-262.

[47] G. Fort. Central limit theorems for stochastic approximation with controlled markov chain dynamics// ESAIM: Probab. Stat. - 2015. - Vol. 19. - P. 60-80.

[48] A. Frieze, M. Karonski. Introduction to Random Graphs. Cambridge University Press, Cambridge, 2016. - 476 p.

[49] P. A. Galashin. Existence of a persistent hub in the convex preferential attachment model// PMS. - 2016. - Vol. 36. - №1. - P. 59-74.

[50] G. Grimmet. Probability on Graphs. Cambridge University Press, Cambridge,

2010. - 247 p.

[51] J. Haslegrave, J. Jordan. Preferential attachment with choice// Random Struct. Algor. - 2016. - Vol. 48. P. 751-766.

[52] R. Hofstag. Random Graphs and Complex Networks. Cambridge University Press, Cambridge, 2016. - 375 p.

[53] S. Janson, T. Luczak, A. Rucinski. Random Graphs. John Wiley and Sons, New York, 2011.- 336 p.

[54] N. L. Johnson, S. Kotz. Urn Models and their Application. John Wiley and Sons, New York, 1977. - 402 p.

[55] J. Jordan, A.R. Wade, Phase transitions for random geometric preferential attachment graphs// Adv. Appl. Probab. - 2015. - Vol. 47. - №2. - P. 565-588.

[56] T. Kamae, U. Krengel, G.L. O'Brien. Stochastic inequalities on partially ordered spaces// Ann. Probab. - 1977. - Vol. 5. - P. 899-912.

[57] V. Koval, R. Schwabeb. A law of the iterated logarithm for stochastic approximation procedures in d-dimensional Euclidean space/ Stoch. Process. Appl. - 2003. - Vol. 105. - P. 299-313.

[58] P. L. Krapivsky and S. Redner. Choice-driven phase transition in complex networks// JSTAT. - 2014. - Vol. 2014. - P. 4-21.

[59] A. Krot, L. Ostroumova-Prohorenkova. Local Clustering Coefficient in Generalized Preferential Attachment Models// Internet Math. - 2017. - Vol. 1. - №1.

[60] T.Z. Lai, H. Robbins. Limit theorems for weighted sums and stochastic approximation processes// Proc. Natl. Acad. Sci. USA. - 1978. - Vol. 75. - P. 1068-1070.

[61] L. Ljung, G. Pflug, H. Walk. Stochastic Approximation and Optimization of Random Systems. Birkhauser, Basel, 1992. - 116 p.

[62] V.I. Lotov. On some boundary crossing problems for Gaussian random walks// Ann. Probab. - 1996. - Vol. 24. - №4. - P. 2154-2171.

[63] H. M. Mahmoud. Polya Urn Models. Chapman and Hall/CRC, 2009. - 312 p.

[64] T.F. Mori. On random trees// Studia Sci. Math. Hungar. - 2002. - Vol. 39. - P. 143-155.

[65] T.F. Mori. The maximum degree of the Barabasi-Albert random tree// Combin. Probab. Comput. - 2005. - Vol. 14. - №3. - P. 339-348.

[66] S.V. Nagaev. Large deviations of sums of independent random variables// Ann. Probab. - 1979. - Vol. 7. - №5. - P. 745-789.

[67] M.E.J. Newman. Models of the small world// J. Stat. Phys. - 2000. - Vol. 101. -P. 819-841.

[68] M.E.J. Newman. The structure and function of complex networks// SIAM Rev. - 2003. - Vol. 45. - №2. - P. 167-256.

[69] L. Ostroumova-Prohorenkova, A. Krot. Assortativity in Generalized Preferential Attachment Models// Internet Math. - 2017. - Vol. 1. - №1.

[70] L. Ostroumova-Prokhorenkova, A. Raigorodskii, P. Pralat. Modularity of complex networks models// Internet Math. - 2017. - Vol. 1. - №1.

[71] L. Ostroumova-Prokhorenkova, E. Samosvat. Recency-based preferential attachment models// Journal of Complex Networks. - 2016. - Vol. 4. - №4. - P. 475-499.

[72] R. Palovics, A.A. Benczur. Raising graphs from randomness to reveal information networks// Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, 2017. - P. 23-32.

[73] E. Pekoz, A. Rollin, N. Ross. Joint degree distributions of preferential attachment random graphs// Adv. Appl. Probab. - 2017. - Vol. 49. - №2. - P. 368-387.

[74] M. Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms// Stoch. Process. Appl. - 1998. - Vol. 78. - P. 217-244.

[75] R. Pemantle. A Survey of Random Processes with Reinforcement Probab. Surv., Vol. 4, 2007. - 79 p.

[76] V.M. Preciado, M.A. Rahimian. Moment-based spectral analysis of random graphs with given expected degrees// IEEE Transactions on Network Science and Engineering. - 2017. - Vol. 4. - №4. - P. 215-228.

[77] A.W. Richa, M. Mitzenmacher, R. Sitaraman. The power of two random choices: A survey of techniques and results// Combinatorial Optimization. - 2001. - Vol. 9. - P. 255-304.

[78] D. Ruppert. Almost sure approximations to the Robbins-Monro and KieferWolfowitz processes with dependent noise// Ann. Probab. - 1982. - Vol. 10. -P. 178-187.

[79] C. Stegehuis, R. Hofstad, S.H. van Leeuwaarden, Johan. Power-law relations in random networks with communities// Phys. Rev. E. - 2016. - Vol. 94. - p. 012302.

[80] E. Thornblad. Asymptotic degree distribution of a duplication-deletion random graph Model// Internet Math. - 2015. - Vol. 11. - №3. - P. 289-305.

[81] W. Willinger, R. Govindan, S. Jamin, V. Paxson, S. Shenker. Scaling phenomena in the internet: Critically examining criticality// Proc. Natl. Acad. Sci. - 2002. -Vol. 99. - P. 2573-2580.

[82] S.-H. Yook, H. Jeong, A.-L. Barabasi. Modeling the internet's large-scale topology// PNAS. - 2002. - Vol. 99. - №22. - P. 13382-13386.

Работы автора по теме дисертации

Статьи в научных журналах Web of science, SCOPUS, RSCI

[83] Y. Malyshkin. Preferential attachment combined with the random number of choices// Internet Math. - 2018. - Vol. 1. - №1. - P. 1-25.

[84] Y. Malyshkin, E. Paquette. The power of choice combined with preferential attachement// Electron. Commun. Probab. - 2014. - Vol. 19. - №44. - P. 1-13.

[85] Y. Malyshkin, E. Paquette. The power of choice over preferential attachment// ALEA, Lat. Am. J. Probab. Math. Stat. - 2015. - Vol. 12. - №2. - P. 903-915.

Статьи в прочих научных журналах

[86] Y. Malyshkin. High degree vertices in the power of choice model combined with preferential attachment// Herald of Tver State University, Series: Applied Mathematics. - 2017. - Vol. 1. - P. 31-43.

Тезисы докладов на научных конференциях

[87] Ю.А. Малышкин. Модель хт j) бд j. j. о ч i' ит ел ь хтого выбора ребер для графа с растущим числом вершин// Материалы Международного Молодежного научного форума "Ломоносов-2014", Москва, 7-14 апреля 2014. - с. 1.

[88] Y. Malyshkin. High degree vertices in the preferential attachment model with choice// International Workshop "Probability, Analysis and Geometry", Lomonosov Moscow State University and Ulm University, Moscow, September 30 - October 4, 2014. - Abstracts of communication. - p.9.

[89] Y. Malyshkin. The number of vertices of fixed degree in the preferential attachment model with choice// Internetional Conference "Analytical and Computational Methods in Probability Theory and its Applications - ACMPT-2017 ", Moscow, October 23-27, 2017. Proceedings. - P. 55-59.