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

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

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

А.М. Райгородский
                                                                                                                                                                                                                                                                
 Модели Интернета: Учебное пособие / А.М. Райгородский –
Долгопрудный: Издательский Дом «Интеллект», 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. Пользуясь теми или иными статистическими инструментами, мы делаем те

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

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

1.2.
КОЛИЧЕСТВО РЕБЕР

Хост-граф, да и веб-граф тоже, — графы разреженные.
Принято считать, что если у такого графа n вершин, то ребер у него mn,
где m — некоторая константа, не меньшая единицы. Разумеется, это
лишь допущение. Скорее, статистика такова, что число ребер — это
Θ(n), т. е. оно зажато в пределах от m1n до m2n с постоянными m1, m2.
Почему при таких характеристиках граф разрежен? Очень просто:
даже если забыть о наличии в графе кратных ребер, за счет которых
общее количество ребер могло бы быть сколь угодно большим, все
равно на n вершинах бывает вплоть до Θ(n2) ребер, и эта функция
растет существенно быстрее линейной функции mn.
Наблюдение о разреженности графов страниц и хостов — одно из
самых первых и простых (см., например, [1–3]).

1.3.
ГИГАНТСКАЯ КОМПОНЕНТА

Понятие гигантской компоненты является одним из центральных в теории графов. Как всегда, нелепо пытаться определить его
для одного конкретного графа. Оно имеет смысл лишь для бесконечных
последовательностей графов. Итак, пусть дана последовательность графов {Gn = (Vn, En)}, в которой
lim
n→+∞ |Vn| = +∞. Говорят, что графы Gn
содержат гигантскую компоненту связности, если существует такая
константа γ > 0, что для каждого n размер наибольшей связной компоненты в Gn не меньше γ|Vn|.

1.4. Устойчивость и уязвимость
9

Одно из важнейших наблюдений в науке о «реальных сетях» (т. е.,
в частности, о веб- и хост-графах) состоит в том, что гигантская компонента в этих сетях всегда есть. Исследователи, которые не очень
склонны к черезмерной математической аккуратности (а таких в этой
области большинство), подходят к понятию гигантской компоненты даже менее формально, чем это сделали мы. Обычно они просто говорят,
что у графа (отдельного графа!) есть гигантская связная компонента,
коль скоро «существенная доля его вершин» образует такую компоненту. Разумеется, совершенно не ясно, что такое «существенная» доля.
Грубо говоря, одна сотая — это не существено, а девять десятых точно
годится. Факт тот, что даже в этом нестрогом смысле принято считать,
что и веб-, и хост-граф содержат гигантскую компоненту. Тем более они
ее содержат в смысле данного выше аккуратного определения.
И в строгом, и в нестрогом определении гигантская компонента, как
правило, ровно одна. Интуиция за этим следующая. Трудно поверить,
что, например, в хост-графе, у которого 1 000 000 000 (миллиард) вершин, может быть две связных компоненты размера 400 000 000 (четыреста миллионов) и ни одной ссылки между ними: слишком велика вероятность того, что хотя бы один владелец сайта из первой компоненты
процитирует хотя бы один сайт из второй компоненты!
Повторим, что все сказанное только что — это лишь способ осознать
суть понятия гигантской компоненты. Строгое определение дано, и в
дальнейшем мы предпочтем апеллировать только к нему.

1.4.
УСТОЙЧИВОСТЬ И УЯЗВИМОСТЬ

Исключительно важное для практики наблюдение о веби хост-графах состоит в том, что они устойчивы к случайным разрушениям (нарушениям функциональности) вершин, но уязвимы, коль
скоро атакам целенаправленно подвергаются вершины максимальной
степени — так называемые «хабы».
Строго указанные статистические результаты можно сформулировать в следующих двух теоремах (см. [4]).
Теорема 1. Пусть Gn — последовательность хост-графов, растущих с течением времени n. Пусть p ∈ (0, 1) и каждая вершина графа Gn уничтожается с вероятностью p независимо от всех остальных вершин. Тогда с вероятностью, стремящейся к единице при
n → ∞, в последовательности случайных графов Gn,p есть гигантская компонента.
Разумеется, размер гигантской компоненты (константа γ) тем меньше, чем ближе p к единице.

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

Теорема 2. Пусть Gn = (Vn, En) — последовательность хост-графов, растущих с течением времени n. Пусть c ∈ (0, 1). Упорядочим
вершины Gn по невозрастанию величины степени (имеется в виду
сумма входящей и исходящей степеней). Удалим из Gn первые [c|Vn|]
вершин (здесь [x] — целая часть числа x). Тогда существует такая
константа c∗, что при c ⩽ c∗ в графе Gn,c есть гигантская компонента, а при c > c∗ в графе Gn,c гигантской компоненты нет.

В последней теореме мы наблюдаем исключительно важное для физики явление — так называемый фазовый переход: уязвимость к атакам
на хабы возникает скачкообразно; до c∗ ее нет, но, едва мы преодолеваем порог ∼ c∗|Vn|, и граф разваливается на мелкие компоненты —
компоненты размера o(|Vn|) каждая.

1.5.
ДИАМЕТР

