Графовые алгоритмы

Марк Нидхем
Эми Ходлер

Графовые алгоритмы

Graph Algorithms

Practical Examples  
in Apache Spark and Neo4j

Mark Needham and Amy E. Hodler

Beijing • Cambridge • Farnham • Köln • Sebastopol • Tokyo

Москва, 2020

Марк Нидхем
Эми Ходлер

Графовые алгоритмы

Практическая реализация  
на платформах Apache Spark и Neo4j

Перевод с английского Яценкова В. С.

УДК   004.021
ББК    32.973.1
Н60

Н60  Марк Нидхем, Эми Ходлер
Графовые алгоритмы. Практическая реализация на платформах Apache 
Spark и Neo4j. / пер. с англ. В. С. Яценкова – М.: ДМК Пресс, 2020. – 
258 с.: ил.

            ISBN 978-5-97060-799-2

Каждую секунду во всем мире собирается и динамически обновляется огромный объем информации. Графовые алгоритмы, которые основаны на математике, специально разработанной для изучения взаимосвязей между данными, 
помогают разобраться в этих гигантских объемах. И, что особенно важно в наши 
дни, они улучшают контекстную информацию для искусственного интеллекта.
Эта книга представляет собой практическое руководство по началу работы 
с графовыми алгоритмами. В начале описания каждой категории алгоритмов 
приводится таблица, которая поможет быстро выбрать нужный алгоритм и 
ознакомиться с примерами его использования.
Издание предназначено для разработчиков и специалистов по анализу данных. Для изучения материала книги желателен опыт использования платформ 
Apache Spark™ или Neo4j, но она пригодится и для изучения более общих понятий теории графов, независимо от выбора графовых технологий.

 
 
 
 
 
 
 
 
           УДК  004.021
ББК  32.973.1

Original English language edition published by O’Reilly Media, Inc. Copyright © 2019 
Mark Needham and Amy E. Hodler. All rights reserved. Russian­language edition copyright 
© 2019 by DMK Press. All rights reserved.

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

ISBN 978­1­49204­768­1 (англ.)                © 2019 Amy Hodler and Mark Needham. 
ISBN 978­5­97060­799­2 (рус.)                  © Оформление, перевод на русский язык, издание, 
 
             ДМК Пресс, 2020

Оглавление

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

Вступительное слово рецензента ................................................................. 14

Глава 1. Введение ............................................................................................. 17

Что такое графы? ....................................................................................... 18
Что такое графовые алгоритмы и анализ графов? ................................. 19
Обработка графов, базы данных, запросы и алгоритмы........................ 22

OLTP и OLAP ....................................................................................................23

Почему мы должны изучать графовые алгоритмы? .............................. 25
Где и когда применяется анализ графов? ............................................... 29
Заключение ............................................................................................... 30

Глава 2. Теория и концепции графов ............................................................ 31

Терминология ............................................................................................ 31
Типы и структуры графов ......................................................................... 32

Случайные, локализованные и безмасштабные сети ..................................32

Разновидности графов ............................................................................. 34

Связные и несвязные графы ..........................................................................35
Невзвешенные и взвешенные графы ............................................................35
Ненаправленные и ориентированные графы ..............................................36
Ациклические и циклические графы ............................................................38
Разреженные и плотные графы .....................................................................39
Однокомпонентные, двудольные и k-дольные графы .................................40

Типы графовых алгоритмов ..................................................................... 42

Поиск пути ......................................................................................................42
Определение центральности .........................................................................43
Обнаружение сообщества ..............................................................................43

Заключение ............................................................................................... 44

Глава 3. Графовые платформы и обработка ................................................ 45

Графовые платформы и особенности обработки ................................... 45

Подходы к выбору платформы ......................................................................45
Подходы к обработке данных ........................................................................46

Объединяющие платформы ..................................................................... 47

Выбор платформы ..........................................................................................48
Apache Spark ....................................................................................................49
Графовая платформа Neo4j ............................................................................51

Заключение ............................................................................................... 54

 Оглавление

Глава 4. Алгоритмы поиска по графу и поиска пути .................................. 55

Пример данных: транспортный граф ...................................................... 58

Импорт данных в Apache Spark .....................................................................59
Импорт данных в Neo4j ..................................................................................60

Поиск в ширину ........................................................................................ 61

