Фразу «Маршрут построен» слышат каждый день миллионы автомобилистов: программы поиска оптимальных маршрутов в городе в объезд пробок и дорожных работ стали органической частью жизни, позволяя экономить время и деньги. Однако теория графов применяется сегодня для решения многих прикладных задач в различных отраслях: для оптимизации вирусных маркетинговых кампаний, обнаружения мошенничества в финансовой сфере путем исследования схем взаимодействия контрагентов, анализа социальных сетей и т. п. При проведении маркетинговых кампаний наибольший упор делается на производство контента, который пользователи будут с большой охотой передавать своим друзьям и знакомым, и здесь важно определить лидеров мнений — людей, имеющих много друзей в социальной сети, которую можно представить в виде графа: вершины — пользователи, ребра — связи между ними. При поиске оптимальных маршрутов движения транспорта вершина графа — это перекресток, а ребро — дорога между перекрестками. При исследовании схем взаимодействия контрагентов вершинами графа будут участники финансовых операций: физические и юридические лица, государственные организации, а ребрами — их финансовые взаимоотношения.

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

Типичный представитель графовых СУБД — система neo4j, использующая специализированный способ моделирования данных. Модель neo4j предусматривает два типа сущностей: вершины, которые могут обладать набором свойств, и ребра, связывающие эти вершины, при этом ребра также могут обладать набором свойств и могут относиться к разным типам. Таким образом, набор данных в neo4j может принимать следующий вид: например, вершина «Юлий Цезарь» связана ребром «является предшественником» с вершиной «Октавиан Август», при этом обе эти вершины связаны ребром типа «занимал должность» с вершиной «Император Рима». Не существует жестко заданной модели данных, и при необходимости добавить связь нового типа или изменить набор свойств какой-либо вершины не составит труда. В neo4j имеется интерфейс REST API, а также ряд интерфейсов для работы с данными и API для языков программирования Java, Python и др. В СУБД имеется специализированный язык запросов Cypher, предназначенный для обращения к данным, представленным в виде графа, причем в neo4j изначально включены функции для решения наиболее типичных задач, таких как поиск кратчайшего расстояния.

neo4J — не единственная, хотя и наиболее распространенная графовая система. Например, Orient DB представляет собой комбинированную графово-документную базу, позволяющую хранить в узлах не просто набор свойств, а целые документы с динамической схемой. Важное отличие еще одной графовой СУБД, Titan, состоит в возможности работы в распределенной среде.

Распределенные фреймворки для работы с графами обычно являются элементами экосистемы Hadoop. Наиболее популярен сегодня GraphX, использующий вычислительный механизм Spark [1], за счет чего достигаются высокие показатели производительности. В отличие от графовых СУБД, GraphX не предназначен для хранения данных в виде графа, и нельзя, например, вставить вершину или ребро в уже имеющуюся структуру описания графа. Главное назначение этого инструмента — аналитика. В GraphX имеется API для языка Scala, в котором предусмотрены ряд стандартных функций для решения типичных задач на графах, а также несколько механизмов для обхода графа вручную, что, хотя и достаточно трудоемко, но открывает широкий спектр возможностей для реализации специализированных...

Это не вся статья. Полная версия доступна только подписчикам журнала. Пожалуйста, авторизуйтесь либо оформите подписку.
Купить номер с этой статьей в PDF