Как известно, диаметр графа — это максимальное расстояние между его вершинами, а расстояние в графе — это число ребер в
кратчайшем реберном пути. Разумеется, у несвязного графа, каковым
является веб-граф, диаметр не определен (или равен бесконечности).
Однако вполне можно искать диаметр гигантской компоненты. И вот
он все долгие годы исследований остается практически постоянным —
не превосходящим 10–20, — и едва ли не уменьшается (см. [3]). Это
при условии, что переходы осуществляются с учетом ориентации ребер.
Если ориентацию убрать, то диаметр уменьшается и вовсе до 5–6. Примерно то же верно и для хост-графа. Это, по сути, знаменитый закон
шести рукопожатий — статистическое наблюдение, состоящее в том,
что любые два человека в мире знакомы друг с другом через не более
чем пять посредников.
Отметим, что в свете разреженности хост-графа столь малый диаметр весьма неожидан и замечателен. По-английски это свойство принято называть «small-world phenomenon», т. е. «мир тесен» (ср. [5]).

1.6.
СТЕПЕНИ ВЕРШИН

Обозначим indeg v, outdeg v, deg v — входящую, исходящую и полную степень вершины v соответственно (петля дает вклад 1
и в indeg v, и в outdeg v, т. е. вклад 2 в deg v). Замечательный статистический закон состоит в том, что каждая из этих степеней и в веб-графе, и в хост-графе, и во многих других реальных сетях (социальных,

1.7. Вторые степени вершин
11

биологических и пр.) подчиняется степенному закону распределения
(см. [1,2]) с тем или иным показателем.

Теорема 3. Пусть Gn = (Vn, En) — последовательность реальных
сетей, растущих с течением времени n. Пусть dn ∈ N. Пусть adeg —
одна из трех видов степеней. Тогда существуют константы γ и c,
с которыми

|{v ∈ Vn : adeg v = dn}|

|Vn|
∼ c

dγ
n .

Константа γ полностью задает распределение: она является степенью, определяющей скорость убывания доли вершин данной степени dn.
Константу c можно найти из тех соображений, что сумма всех долей
(вероятностей того, что степень вершины равна dn) есть 1.
Степенные законы в сетях стали изучать задолго до появления Интернета (см., например, [6]).
Как правило, γ ∈ (2, 3). Например, для adeg = deg и хост-графа
γ ≈ 2,3 (см. [7]).

1.7.
ВТОРЫЕ СТЕПЕНИ ВЕРШИН

Степени вершин хост-графа, о которых мы писали в предыдущем разделе, свидетельствуют, в частности, об их популярности: чем
больше ссылок на данный сайт, тем он, конечно, популярнее. Однако
такую характеристику достаточно легко увеличить искусственно, создав множество фиктивных сайтов, которые будут цитировать сайт,
подлежащий раскрутке. И, разумеется, спамеры и оптимизаторы этим
активно пользуются. Поэтому важно не только количество ссылок на
сайт, но и авторитетность тех сайтов, владельцы которых эти ссылки
проставляют. В простейшем случае достаточно посмотреть на степени
тех вершин, которые соединены ребром с данной вершиной v хостграфа.
В частности, можно изучать вторую степень вершины v. Ее, в свою
очередь, можно определять по-разному. Например, можно считать ее
равной числу вершин, отстоящих на расстояние 2 от v, или числу
вершин, отстоящих на расстояние ⩽ 2 от v, или сумме степеней вершин,
отстоящих на расстояние 1 от v, и т. д. На рис. 1 показано, насколько
разнятся данные определения.
Можно показать, что вторые степени вершин подчиняются степенным законам, как и обычные степени.
Разумеется, давались определения и k-х степеней с k > 2. Но нас такие степени в дальнейшем интересовать не будут. В следующем разделе

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

Рис. 1

мы сразу дадим определение пейджранка, который в некотором роде
содержит в себе информацию обо всех степенях всех вершин графа.

1.8.
ПЕЙДЖРАНК

Пейджранк — это, при всей своей простоте, одна из самых
сильных характеристик вершины веб-графа, уточняющая в некотором
смысле понятие степени, второй степени и т. д. Пусть Gn = (Vn, En) —
веб-граф (пока именно веб-граф). Обозначим PR(v) пейджранк его вершины v. Тогда PR(i), где i ∈ {1, . . . , |Vn|}, определяется как решение
системы линейных уравнений

PR(i) = c
j→i

PR(j)

outdeg j +
c

|Vn|

j∈D
PR(j) + 1 − c

|Vn| ,
i = 1, . . . , |Vn|,

где c ∈ (0, 1) — константа, а D — множество вершин, исходящие степени которых равны нулю.
Смысл пейджранка очень простой. Мы хотим учесть не только количество ссылок на данную страницу веб-графа, но и качество ссылок.
Пусть качество — это пейджранк. Тогда качество (пейджранк) страницы i и выражается, грубо говоря, как сумма качеств (пейджранков)
страниц j, j → i, нормированных на величины outdeg j. При этом надо
учитывать, что есть страницы нулевой исходящей степени. Величина
1 − c называется вероятностью телепортации. Идея в том, что мы
можем представлять себе человека, который блуждает по сети: с вероятностью c он на очередном шаге переходит по ссылке, а с вероятностью
1 − c совершает «скачок» на случайную страницу.