Читать фрагмент

книга

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

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

Форматы: PDF

Издательство: ДМК Пресс

Год: 2020

Место издания: Москва

ISBN: 978-5-97060-799-2

Страниц: 260

Артикул: 95141

Возрастная маркировка: 16+

Электронная книга

998 ₽

Купить и скачать

Содержание

Содержание книги "Графовые алгоритмы : практическая реализация на платформах Apache Spark и Neo4j"

Предисловие

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

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

Что такое графы?

Что такое графовые алгоритмы и анализ графов?

Обработка графов, базы данных, запросы и алгоритмы

OLTP и OLAP

Почему мы должны изучать графовые алгоритмы?

Где и когда применяется анализ графов?

Заключение

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

Терминология

Типы и структуры графов

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

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

Связные и несвязные графы

Невзвешенные и взвешенные графы

Ненаправленные и ориентированные графы

Ациклические и циклические графы

Разреженные и плотные графы

Однокомпонентные, двудольные и k-дольные графы

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

Поиск пути

Определение центральности

Обнаружение сообщества

Заключение

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

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

Подходы к выбору платформы

Подходы к обработке данных

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

Выбор платформы

Apache Spark

Графовая платформа Neo4j

Заключение

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

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

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

Импорт данных в Neo4j

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

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

Поиск в глубину

Кратчайший путь

Когда следует использовать алгоритм кратчайшего пути?

Реализация алгоритма кратчайшего пути с Neo4j

Поиск кратчайшего взвешенного пути с Neo4j

Поиск кратчайшего взвешенного пути с Apache Spark

Вариант алгоритма кратчайшего пути: A*

Вариант алгоритма кратчайшего пути: k-кратчайший путь Йена

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

Подробный разбор алгоритма APSP

Когда следует использовать APSP?

Реализация APSP на платформе Apache Spark

Реализация APSP на платформе Neo4j

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

Когда следует использовать алгоритм SSSP?

Реализация алгоритма SSSP на платформе Apache Spark

Реализация алгоритма SSSP на платформе Neo4j

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

Когда следует использовать минимальное остовное дерево?

Реализация минимального остовного дерева на платформе Neo4j

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

Когда следует использовать алгоритм случайного блуждания?

Реализация алгоритма случайного блуждания на платформе Neo4j

Заключение

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

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

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

Импорт данных в Neo4j

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

Охват вершины

Когда следует использовать степенную центральность?

Реализация алгоритма степенной центральности с Apache Spark

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

Когда следует использовать центральность по близости?

Реализация алгоритма центральности по близости с Apache Spark

Реализация алгоритма центральности по близости с Neo4j

Вариант центральности по близости: Вассерман и Фауст

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

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

Когда следует использовать центральность по посредничеству?

Реализация центральности по посредничеству с Neo4j

Вариант центральности по посредничеству: алгоритм Брандеса

PageRank

Влияние

Формула алгоритма PageRank

Итерация, случайные пользователи и ранжирование

Когда следует использовать PageRank?

Реализация алгоритма PageRank с Apache Spark

Реализация алгоритма PageRank с Neo4j

Вариант алгоритма PageRank: персонализированный PageRank

Заключение

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

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

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

Импорт данных в Neo4j

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

Локальный коэффициент кластеризации

Глобальный коэффициент кластеризации

Когда следует использовать подсчет треугольников и коэффициент кластеризации?

Реализация подсчета треугольников с Apache Spark

Реализация подсчета треугольников с Neo4j

Локальный коэффициент кластеризации с Neo4j

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

Когда следует использовать сильно связанные компоненты?

Реализация поиска сильно связанных компонентов с Apache Spark

Реализация поиска сильно связанных компонентов с Neo4j

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

Когда следует использовать связанные компоненты?

Реализация алгоритма связанных компонентов с Apache Spark

Реализация алгоритма связанных компонентов с Neo4j

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

Обучение с частичным привлечением учителя и начальные метки

Когда следует использовать распространение меток?

Реализация алгоритма распространения меток с Apache Spark

Реализация алгоритма распространения меток с Neo4j

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

Когда следует использовать Лувенский алгоритм?

Реализация Лувенского алгоритма с Neo4j

Проверка достоверности сообществ

Заключение

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

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

Социальная сеть Yelp

Импорт данных

Графовая модель

Краткий обзор данных Yelp

Приложение для планирования поездки

Туристический бизнес-консалтинг

Поиск похожих категорий

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

Предварительный анализ