Графовые алгоритмы
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Перевод:
Яценков Валерий Станиславович
Год издания: 2020
Кол-во страниц: 258
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Специалитет
ISBN: 978-5-97060-799-2
Артикул: 739784.01.99
Доступ онлайн
В корзину
Каждую секунду во всем мире собирается и динамически обновляется огромный объем информации. Графовые алгоритмы, которые основаны на математике, специально разработанной для изучения взаимосвязей между данными, помогают разобраться в этих гигантских объемах. И, что особенно важно в наши дни, они улучшают контекстную информацию для искусственного интеллекта. Эта книга представляет собой практическое руководство по началу работы с графовыми алгоритмами. В начале описания каждой категории алгоритмов приводится таблица, которая поможет быстро выбрать нужный алгоритм и ознакомиться с примерами его использования. Издание предназначено для разработчиков и специалистов по анализу данных. Для изучения материала книги желателен опыт использования платформ Apache Spark™ или Neo4j, но она пригодится и для изучения более общих понятий теории графов, независимо от выбора графовых технологий.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.04: Программная инженерия
- ВО - Специалитет
- 09.05.01: Применение и эксплуатация автоматизированных систем специального назначения
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Марк Нидхем Эми Ходлер Графовые алгоритмы
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. Russianlanguage edition copyright © 2019 by DMK Press. All rights reserved. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. ISBN 9781492047681 (англ.) © 2019 Amy Hodler and Mark Needham. ISBN 9785970607992 (рус.) © Оформление, перевод на русский язык, издание, ДМК Пресс, 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 Маркетинговая атрибуция – это анализ отдачи от точек взаимодействия с клиентом. Любимая поговорка маркетологов гласит: «Половина денег, которые я трачу на рекламу, выбрасывается впустую. Беда в том, что я не знаю, какая половина». Атрибуция призвана дать ответ на этот вопрос. – Прим. перев.
Доступ онлайн
В корзину