Поиск в ширину с помощью Apache Spark ....................................................61

Поиск в глубину ......................................................................................... 63
Кратчайший путь ...................................................................................... 64

Когда следует использовать алгоритм кратчайшего пути? .........................66
Реализация алгоритма кратчайшего пути с Neo4j .......................................67
Поиск кратчайшего взвешенного пути с Neo4j ............................................69
Поиск кратчайшего взвешенного пути с Apache Spark................................70
Вариант алгоритма кратчайшего пути: A* ...................................................73
Вариант алгоритма кратчайшего пути: k-кратчайший путь Йена .............75

Алгоритм кратчайшего пути между всеми парами вершин.................. 76

Подробный разбор алгоритма APSP .............................................................77
Когда следует использовать APSP? ................................................................79
Реализация APSP на платформе Apache Spark .............................................79
Реализация APSP на платформе Neo4j ..........................................................80

Кратчайший путь из одного источника .................................................. 82

Когда следует использовать алгоритм SSSP? ................................................83
Реализация алгоритма SSSP на платформе Apache Spark ...........................83
Реализация алгоритма SSSP на платформе Neo4j ........................................86

Минимальное остовное дерево................................................................ 87

Когда следует использовать минимальное остовное дерево?.....................88
Реализация минимального остовного дерева на платформе Neo4j ...........89

Алгоритм случайного блуждания ............................................................ 91

Когда следует использовать алгоритм случайного блуждания? .................91
Реализация алгоритма случайного блуждания на платформе Neo4j .........92

Заключение ............................................................................................... 93

Глава 5. Алгоритмы вычисления центральности ........................................ 94

Пример графовых данных – социальный граф ....................................... 96

Импорт данных в Apache Spark .....................................................................98
Импорт данных в Neo4j ..................................................................................98

Степенная центральность ........................................................................ 98

Охват вершины ...............................................................................................99
Когда следует использовать степенную центральность? ..........................100
Реализация алгоритма степенной центральности с Apache Spark ...........100

Центральность по близости ....................................................................102

Когда следует использовать центральность по близости? ........................103
Реализация алгоритма центральности по близости с Apache Spark .........103
Реализация алгоритма центральности по близости с Neo4j .....................106

Оглавление  7

Вариант центральности по близости: Вассерман и Фауст .........................107
Вариант центральности по близости: гармоническая центральность .....109

Центральность по посредничеству .........................................................110

Когда следует использовать центральность по посредничеству? .............113
Реализация центральности по посредничеству с Neo4j ............................113
Вариант центральности по посредничеству: алгоритм Брандеса ............116

PageRank ...................................................................................................118

Влияние .........................................................................................................118
Формула алгоритма PageRank .....................................................................119
Итерация, случайные пользователи и ранжирование ...............................119
Когда следует использовать PageRank? .......................................................122
Реализация алгоритма PageRank с Apache Spark ........................................122
Реализация алгоритма PageRank с Neo4j ....................................................125
Вариант алгоритма PageRank: персонализированный PageRank .............126

Заключение ..............................................................................................127

Глава 6. Алгоритмы выделения сообществ ............................................... 128

Пример данных: граф зависимостей библиотек ...................................131

Импорт данных в Apache Spark ...................................................................132
Импорт данных в Neo4j ................................................................................133

Подсчет треугольников и коэффициент кластеризации .......................134

Локальный коэффициент кластеризации ..................................................134
Глобальный коэффициент кластеризации .................................................135
Когда следует использовать подсчет треугольников и коэффициент 
кластеризации? ....................................................................................136

Реализация подсчета треугольников с Apache Spark .................................136
Реализация подсчета треугольников с Neo4j..............................................137
Локальный коэффициент кластеризации с Neo4j ......................................137

Сильно связанные компоненты .............................................................139

Когда следует использовать сильно связанные компоненты? ..................140
Реализация поиска сильно связанных компонентов с Apache Spark .......141
Реализация поиска сильно связанных компонентов с Neo4j....................142

Связанные компоненты ..........................................................................144

Когда следует использовать связанные компоненты? ..............................144
Реализация алгоритма связанных компонентов с Apache Spark ..............145
Реализация алгоритма связанных компонентов с Neo4j ..........................145

Алгоритм распространения меток .........................................................147

