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

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

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

Второе издание

À.Ì. Ðàéãîðîäñêèé

Ìîäåëè Èíòåðíåòà: Ó÷åáíîå ïîñîáèå / À.Ì. Ðàéãîðîäñêèé – 2-å èçä. –

Äîëãîïðóäíûé: Èçäàòåëüñêèé Äîì «Èíòåëëåêò», 2019. – 64 ñ.

ISBN 978-5-91559-260-4

Ó÷åáíîå ïîñîáèå ïîñâÿùåíî ìîäåëèðîâàíèþ Èíòåðíåòà, êîòîðûé áûë
äèêîâèíêîé äëÿ áîëüøèíñòâà èç íàñ åùå êàêèõòî 20 ëåò íàçàä. Ñåé÷àñ
ìû åæåäíåâíî ïîëüçóåìñÿ ðåñóðñàìè Èíòåðíåòà ïîèñêîì, ýëåêòðîííîé
ïî÷òîé, áëîãàìè è äð. Ñåòü äèíàìè÷íî ðàçâèâàåòñÿ, ðàñòåò è óñëîæíÿåòñÿ,
à ïîòîìó ðÿäîâîìó ïîëüçîâàòåëþ ìîæåò êàçàòüñÿ, ÷òî â Èíòåðíåòå öàðèò
ïîëíûé õàîñ. Îäíàêî â ðåàëüíîñòè âñå óñòðîåíî íàìíîãî èíòåðåñíåå.
Ìíîãî÷èñëåííûå ñòàòèñòè÷åñêèå èññëåäîâàíèÿ ïîêàçûâàþò, ÷òî åñòü
ðÿä çàêîíîâ, êîòîðûì ïîä÷èíÿåòñÿ «âñåìèðíàÿ ïàóòèíà».  ÷àñòíîñòè,
ýòè çàêîíû ñâÿçàíû ñ èíòåðïðåòàöèåé Èíòåðíåòà êàê ãðàôà, âåðøèíû
êîòîðîãî ñàéòû, à ðåáðà ãèïåðññûëêè. Â êíèãå îïèñàíû îñíîâíûå çàêîíû
òàêîãî òèïà è ðàññêàçàíî, êàê ñîâðåìåííàÿ ìàòåìàòèêà ïîìîãàåò èõ ìîäåëèðîâàòü.
Äëÿ ïîíèìàíèÿ êíèãè ÷èòàòåëþ ïîíàäîáèòñÿ çíàíèå îñíîâ êîìáèíàòîðèêè, òåîðèè ãðàôîâ è òåîðèè âåðîÿòíîñòåé. Êíèãà áóäåò ïîëåçíà ñòóäåíòàì, àñïèðàíòàì è ïðåïîäàâàòåëÿì òåõíè÷åñêèõ ÂÓÇîâ, à òàêæå âñåì, êòî
èíòåðåñóåòñÿ ïðèëîæåíèÿìè ìàòåìàòèêè ê ìîäåëèðîâàíèþ «ñëîæíûõ ñåòåé» Èíòåðíåòà, ñîöèàëüíûõ, áèîëîãè÷åñêèõ, òðàíñïîðòíûõ è äðóãèõ ñåòåé.
Ïåðâîå èçäàíèå êíèãè øèðîêî èñïîëüçóåòñÿ â ðîññèéñêèõ óíèâåðñèòåòàõ è ñïåöèàëèñòàìè ïî èíôîðìàöèîííûì òåõíîëîãèÿì.

© 2018, À.Ì. Ðàéãîðîäñêèé
© 2019, ÎÎÎ Èçäàòåëüñêèé Äîì
«Èíòåëëåêò», îðèãèíàë-ìàêåò,
îôîðìëåíèå

ISBN 978-5-91559-260-4

Êîìïüþòåðíàÿ âåðñòêà – ÈÄ «Èíòåëëåêò»
Êîððåêòóðà – àâòîðà
Îòâåòñòâåííûé çà âûïóñê – Ë.Ô. Ñîëîâåé÷èê

Ôîðìàò 60õ90/16. Ïå÷àòü îôñåòíàÿ. Ãàðíèòóðà Íüþòîí.
                             Ïå÷. ë. 4. Çàê. ¹
Áóìàãà îôñåòíàÿ ¹ 1, ïëîòíîñòü 80 ã/ì2

Èçäàòåëüñêèé Äîì «Èíòåëëåêò»
141700, Ìîñêîâñêàÿ îáë., ã. Äîëãîïðóäíûé,
Ïðîìûøëåííûé ïð-ä, ä. 14, òåë. (495) 617-41-85

Îòïå÷àòàíî â òèïîãðàôèè
ÎÎÎ «Áóêè Âåäè»

ОГЛАВЛЕНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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

ВВЕДЕНИЕ

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

Введение

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

Г Л А В А
1

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

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

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