Наука о сетях: вводный курс

Филиппо Менцер, Санто Фортунато и Клейтон А. Дэвис

Наука о сетях: вводный курс

A First Course in Network Science

FILIPPO MENCSER

SANTO FORTUNATO

CLAYTON A. DAVIS

Наука о сетях: вводный курс

ФИЛИППО МЕНЦЕР

САНТО ФОРТУНАТО

К ЛЕЙТОН А. ДЭВИС

Москва, 2022

УДК004.7
ББК16.263
М50

МенцерФ.,ФортунатоС.,ДэвисК.А.
М50 Наука о сетях: вводный курс / пер. с англ. А. В. Логунова. – М.: ДМК Пресс, 

2022. – 338 с.: ил. 

ISBN978-5-97060-984-2

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

УДК 004.7
ББК 16.263

This translation of A First Course in Network Science is published by arrangement with Cambridge 
University Press. Russian-language edition copyright © 2021 by DMK Press. All rights reserved.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой 
бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав.

ISBN 978-1-10847-113-8 (англ.) 
©  Filippo Menczer, Santo Fortunato,  
and Clayton A. Davis, 2020
ISBN 978-5-97060-984-2 (рус.) 
©  Перевод, оформление, издание,  

ДМК Пресс, 2022

Коллин, Массимилиано, Айрис: спасибо.
– Филиппо Менцер

Моим родителям и брату.
– Санто Фортунато

Лиз, Джина, Мэри Джо и Джей: ваша любовь и поддержка значат для меня все.
– Клейтон Дэвис

 
 
Содержание

Предисловие .................................................................................................................... 10

Признательности ............................................................................................................. 16

Введение ........................................................................................................................... 17
0.1 Социальные сети............................................................................................... 18
0.2 Коммуникационные сети ............................................................................... 21
0.3 Всемирная паутина и «Википедия» ............................................................. 24
0.4 Интернет ............................................................................................................. 26
0.5 Транспортные сети ........................................................................................... 27
0.6 Биологические сети .......................................................................................... 29
0.7 Резюме ................................................................................................................. 30
0.8 Дальнейшее чтение .......................................................................................... 31
Упражнения................................................................................................................. 32

1Сетевыеэлементы .................................................................................................... 34
1.1 Базовые определения ...................................................................................... 34
1.2 Манипулирование сетями в исходном коде .............................................. 36
1.3 Плотность и разреженность ........................................................................... 39
1.4 Подсети ............................................................................................................... 42
1.5 Степень ................................................................................................................ 43
1.6 Направленные сети .......................................................................................... 44
1.7 Взвешенные сети .............................................................................................. 45
1.8 Многослойные и темпоральные сети .......................................................... 46
1.9 Представления сетей ....................................................................................... 49
1.10 Рисование сетей ................................................................................................ 51
1.11 Резюме ................................................................................................................. 52
1.12 Дальнейшее чтение .......................................................................................... 53
Упражнения................................................................................................................. 53

2Малыемиры ............................................................................................................... 58
2.1 Рыбак рыбака видит издалека ....................................................................... 58
2.2 Пути и расстояния ............................................................................................ 62
2.3 Соединенность и компоненты ...................................................................... 67
2.4 Деревья ................................................................................................................ 69

Содержание

2.5 Отыскание кратчайших путей ...................................................................... 71
2.6 Социальное расстояние................................................................................... 75
2.7 Шесть степеней сепарации ............................................................................. 78
2.8 Друг моего друга ............................................................................................... 81
2.9 Резюме ................................................................................................................. 84
2.10 Дальнейшее чтение .......................................................................................... 85
Упражнения................................................................................................................. 86

3Хабы .............................................................................................................................. 94
3.1 Меры центральности ....................................................................................... 95
3.1.1 Степень .................................................................................................... 95
3.1.2 Близость ................................................................................................... 95
3.1.3 Промежуточность .................................................................................. 96
3.2 Распределения значений центральности ................................................... 99
3.3 Парадокс дружбы .............................................................................................104
3.4 Ультрамалые миры ..........................................................................................107
3.5 Устойчивость.....................................................................................................108
3.6 Разложение ядра ..............................................................................................110
3.7 Резюме ................................................................................................................112
3.8 Дальнейшее чтение .........................................................................................113
Упражнения................................................................................................................113

4Направленияи веса .................................................................................................119
4.1 Направленные сети .........................................................................................119
4.2 Всемирная паутина .........................................................................................120
4.2.1 Краткая история Всемирной паутины ............................................121
4.2.2 Как работает Всемирная паутина .....................................................122
4.2.3 Обходчики Всемирной паутины .......................................................124
4.2.4 Структура Всемирной паутины ........................................................127
4.2.5 Тематическая локальность .................................................................129
4.3 Метрика Page Rank ...........................................................................................132
4.4 Взвешенные сети .............................................................................................137
4.5 Информация и дезинформация ...................................................................138
4.6 Сети совместной встречаемости ..................................................................143
4.7 Весовая гетерогенность..................................................................................147
4.7.1 Трафик Всемирной паутины .............................................................147
4.7.2 Фильтрация связей ..............................................................................149
4.8 Резюме ................................................................................................................151
4.9 Дальнейшее чтение .........................................................................................153
Упражнения................................................................................................................155

