Модели Интернета

А.М. РАЙГОРОДСКИЙ

МОДЕЛИ 
ИНТЕРНЕТА

А.М. Райгородский
                                                                                                                                                                                                                                                                
 Модели Интернета: Учебное пособие / А.М. Райгородский –
Долгопрудный: Издательский Дом «Интеллект», 2013. – 64 с.

ISBN 9785915591430

Учебное пособие посвящено моделированию Интернета, который был диковинкой для большинства из нас еще какихто 15 лет назад. Сейчас мы ежедневно пользуется ресурсами Интернета поиском, электронной почтой, блогами и
др. Сеть динамично развивается, растет и усложняется, а потому рядовому
пользователю может казаться, что в Интернете царит полный хаос. Однако в
реальности все устроено намного интереснее.
Многочисленные статистические исследования показывают, что есть ряд законов, которым подчиняется «всемирная паутина». В частности, эти законы
связаны с интерпретацией Интернета как графа, вершины которого сайты, а
ребра гиперссылки. В книге описаны основные законы такого типа и рассказано, как современная математика помогает их моделировать.
Для понимания книги читателю понадобится знание основ комбинаторики,
теории графов и теории вероятностей. Книга будет полезна студентам, аспирантам и преподавателям технических ВУЗов, а также всем, кто интересуется
приложениями математики к моделированию «сложных сетей» Интернета,
социальных, биологических, транспортных и других сетей.

ISBN 9785915591430
© 2013, А.М. Райгородский
© 2013, ООО Издательский Дом
«Интеллект», оригиналмакет,
оформление

ОГЛАВЛЕНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Глава 1. Свойства Интернета . . . . . . . . . . . . . . . . . . . . . . . .
7

1.1. Основные объекты и общая идеология их изучения . . . . . . . . . .
7
1.2. Количество ребер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.3. Гигантская компонента . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.4. Устойчивость и уязвимость . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.5. Диаметр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.6. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.7. Вторые степени вершин. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.8. Пейджранк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.9. Количество ребер между вершинами заданных степеней . . . . . .
13
1.10. Корреляции степеней вершин . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.11. Кластерные коэффициенты . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.12. Число копий фиксированного графа . . . . . . . . . . . . . . . . . . . .
17

Глава 2. Модели хост-графов . . . . . . . . . . . . . . . . . . . . . . . .
19

2.1. Общая концепция. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.2. Модель Эрдеша–Реньи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3. Модели Барабаши–Альберт . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.4. Модель Боллобаша–Риордана: определения . . . . . . . . . . . . . . .
24
2.4.1. Динамическое определение модели . . . . . . . . . . . . . . . . .
24
2.4.2. Статическое определение модели . . . . . . . . . . . . . . . . . .
26
2.5. Модель Боллобаша–Риордана: результаты . . . . . . . . . . . . . . . .
28
2.5.1. Гигантская компонента, устойчивость и уязвимость . . . . . .
28
2.5.2. Диаметр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

Оглавление

2.5.3. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.5.4. Вторые степени вершин . . . . . . . . . . . . . . . . . . . . . . . .
30
2.5.5. Пейджранк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.5.6. Количество ребер между вершинами заданных степеней . .
33
2.5.7. Кластерные коэффициенты . . . . . . . . . . . . . . . . . . . . . .
34
2.5.8. Число копий фиксированного графа . . . . . . . . . . . . . . . .
34
2.6. Уточнения модели Боллобаша–Риордана: начальная притягательность
вершины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
2.6.1. Несколько вводных замечаний . . . . . . . . . . . . . . . . . . . .
36
2.6.2. Модель Бакли–Остгуса . . . . . . . . . . . . . . . . . . . . . . . . .
36
2.6.3. Модель Мори . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.6.4. Степени вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.6.5. Вторые степени вершин . . . . . . . . . . . . . . . . . . . . . . . .
38
2.6.6. Количество ребер между вершинами заданных степеней . .
39
2.6.7. Кластерные коэффициенты . . . . . . . . . . . . . . . . . . . . . .
40
2.6.8. Число копий фиксированного графа . . . . . . . . . . . . . . . .
41
2.6.9. Удивительное соответствие модели Бакли–Остгуса реальному хост-графу . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
2.6.10. Классификация ссылочного спама . . . . . . . . . . . . . . . . .
44
2.7. Дальнейшие уточнения модели Боллобаша–Риордана. . . . . . . . .
44
2.7.1. Несколько вводных замечаний . . . . . . . . . . . . . . . . . . . .
44
2.7.2. Модель Боллобаша–Боргса–Риордана–Чайес . . . . . . . . . .
45
2.7.3. Модель копирования. . . . . . . . . . . . . . . . . . . . . . . . . . .
47
2.7.4. Модель Купера–Фриза . . . . . . . . . . . . . . . . . . . . . . . . .
49
2.7.5. Модель Холма–Кима . . . . . . . . . . . . . . . . . . . . . . . . . .
51