Обучение с частичным привлечением учителя и начальные метки ........148
Когда следует использовать распространение меток? ..............................149
Реализация алгоритма распространения меток с Apache Spark ...............150
Реализация алгоритма распространения меток с Neo4j ...........................151

Лувенский модульный алгоритм ............................................................152

Когда следует использовать Лувенский алгоритм? ....................................157
Реализация Лувенского алгоритма с Neo4j ................................................158

 Оглавление

Проверка достоверности сообществ .......................................................162
Заключение ..............................................................................................162

Глава 7. Графовые алгоритмы на практике ............................................... 164

Анализ данных Yelp на платформе Neo4j ..............................................165

Социальная сеть Yelp ....................................................................................165
Импорт данных .............................................................................................166
Графовая модель ...........................................................................................166
Краткий обзор данных Yelp .........................................................................167
Приложение для планирования поездки ...................................................171
Туристический бизнес-консалтинг .............................................................177
Поиск похожих категорий ...........................................................................182

Анализ данных о рейсах авиакомпании с помощью Apache Spark ......187

Предварительный анализ ............................................................................188
Популярные аэропорты ...............................................................................189
Задержки вылетов из аэропорта Чикаго .....................................................190
Плохой день в Сан-Франциско ....................................................................193
Взаимосвязи аэропортов через авиакомпании .........................................194

Заключение ..............................................................................................201

Глава 8. Графовые алгоритмы и машинное обучение ............................. 202

Машинное обучение и важность контекста ...........................................202

Графы, контекст и точность .........................................................................203

Извлечение и отбор связанных признаков ............................................205

Графовые признаки ......................................................................................207
Признаки и графовые алгоритмы ...............................................................207

Графы и машинное обучение на практике: прогнозирование связей .. 209

Инструменты и данные ................................................................................210
Импорт данных в Neo4j ................................................................................211
Граф соавторства ..........................................................................................213
Создание сбалансированных наборов данных для обучения 
и тестирования .....................................................................................214

Как мы предсказываем недостающие связи ..............................................220
Разработка полного цикла машинного обучения ......................................221
Прогнозирование связей: основные признаки графа ...............................222
Прогнозирование связей: треугольники и коэффициент  
кластеризации ......................................................................................235

Прогнозирование связей: выделение сообществ ......................................239

Заключение ..............................................................................................245
Итог книги ................................................................................................246

Приложение А. Дополнительная информация и ресурсы ...................... 247

Дополнительные алгоритмы ...................................................................247
Массовый импорт данных Neo4j и Yelp ..................................................248

Оглавление  9

APOC и другие инструменты Neo4j ........................................................249
Поиск наборов данных ............................................................................249
Помощь в освоении платформ Apache Spark и Neo4j ............................250
Дополнительные курсы ...........................................................................250

Об авторах ...................................................................................................... 252

Об изображении на обложке ....................................................................... 253

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

Предисловие

Миром правят связи – повсеместно, от финансовых и коммуникационных 
систем до социальных и биологических процессов. Выявление скрытого 
смысла этих связей приводит к прорывным решениям различных задач, 
таких как выявление мошеннических звонков, оптимизация связей в рабочей группе или прогнозирование каскадных сетевых сбоев.
Поскольку связность мира продолжает нарастать, неудивительно, что 
возрастает интерес к графовым алгоритмам, потому что они основаны на 
математике, специально разработанной для изучения взаимосвязей между данными. Анализ графов может раскрыть работу сложных систем и сетей в огромных масштабах – для любой организации.
Мы искренне увлечены полезностью и важностью анализа графов и с 
удовольствием расшифровываем тонкости внутренней работы сложных 
сценариев. До недавнего времени применение анализа графов требовало 
значительного опыта и упорства, потому что инструменты и средства интеграции были трудными в освоении, и лишь немногие знали, как применять графовые алгоритмы к своим задачам. Наша цель – помочь вам преодолеть трудности. Мы написали эту книгу, чтобы исследователи данных 
начали в полной мере использовать анализ графов, а значит, могли делать 
новые открытия и быстрее разрабатывать интеллектуальные решения.

О чем эта книга

