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

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

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

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 или 
покупают авиабилет, чтобы навестить семью, они используют сети, не 
осознавая того. Сегодня базовое понимание сетевых процессов требуется 
в различных сферах деятельности – от технологий до маркетинга, 
от менеджмента до дизайна, от биологии до искусства и гуманитарных 
наук. В этом учебнике проводится разведывательный анализ 
учения о сетях и то, как сети помогают нам понимать сложные шаблоны 
взаимоотношений, которые формируют наши жизни.

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

Предисловие

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

Зачемнужен«Вводныйкурс»понаукео сетях?

Это не первая книга о науке о сетях – на самом деле есть несколько отличных 
книг на выбор, и мы перечислим некоторые из них в главе 1. 
Мы преподаем эти темы уже в течение нескольких лет в Университете 
Индианы для широкой аудитории студентов старших курсов по 
информатике, теории вычислительных машин, науке о данных, теории 
информации, бизнесу, естественным и социальным наукам. Этот 
опыт научил нас тому, что студенты стремятся «пачкать свои руки» 
выполнением черновой работы и писать исходный код, чтобы понимать 
и использовать сети в интересующих их областях применения, 
даже если они только учатся программировать и не имеют математического 
и компьютерного образования за пределами средней школы 
и курсов начального уровня колледжей. Поэтому мы разработали широкий 
круг учебно-практических занятий и задач, как теоретических, 
так и вычислительных, предоставив студентам обилие практических 
занятий по науке о сетях. Используя такой подход, книга знакомит 
с сетями широкую аудиторию студентов, не имеющих никаких технических 
предпосылок, кроме какого-то вводного программирования 
и готовности учиться на деле. Это делает наш учебник пригодным для 
«вводного курса» науки о сетях.

Синопсис

После проведения обзора сетей, существующих во многих областях 
человеческих знаний и деятельности, мы поговорим о социальных 
сетях, которые знакомы студентам больше всего. Это позволяет ввести 
такие понятия, как маломировое свойство (короткие пути) и кластеризация (
треугольники и транзитивность). Указанные темы объясняются 
с использованием увлекательных учебных занятий, таких как 
игра «Шесть степеней Кевина Бейкона». Затем мы погрузимся в роль 
хабов, используя Парадокс дружбы, и обсудим тему устойчивости сетей. 
Далее мы вводим соответственно направленные и взвешенные 
сети. Всемирная паутина, «Википедия», цитирование, трафик и Twit-
ter используются для иллюстрации роли направления и веса. Последние 
три главы охватывают более сложные темы, а именно модели возникновения 
сетей, методы обнаружения сообществ и динамические 
процессы, происходящие в сетях.
В каждой главе рассматриваются базовые концепции, необходимые 
для понимания фундаментального аспекта сетей; избегаются 

Предисловие

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

Целеваяаудитория

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

Педагогика

Настоящий курс не требует никакого технического образования в области 
математики или программирования, что делает эту книгу пригодной 
для вводных курсов любого уровня, включая курсы сетевой 
грамотности и грамотности в программировании. Подобного рода 
курсы могут пропускать математические вставки. Отрабатывая учебно-
практические занятия по программированию в коллаборативной 
вычислительной лаборатории и назначая упражнения по программированию, 
преподаватели предоставят студентам возможность 
приобрести технические навыки, достаточные для выполнения задач 

1 См. github.com/CambridgeUniversityPress/FirstCourseNetworkScience.

Предисловие

