Моделирование интернета с помощью случайных графов

• Автор: Самосват, Егор Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 98 с. : ил.

Оглавление
Введение

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

Модели и основные характеристики сложных сетей

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

Свойства медиа-веба и модели с устареванием

Приложение моделей к задаче обхода эфемерных страниц поисковым роботом

1 Модели предпочтительного присоединения

1.1 Модель Варабаши-Альберт

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

1.1.2 ЬСБ-модель Ст}

1.1.3 Модификация ЬСО-модели: модель <3^
1.2 О числе подграфов случайного графа в модели (7^
1.2.1 Подсчет количества треугольников
1.2.2 Обобщение на случай произвольного подграфа
1.2.3 Доказательство теоремы о коротком спуске
1.2.4 Доказательство теоремы о длинном спуске
1.2.5 Доказательство теоремы о произвольном подграфе
1.3 Обобщенное предпочтительное присоединение
1.3.1 Определение РА-класса
1.3.2 Степенной закон распределения степеней вершин
1.3.3 Кластерный коэффициент
1.3.4 Полиномиальная модель
1.3.5 Описание модели, изученной эмпирически
1.3.6 Эмпирические результаты
1.3.7 Обсуждение
1.3.8 Доказательства теорем

2 Свойства медиа-веба и модели с устареванием
2.1 Базовые модели
2.2 Свойство устаревания медиа-веба
2.2.1 Данные
2.2.2 Свойство устаревания
2.3 Модель медиа-веба
2.4 Теоретический анализ предложенной модели
2.4.1 Распределение входящей степени
2.4.2 Свойство устаревания
2.5 Эмпирический анализ предложенной модели
2.5.1 Оценивание параметров
2.5.2 Правдоподобие
3 Приложение моделей к задаче обхода эфемерных страниц поисковым роботом
3.1 Формализация проблемы
3.2 Источники контента
3.3 Оптимальный обход источников
3.3.1 Теоретический анализ
3.3.2 Реализация
3.4 Эксперименты
3.4.1 Данные
3.4.2 Упрощения предложенного алгоритма
3.4.3 Результаты
3.5 Обсуждение
Заключение
Список литературы

Введение
Актуальность темы
Современный этап изучения графовой структуры сложных сетей начался сравнительно недавно, в конце 1990-х годов. По всей видимости, главным толчком к активному развитию данной области послужило появление и рост сети Интернет. Под сложными сетями обычно понимают совершенно разные графы (сети), которые встречаются в природе и обладают нетривиальными топологическими свойствами, от компьютерных и социальных сетей до биологических и экономических. Удивительно, но несмотря на столь разные области происхождения, все эти сети обладают многими общими свойствами: малый диаметр (теория шести рукопожатий), степенной закон распределения степеней вершин, выраженная кластерная структура и др., что, с одной стороны, отличает их от сильно регулярных графов вроде решеток, а с другой стороны, от случайных графов в стиле Эрдеша-Реньи. А это значит, что можно пытаться построить общую теорию подобных сетей. В эту работу включились и физики, и математики, и исследователи в области информационных технологий (computer scientists).
Физики находят аналогии между сетями и термодинамическими системами, ищут фазовые переходы в сетях, применяют методы статистической физики. Математики подходят к вопросу более формально, строго доказывая гипотезы физиков: изучение сложных сетей оказалось хорошим полигоном для приложения теории вероятностей и случайных процессов, дискретного анализа и теории графов. Исследователи в области информационных технологий пытаются извлечь практическую пользу из изучения сетевых структур: разрабатывают алгоритмы поиска сообществ в сетях и их оптимального обхода, считают PageRank и подобные ему характеристики. В этой работе автору удалось попробовать себя в каждом из этих трех амплуа.

(видим, что слагаемые с ф{а[ ^ аг} > 1 имеют большую степень по | и могут быть занесены в О (у) )
Е л К> • • • - о ЭДЕ (б • «Ґ1 ■■■■■ Ю4)
°Га2' 'а'к #{а[фа1}=
Подставим
А(а1,...,а[,...}ак) = .
выбор скобок, из которых берутся индикаторы выбор (I
Получим
(1.13)=е(1)ее сё-1--
<=1 о'(< Й,
(1 + 014] ) <
(6-• «г«г)
£ ®т Е Е °:'г'£ (б ■«)“ ■■■■■«)" ■■■■■ КГ) ■
£=1 а[<аі
■(т)^(1 + 0(ї ))-Е(6-(4Г--Ю")(?)^-в(1).
Мы получили, что вклад побочных членов не превосходит вклада главного члена. Теорема доказана.
1.2.5 Доказательство теоремы о произвольном подграфе
Выражения, подобные (1.1) и (1.6), могут быть записаны и для произвольного подграфа. Общий случай отличается тем, что произвольный подграф (Зо может быть вложен в разными способами, имеющими одно и то же множество вершин, но разные множества ребер. Рассмотрим, например, случай бо = К2.2, который мало отличается от случая произвольного (?о-