Эта книга представляет собой практическое руководство по началу работы 
с графовыми алгоритмами для разработчиков и специалистов по анализу 
данных, которые имеют опыт использования Apache Spark™ или Neo4j. 
Хотя в наших примерах алгоритмов используются платформы Spark и 
Neo4j, эта книга также пригодится для изучения более общих понятий теории графов, независимо от вашего выбора графовых технологий.
Первые две главы содержат введение в теорию, анализ графов и графовые алгоритмы. В третьей главе кратко рассмотрены платформы, используемые в этой книге, прежде чем мы углубимся в следующие три главы, 
посвященные классическим графовым алгоритмам – нахождению пути, 
вычислению центральности и выделению сообществ. Мы завершим книгу 
двумя главами, показывающими, как графовые алгоритмы используются 
в рабочих процессах – один для общего анализа и другой для машинного 
обучения.
В начале описания каждой категории алгоритмов есть справочная таблица, которая поможет вам быстро выбрать нужный алгоритм. Для каждого алгоритма вы найдете:

Предисловие  11

• объяснение того, что делает алгоритм;
• примеры использования алгоритма и ссылки, где вы можете узнать 
больше;
• примеры кода, демонстрирующие способы реализации алгоритма в 
Spark и Neo4j.

Условные обозначения, принятые в книге

В книге имеются следующие условные обозначения:

Курсив
  
Используется для смыслового выделения важных положений, новых 
терминов, URL-адресов и адресов электронной почты в интернете, имен 
команд и утилит, а также имен и расширений файлов и каталогов.

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

Моноширинный полужирный шрифт
  
Используется для обозначения команд или фрагментов текста, которые пользователь должен ввести дословно, без изменений.

Моноширинный курсив
  
Используется для обозначения в исходном коде или в командах шаблонных меток-заполнителей, которые должны быть заменены соответствующими контексту реальными значениями.

Такая пиктограмма обозначает совет или рекомендацию.

Обозначает указание или примечание общего характера.

Эта пиктограмма обозначает предупреждение или особое 
внимание к потенциально опасным объектам.

 Предисловие

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

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

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

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

Список опечаток

Хотя мы приняли все возможные меры, для того чтобы удостовериться 
в качестве наших текстов, ошибки все равно случаются. Если вы найдете 
ошибку в одной из наших книг – возможно, ошибку в тексте или в коде, – 
мы будем очень благодарны, если вы сообщите нам о ней. Сделав это, вы 
избавите других читателей от расстройств и поможете нам улучшить последующие версии этой книги.
Если вы найдете какие-либо ошибки в коде, пожалуйста, сообщите о них 
главному редактору по адресу dmkpress@gmail.com, и мы исправим это в следующих тиражах.

Нарушение авторских прав

Пиратство в интернете по-прежнему остается насущной проблемой. Издательства «ДМК Пресс» и O’Reilly очень серьезно относятся к вопросам 
защиты авторских прав и лицензирования. Если вы столкнетесь в интернете с незаконно выполненной копией любой нашей книги, пожалуйста, 
сообщите нам адрес копии или веб-сайта, чтобы мы могли применить 
санкции.
Пожалуйста, свяжитесь с нами по адресу электронной почты dmkpress@
gmail.com со ссылкой на подозрительные материалы.

Предисловие  13

Мы высоко ценим любую помощь по защите наших авторов, помогающую нам предоставлять вам качественные материалы.

Благодарности

Нам очень понравилось работать над этой книгой благодаря помощи наших друзей. Мы особенно благодарны Майклу Хангеру (Michael Hunger) 
за его руководство, Джиму Уэбберу (Jim Webber) за его бесценные правки 
и Томазу Братаничу (Tomaz Bratanic) за его увлекательные исследования. 
Наконец, мы искренне благодарим каталог Yelp, который позволяет нам 
использовать его богатый набор данных в качестве практических примеров.

Вступительное слово 
рецензента

