Введение
1 Модели предпочтительного присоединения 11
1.1 Модель Барабаши-Альберт 11
1.1.1 Предпочтительное присоединение 11
1.1.2 LCD-модель G^ 13
1.1.3 Модификация LCD-модели: модель Gvm 15
1.2 О числе подграфов случайного графа в модели G^ 16
1.2.1 Подсчет количества треугольников 16
1.2.2 Обобщение на случай произвольного подграфа 25
1.2.3 Доказательство теоремы о коротком спуске 28
1.2.4 Доказательство теоремы о длинном спуске 30
1.2.5 Доказательство теоремы о произвольном подграфе . 35
1.3 Обобщенное предпочтительное присоединение 38
1.3.1 Определение РА-класса 38
1.3.2 Степенной закон распределения степеней вершин . 39
1.3.3 Кластерный коэффициент 40
1.3.4 Полиномиальная модель 43
1.3.5 Описание модели, изученной эмпирически 44
1.3.6 Эмпирические результаты 45
1.3.7 Обсуждение 48
1.3.8 Доказательства теорем 49
2 Свойства медиа-веба и модели с устареванием 56
2.1 Базовые модели 56
2.2 Свойство устаревания медиа-веба 57
2.2.1 Данные 57
2.2.2 Свойство устаревания 58
2.3 Модель медиа-веба 58
2.4 Теоретический анализ предложенной модели 59
2.4.1 Распределение входящей степени 59
2.4.2 Свойство устаревания 62
2.5 Эмпирический анализ предложенной модели 64
2.5.1 Оценивание параметров 65
2.5.2 Правдоподобие 65
3 Приложение моделей к задаче обхода эфемерных страниц по исковым роботом 70
3.1 Формализация проблемы 70
3.2 Источники контента 73
3.3 Оптимальный обход источников 76
3.3.1 Теоретический анализ 76
3.3.2 Реализация 80
3.4 Эксперименты 82
3.4.1 Данные 83
3.4.2 Упрощения предложенного алгоритма 84
3.4.3 Результаты 85
3.5 Обсуждение 89
Заключение 92
Список литературы 94
