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

• Автор: Прохоренкова, Людмила Александровна
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 119 с. : ил.

Оглавление

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

Введение

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

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

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

Глава 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 Доказательство теоремы
2.4.2 Доказательство теоремы
2.4.3 Доказательство леммы
2.4.4 Доказательство теоремы
Глава 3 Предпочтительное присоединение с устареванием
3.1 Классические модели и свойство устаревания
3.2 Модель с устареванием
3.3 Функция привлекательности д(г)1^ > £ — ./V]
3.3.1 Распределение степеней
3.3.2 Свойство устаревания
3.4 Функция привлекательности д(г)е «
3.4.1 Распределение степеней
3.4.2 Свойство устаревания
3.5 Доказательства вспомогательных лемм
3.5.1 Доказательство леммы
3.5.2 Доказательство леммы
Заключение
Список литературы

Список основных обозначений
V(G) — множество вершин графа G;
E(G) — множество ребер графа G;
ij € G — ребро ij принадлежит графу G
t Є G — вершина t принадлежит графу G;
f(n) — o(g(n)) - - для любого числа с > 0 существует такое число щ, что для любого п > ?го выполнено неравенство |/(п)| < сд{п)]
/(п) = 0{д(п)) — существуют такие числа С > 0 и щ, что для любого п > по выполнено неравенство f(n) ^ Сд{п)|;
/(п) = — существуют такие числа Сі > 0, Сі > 0 и щ, что для
любого п > щ выполнено неравенство С ■ д{п) ^ /(n) ^ С2 • д{п)
/(■) = 9(g(j) - выполнено неравенство |/(-)| ^ |<7(')1’>
f(x) ~ д{х) — функции асимптотически равны при х —> оо, то есть
f(x) = д(х) ■ (1 + о(1));
1(Х) — индикатор события X. То есть 1(Х) — 1 в случае, если X выполняется, и 0 - иначе;
С* число сочетаний из п элементов по к
|Л| - мощность множества А.

С к2 <
In /n/i
. k-
Ck2 ( R
2xt V П V x
fe-2 Ck2 (lnv/njtj
dec — '
t{k — 1)
Итак,
E#fc+i(£) - (l + di(t))k+1 i f ^ (^ln + 0s (£)^ -
fc(04(O + 05(*))

(1 + адГ1.
Положим 0(А; + 1, А, га) = Осталось лишь проверить, что эта вели-
(1пУт)
чина достаточно мала:
в (к + 1, t, п) In
k(e4(t) + 65(t))

fc С A;3 C(fc + 1)2 < ш: + — ^

Последнее неравенство выполнено для любых к>2иС^1. Теорема доказана.
Доказательство теоремы
Доказательство этой теоремы будет аналогично доказательству теоремы 5. Фиксируем натуральное число т ^ 2. Помним, что граф С"г получается из графа С”т объединением вершин в группы по т. Вершина Ь в С1п получена из вершин т(Ь — 1) + 1, rn.it — 1) + 2,..., тЬ. Положим N = тп.
Для начала посмотрим, что происходит с математическим ожиданием степени вершины А в графе С", . Нужно сложить математические ожидания степеней вершин графа Сг, из которых получена вершина £:

Ed{t) = ]Г

/ лг /
J-(l + 0(l/«))= У /Д(1+0(1/т1 )) =
^ V v
i—m(t—1)+
Хотим доказать, что для любого к ^
ЕдДА) = тк /*(£, п) (1 + 9(к, А, га)) (1 + 0! (А)/
где |0(Д t, п) С
г, < <5Д.
4 111 Jnjt ’ 1 1,4 ^ 1
Докажем аналог леммы 4 в нашем случае.