Как вы думаете, что общего имеют следующие вещи: анализ маркетинговых взаимосвязей, противодействие отмыванию денег, моделирование 
поездок клиентов, анализ инцидентов безопасности, анализ литературных 
источников, обнаружение мошеннических сетей, анализ поисковых узлов 
в интернете, создание картографических приложений, анализ распространения эпидемий и изучение пьес Уильяма Шекспира? Как вы уже догадались, общим для всех них является использование графов, доказывающих, что Шекспир был прав, когда заявил: «Весь мир – это граф!»
Ну хорошо, великий бард с берегов Эйвона на самом деле не говорил про 
граф, он сказал «театр». Тем не менее обратите внимание, что приведенные выше примеры включают в себя сущности и отношения между ними, 
как прямые, так и косвенные. Сущности – вершины графа – могут быть 
людьми, событиями, объектами, концепциями или местами. Отношения 
между вершинами – это ребра графа. Но разве сама суть шекспировской 
пьесы не заключается в изображении героев (вершин) и их отношений 
(ребер)? Следовательно, Шекспир в своей знаменитой фразе имел полное 
право сказать про граф.
Что делает графовые алгоритмы и графовые базы данных такими интересными и мощными, так это не простые отношения между двумя 
сущнос тями, где A связан с B. В конце концов, стандартная реляционная 
модель баз данных использует эти типы отношений уже несколько десятилетий. Что на самом деле делает графы настолько удивительными – это 
направленные и транзитивные отношения. В направленных отношениях 
A может вызвать B, но не наоборот. В транзитивных отношениях A может 
быть непосредст венно связан с B, а B может быть напрямую связан с C, в 
то время как A не имеет прямого отношения к C. Следовательно, A транзитивно связан с C.
Благодаря транзитивным отношениям – особенно когда они многочисленны и разнообразны, с различными паттернами отношений и степеней 
разделения между объектами – графовая модель раскрывает связи между 
объектами, которые в противном случае могут показаться не связанными 
или независимыми в обычной реляционной базе данных. Следовательно, 
во многих задачах сетевого анализа можно эффективно применять графовую модель.

Вступительное слово рецензента  15

Рассмотрим пример маркетинговой атрибуции1 (marketing attribution): 
человек А видит маркетинговую кампанию; человек А пишет комментарий в социальных сетях; человек B связан с человеком A и видит комментарий; и впоследствии человек B покупает продукт. С точки зрения 
менеджера маркетинговой кампании, стандартная реляционная модель 
не может определить атрибуцию, поскольку персонаж B не видел кампанию, а персонаж A не купил продукт. Кампания выглядит как провал, 
но ее фактический успех (и положительная рентабельность инвестиций) 
обнаруживается алгоритмом анализа графов через транзитивные отношения между маркетинговой кампанией, посредником и конечной покупкой.
Далее рассмотрим пример противодействия отмыванию денег: лица A 
и C подозреваются в обороте денег, полученных незаконным путем. Любая 
прямая сделка между ними – например, транзакция через расчетно-кассовый центр – будет без труда зафиксирована и подвергнута строгому контролю. Однако, если A и C никогда не совершают взаимные сделки, а вместо этого проводят финансовые операции через надежные, уважаемые и 
незапятнанные финансовые органы B, что может провалить сделку? Алгоритм анализа графов! Графовый движок обнаружит транзитивные отношения между A и C через посредника B.
Отвечая на поисковый запрос, основные поисковые системы интернета используют алгоритмы на основе графов, чтобы найти самый авторитетный сайт во всем интернете для любого заданного набора поисковых 
слов. В этом случае принципиально важна направленность связей, поскольку авторитетным сайтом в сети является тот, на который ссылается 
большинс тво других сайтов.
Сегодня существует особая отрасль анализа данных – литературный поиск (literature-based discovery, LBD), технология на основе графов, позволяющая искать открытия в базе знаний тысяч (или даже миллионов) статей 
исследовательских журналов. Скрытые знания обнаруживаются только через связи между опубликованными результатами исследований, которые 
могут иметь много этапов переходных отношений. LBD активно применяется для поиска методов лечения рака, где обширная база семантических 
медицинских знаний о симптомах, диагнозах, методах лечения, взаимодействиях лекарств, генетических маркерах, краткосрочных результатах 
и долгосрочных последствиях может таить в себе ранее неизвестные или 
потенциально полезные методы лечения для самых безнадежных случаев. 
Это невероятно – знание уже может лежать в сети, и нам остается лишь 
соединить точки, чтобы найти его.

1 
Маркетинговая атрибуция – это анализ отдачи от точек взаимодействия с клиентом. Любимая поговорка маркетологов гласит: «Половина денег, которые я трачу на рекламу, выбрасывается впустую. Беда в том, что я не знаю, какая половина». Атрибуция призвана дать ответ на этот вопрос. – 
Прим. перев.