Глава 3. Схемы и идеи некоторых доказательств . . . . . . . .
53

3.1. Несколько вводных слов . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
3.2. Схема доказательства теоремы 9 . . . . . . . . . . . . . . . . . . . . . .
53
3.3. Схема доказательства теоремы 10 . . . . . . . . . . . . . . . . . . . . . .
56
3.4. Неравенства плотной концентрации и теоремы об асимптотическом
распределении. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
3.4.1. Несколько вступительных слов . . . . . . . . . . . . . . . . . . .
57
3.4.2. Неравенство Чебышёва . . . . . . . . . . . . . . . . . . . . . . . . .
57
3.4.3. Неравенство Азумы–Хёффдинга . . . . . . . . . . . . . . . . . . .
58
3.4.4. Неравенство Талаграна . . . . . . . . . . . . . . . . . . . . . . . . .
59

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

ВВЕДЕНИЕ

Еще каких-то 15 лет назад про существование сети Интернет мало кто знал. Сейчас же Интернет прочно вошел в нашу жизнь,
став для нас незаменимым инструментом получения и распространения
информации, а также, конечно, общения. Поиск, электронная почта,
блоги, социальные сети, скайп и пр., — без этого многие уже не могут обойтись. Всемирная паутина невероятно разрослась за эти годы.
Может показаться даже, что в ней царит полный хаос: так велика она
и, на первый взгляд, неконтролируема. И тем не менее, существуют
законы, по которым развивается Интернет. Изучение этих законов так
же увлекательно, как и изучение законов природы. Начато оно было
практически одновременно с появлением сети. И к настоящему времени
возникла целая научная дисциплина, лежащая на стыке физики, математики и социологии.
Этой небольшой книгой мы открываем серию брошюр, посвященных
исследованиям Интернета. Здесь мы сделаем акцент на интерпретации
Интернета как графа, вершины которого, в зависимости от контекста,
суть страницы или сайты (хосты), а ребра — (гипер)ссылки между
ними. Об удивительных свойствах этого графа — графа, растущего с
течением времени, — и о неожиданно простых моделях, в которых эти
свойства реализуются, мы и поговорим в книге.
Для понимания книги читателю потребуются начальные знания в
области комбинаторики, теории графов и теории вероятностей. Структурно книга устроена следующим образом. В первой главе мы расскажем о многочисленных характеристиках Интернета, которые изучались
и продолжают изучаться исследователями. Эти-то характеристики и покажут, насколько ошибочно первоначальное впечатление о полном хаосе, якобы царящем во всемирной паутине. Во второй главе мы опишем

Введение

несколько вероятностных моделей веба и сформулируем теоретические
результаты, которые выявят как сильные, так и слабые стороны моделей. При этом мы пройдем основные этапы того пути, который прошли
исследователи Интернета: от простейших моделей конца 90-х годов
ХХ века до значительно более точных моделей, возникших буквально
в последние несколько лет. Правда, мы будем следовать лишь одному
из важнейших направлений в идеологии построения моделей. А именно,
мы обсудим только идею так называемого предпочтительного присоединения. Это уже огромный пласт современной Интернет-математики. Его
мы и постараемся вскрыть в нашей первой книге. Наконец, в третьей
главе мы приведем схемы доказательств некоторых теорем из второй
главы.

Г Л А В А
1

СВОЙСТВА ИНТЕРНЕТА

1.1.
ОСНОВНЫЕ ОБЪЕКТЫ
И ОБЩАЯ ИДЕОЛОГИЯ ИХ ИЗУЧЕНИЯ

Существуют два типа графов, возникающих при изучении
всемирной паутины. С одной стороны, можно считать вершинами графа
компьютеры, подключенные к Интернету, или серверы, через которые
идет Интернет-коммуникация. В этом случае ребрами являются линии
связи. Это такой граф «из железа». Он называется Интернет-графом,
и он нас не будет интересовать. Нашим объектом послужит более «виртуальный» граф. Его вершины — это страницы или сайты в Интернете,
а ребра — (гипер)ссылки между ними. Если вершины — страницы, граф
называется веб-графом; если вершины — сайты (хосты), граф называется хост-графом. Хост-граф проще для статистического анализа, так
как он гораздо меньше веб-графа. В хост-графе есть и кратные ребра
(несколько различных ссылок с одного сайта на другой), и (кратные)
петли (ссылки между страницами внутри сайта), и, конечно, хост-граф
(как и веб-граф) ориентирован. Мы будем, как правило, говорить о
хост-графах.
Предположим, нас интересует какая-то статистика хост-графа. Например, число ребер в нем. Разумеется, желая узнать ее приблизительное значение, мы действуем так же, как и всегда в статистическом
анализе. Мы берем достаточно репрезентативную (большую) выборку,
состоящую из хост-графов, которые получены в результате взятия надлежащего количества «временн ´ых срезов». И для каждого из этих графов мы считаем число ребер xi. Получается выборка x1, . . . , xn. Пользуясь теми или иными статистическими инструментами, мы делаем те