5Сетевыемодели ........................................................................................................162
5.1 Случайные сети ................................................................................................162
5.1.1 Плотность ...............................................................................................165
5.1.2 Степенное распределение ..................................................................166

Содержание

5.1.3 Короткие пути .......................................................................................168
5.1.4 Коэффициент кластеризации ............................................................169
5.2 Малые миры ......................................................................................................170
5.3 Конфигурационная модель ...........................................................................174
5.4 Преференциальное прикрепление .............................................................177
5.5 Другие преференциальные модели ............................................................182
5.5.1 Модель на основе привлекательности ............................................184
5.5.2 Модель на основе приспособленности ...........................................185
5.5.3 Модель на основе случайного блуждания ......................................187
5.5.4 Модель на основе копирования ........................................................190
5.5.5 Модель на основе ранга ......................................................................191
5.6 Резюме ................................................................................................................193
5.7 Дальнейшее чтение .........................................................................................194
Упражнения................................................................................................................194

6Сообщества ................................................................................................................200
6.1 Базовые определения .....................................................................................203
6.1.1 Переменные сообщества ....................................................................203
6.1.2 Определения cообщества ...................................................................205
6.1.3 Разделы ...................................................................................................207
6.2 Смежные проблемы ........................................................................................209
6.2.1 Деление сети на разделы ....................................................................209
6.2.2 Кластеризация данных .......................................................................212
6.3 Обнаружение сообществ ................................................................................215
6.3.1 Устранение мостов ...............................................................................216
6.3.2 Оптимизация модулярности .............................................................218
6.3.3 Распространение меток ......................................................................225
6.3.4 Стохастическое блочное моделирование .......................................227
6.4 Оценивание методов ......................................................................................230
6.4.1 Искусственные эталоны......................................................................230
6.4.2 Реально существующие эталоны ......................................................233
6.4.3 Сходство между разделами ................................................................234
6.5 Резюме ................................................................................................................236
6.6 Дальнейшее чтение .........................................................................................237
Упражнения................................................................................................................238

7Динамика ....................................................................................................................244
7.1 Идеи, информация, влияние ........................................................................246
7.1.1 Пороговые модели ...............................................................................247
7.1.2 Независимо-каскадные модели .......................................................250
7.2 Распространение эпидемий..........................................................................252
7.2.1 Модели SIS и SIR ...................................................................................254
7.2.2 Распространение слухов .....................................................................259
7.3 Динамика мнений ...........................................................................................261
7.3.1 Дискретные мнения ............................................................................262
7.3.2 Непрерывные мнения .........................................................................265

Содержание

7.3.3 Коэволюция сетей и динамика .........................................................267
7.4 Поиск ..................................................................................................................270
7.4.1 Локальный поиск..................................................................................270
7.4.2 Доступность поиска .............................................................................273
7.5 Резюме ................................................................................................................278
7.6 Дальнейшее чтение .........................................................................................280
Упражнения................................................................................................................281

ПриложениеА.РуководствопоязыкуPython ............................................................288
A.1 Блокнот Jupyter .................................................................................................288
A.2 Условный блок ..................................................................................................289
A.3 Списки ................................................................................................................290
A.4 Циклы .................................................................................................................292
A.5 Кортежи ..............................................................................................................295
A.6 Словари ..............................................................................................................297
A.7 Комбинирование типов данных ..................................................................300
A.7.1 Список кортежей ..................................................................................300
A.7.2 Список словарей ...................................................................................301
A.7.3 Словарь словарей..................................................................................302
A.7.4 Словарь с кортежными ключами ......................................................302
A.7.5 Еще один словарь словарей ...............................................................303

ПриложениеВ.МоделиNetLogo ................................................................................305
B.1 Модель Page Rank ..............................................................................................306
B.2 Гигантская компонента..................................................................................307
B.3 Малые миры ......................................................................................................308
B.4 Преференциальное прикрепление .............................................................309
B.5 Вирус в сети .......................................................................................................310
B.6 Изменение языка .............................................................................................312

Справочныематериалы ...............................................................................................314

Предметныйуказатель .................................................................................................331

Предисловие

Сети присутствуют во всех аспектах нашей жизни: круг друзей, коммуникационные и транспортные сети, а также Веб как Всемирная паутина – все это примеры, которые мы воспринимаем внешне, тогда как 
нейроны в нашем мозге и белки в нашем теле образуют сети, которые определяют наш интеллект и выживание. Когда люди общаются 
в Facebook или Twitter, покупают что-то в Amazon, ищут в Google или 
покупают авиабилет, чтобы навестить семью, они используют сети, не 
осознавая того. Сегодня базовое понимание сетевых процессов требуется в различных сферах деятельности – от технологий до маркетинга, от менеджмента до дизайна, от биологии до искусства и гуманитарных наук. В этом учебнике проводится разведывательный анализ 
учения о сетях и то, как сети помогают нам понимать сложные шаблоны взаимоотношений, которые формируют наши жизни.

Эта книга тоже является сетью! На приведенном выше рисунке показаны взаимоотношения между главами, разделами и подразделами. 
Связи представляют и иерархическую структуру книги (как показано 
в Оглавлении), и перекрестные ссылки между главами, разделами,