Введение
Глава 1 Анализ модели Боллобаша–Риордана
1.1 Определение модели и известные результаты 9
1.2 Распределение вторых степеней вершин 10
1.2.1 Введение обозначений и формулировка результатов 10
1.2.2 Доказательства теорем 12
1.3 k-е степени вершин 28
1.3.1 Введение обозначений и формулировка результатов 28
1.3.2 Доказательства теорем 30
1.4 r-диаметр 41
1.4.1 Введение обозначений и формулировка результатов 41
1.4.2 Оценка снизу 42
1.4.3 Оценка сверху 46
Глава 2 Анализ модели Бакли–Остхуса
2.1 Определение модели и известные результаты 52
2.2 Введение обозначений и формулировка результатов 53
2.2.1 Определения 53
2.2.2 Математическое ожидание 54
2.2.3 Концентрация 55
2.3 Концентрация 57
2.3.1 Интерпретация модели Бакли–Остхуса в терминах независимых случайных величин 57
2.3.2 Уменьшение количества k-вершин 58
2.3.3 Построение подходящей системы множеств K 60
2.3.4 Применение неравенства Талаграна 61
2.3.5 Доказательство теоремы 17 63
2.3.6 Обобщение на случай произвольного m 64
2.4 Оценка EYn(k) 65
2.4.1 Доказательство теоремы 15 65
2.4.2 Доказательство теоремы 13 74
2.4.3 Доказательство леммы 15 83
2.4.4 Доказательство теоремы 14 85
Глава 3 Предпочтительное присоединение с устареванием
3.1 Классические модели и свойство устаревания 87
3.2 Модель с устареванием 88
3.3 Функция привлекательности q(i)I[i t - N] 90
3.3.1 Распределение степеней 90
3.3.2 Свойство устаревания 98
3.4 Функция привлекательности q(i)eN-i 99
3.4.1 Распределение степеней 99
3.4.2 Свойство устаревания 106
3.5 Доказательства вспомогательных лемм 106
3.5.1 Доказательство леммы 23 106
3.5.2 Доказательство леммы 24 109
Заключение 114
Список литературы