анализа данных, связанных с сетями. Таков наш подход в Университете 
Индианы, где мы преподаем материал данной книги в течение 
двух курсов: первый вводный курс, предназначенный для студентов-
второкурсников / младших курсов, которые прошли или проходят 
курсы конкурентного программирования на Python; и второй курс, 
предназначенный для студентов младших/старших курсов. Первый 
курс примерно охватывает материал глав с 0 по 4. Второй курс сосредоточен 
на главах 5–7 после расширенного обзора и нескольких 
более продвинутых учебно-практических занятий по предыдущему 
материалу.
Обширные учебно-практические занятия по программированию 
и упражнения позволят преподавателям легко руководить учебным 
процессом и проводить практические мероприятия, а также позволят 
студентам укрепить и проверить свое понимание сетевых концепций. 
Мероприятия включают учебно-практические занятия по Net-
workX, широко распространенной библиотеке для сетевой аналитики; 
и по всем затронутым в книге темам, от базовых упражнений до передовых 
методов. Например, на одном учебно-практическом занятии 
студенты знакомятся с шагами извлечения данных социальных сетей 
из Всемирной паутины. Используя интерфейс прикладного программирования (
API) Twitter, студенты смогут анализировать популярные 
темы, выявлять влиятельных пользователей и реконструировать сети 
диффузии информации, показывающие процесс онлайнового распространения 
хештегов. Студенты, которые проходят учебно-практические 
занятия и выполняют упражнения по программированию, 
наберутся опыта в строительстве, импортировании/экспортировании, 
анализировании, манипулировании и визуализировании сетей 
любого типа.
Учебно-практические занятия основаны на языке Python, т. е. самом 
популярном языке для написания скриптов/программ. Учебное 
руководство, в котором рассматриваются главные концепции программирования 
на Python, включен в приложение A книги. Все учебно-
практические занятия доступны онлайн в виде блокнотов Jupyter/
IPython. Со временем библиотека NetworkX (и даже язык Python), возможно, 
эволюционирует, и, возможно, потребуется обновить часть 
исходного кода книги. Мы будем отмечать такие обновления в репозитории 
книги на GitHub.
Разумеется, для программирования сетей существуют и другие библиотеки, 
например igraph, SNAP и graph-tool. Наш выбор библиотеки 
NetworkX основан на том факте, что она написана на чистом Python, 
что облегчает отладку для студентов, знакомых с Python. Многие альтернативы 
имеют интерфейсы Python, но написаны на языке C, что 
делает их эффективнее, но и сложнее в отладке.
Наконец, в некоторых главах используются интерактивные модели 
для демонстрации сетевых явлений, таких как гигантские компоненты, 
малые миры, алгоритм Page Rank, предпочтительное прикрепле-

Предисловие

ние и эпидемии. Эти модели работают в NetLogo, популярной симу-
ляционной платформе. Учебно-практический материал по NetLogo 
и несколько наиболее актуальных моделей представлены в приложении 
B книги.

Обобложке

Сеть на обложке, сгенерированная Онуром Варолом (Onur Varol) 
(Феррара и соавт., 2016), изображает диффузию хештега #SB277 в Twit-
ter. Этот хештег относится к калифорнийскому закону 2015 года об 
обязательствах в отношении вакцинации и освобождении от нее, 
и указанная сеть изображает обсуждение, которое проходило онлайн 
среди сторонников и противников указанного законопроекта. Узлы 
изображают пользователей Twitter, а связи показывают информацию, 
распространяемую среди пользователей через ретвиты. Размер узла 
отражает влияние учетной записи (сколько раз пользователь ретвит-
нул), а цвета узлов иллюстрируют баллы ботов: красные узлы, скорее 
всего, являются учетными записями ботов, синие узлы, скорее всего, 
являются людьми.

Отзывыи пожелания

Мы всегда рады отзывам наших читателей. Расскажите нам, что вы 
ду маете об этой книге, – что понравилось или, может быть, не понравилось. 
Отзывы важны для нас, чтобы выпускать книги, которые 
будут для вас максимально полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, 
зайдя  на страницу книги и оставив комментарий в разделе «Отзывы 
и рецензии». Также можно послать письмо главному редактору 
по адресу dmkpress@gmail.com; при этом укажите название книги 
в теме письма. 
Если вы являетесь экспертом в какой-либо области и заинтересованы 
в написании новой книги, заполните форму на нашем сайте по 
адресу http://dmkpress.com/authors/publish_book/ или напишите в издательство 
по адресу dmkpress@gmail.com.

Скачиваниеисходногокодапримеров

Скачать файлы с дополнительной информацией для книг издательства «
ДМК Пресс» можно на сайте www.dmkpress.com на странице 
с описанием соответствующей книги.