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

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

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

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

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

Один из первых, но до сих пор достаточно широко распространенный инструмент этой группы — Giraph, главное отличие которого от GraphX состоит в применении механизма MapReduce. Благодаря тому, что в MapReduce на каждом этапе вычислений на диске сохраняются промежуточные результаты (в отличие от Spark, который для обеспечения высокой производительности работает в основном в памяти), достигается высокая надежность и устойчивость к сбоям.

В отдельную группу инструментов, позволяющих работать с графами, можно выделить универсальные исследовательские средства, широко применяемые в корпоративной среде и поставляемые такими компаниями, как IBM, SAP, SAS и Teradata. В этом случае в одном инструменте обычно собраны возможности для выполнения различной аналитики: статистика, временные ряды, теория графов и т. д. При этом с точки зрения используемых подходов и вычислительных механизмов инструменты данной группы могут сильно отличаться друг от друга. В этих инструментах могут применяться различные языки программирования и API, и хотя все эти средства создаются для работы в корпоративной среде и потому предъявляют невысокие требования к подготовке пользователя, возможна ситуация, когда пользователь, привыкший в своей профессиональной деятельности иметь дело только с SQL, окажется не готов к освоению новых средств, реализованных в конкретной системе. Учитывая то, что данные инструменты часто используют принципиально отличающиеся друг от друга вычислительные модели, они могут быть ориентированы только на задачи конкретных типов: например, у какого-то из них самая сильная сторона — статистика, а графовый анализ — побочное свойство. Один из инструментов этой группы — система Teradata Aster [2], предлагающая для решения задач на графах отдельный механизм SQL-GR, позволяющий распараллелить выполнение операций на масштабируемом пространстве данных. В системе имеются функции для решения стандартных задач на графах: нахождение кратчайших путей, определение различных мер центральности, нахождение замкнутых циклов и др. Модель данных, описывающая граф в Aster, представляет собой две таблицы реляционной СУБД: таблицу вершин и таблицу ребер. Пользователям, не знакомым с языками программирования, предлагается интерфейс на базе SQL, позволяющий анализировать данные.

Особенности применения инструментов каждого класса хорошо видны на примере задачи поиска кратчайшего пути.

В СУБД neo4j имеется готовая функция для поиска кратчайшего пути, при этом предоставляется возможность выбора алгоритма: алгоритм Дейкстры, алгоритм А* (A-star) и др. Данная СУБД показывает высокую производительность при решении этой задачи, однако нет стандартного механизма доступа к данным через драйвер JDBC/ODBC. Кроме того, невысока производительность выполнения операции вставки записей, что приводит к необходимости использования специального загрузчика при организации ETL-процессов, любые неточности в настройке которого приведут к тому, что перемещение в базу даже не очень большого графа может занимать весьма продолжительное время. В качестве еще одной «ложки дегтя» следует упомянуть тот факт, что данный инструмент написан на Java и при решении требовательных к памяти задач разработчикам приходится в полной мере ощутить неэффективность модели управления памятью виртуальной машины Java.

При решении задачи поиска кратчайшего пути с помощью GraphX разработчикам придется вручную реализовывать соответствующий конкретный алгоритм, используя API обхода графа. Однако в качестве вознаграждения за неудобство имеется возможность выполнения кода в действительно распределенной среде с почти горизонтальным масштабированием. Другой положительной стороной GraphX является унаследованная от Spark «всеядность» источников данных.

При решении задачи при помощи Teradata Aster разработчикам доступен ряд готовых функций, позволяющих находить кратчайшие пути, указав один SQL-вызов. Вычислительный механизм Aster реализован на языке Cи, что обеспечивает более эффективную работу с памятью, чем позволяют инструменты, написанные на Java. Однако Aster — коммерческий продукт, в отличие от большинства инструментов стека Hadoop и многих графовых СУБД, и это может стать препятствием для небольших компаний и отдельных разработчиков.

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

При выборе инструментария для решения графовой задачи нужно помнить, что применение только графового математического аппарата не всегда приводит к цели. Например, его применение при решении задачи анализа государственных закупок для выявления аномалий не принесет результата. Однако, если сопоставить параметры вершин — участников закупочного процесса, применить методы нечеткой логики (например, анализируя вершины графа «ИП Смирнов А. С., Москва, Денисовский пер., 26» и «ООО Смирнов, Денисовский 26») и рассчитать различные меры центральности таких вершин, можно получить результаты, позволяющие выдать задание для проверки регулирующим органам.

***

Сегодня имеется множество инструментов, позволяющих решать задачи графовой аналитики, каждый из которых эффективен в определенных ситуациях. Например, при построении транзакционной системы, оперирующей графовой моделью данных, могут быть использованы специализированные СУБД neo4j, OrientDB и т. п. В случае, если у компании, решающей задачи графовой аналитики, уже имеются кластер Hadoop и штат квалифицированных разработчиков, знакомых с языком Scala, логично обратить внимание на систему GraphX. Предприятиям стоит взять на вооружение и универсальные аналитические решения, такие как Aster, ввиду высокой степени их готовности к применению, невысоким требованиям к подготовке пользователей в области ИТ и простоты интеграции в корпоративную информационную среду.

Литература

  1. Андрей Николаенко, Дмитрий Волков. Новые инструменты Hadoop // Открытые системы.СУБД. — 2014. — № 10. — С. 12–14. URL: http://www.osp.ru/os/2014/10/13044382 (дата обращения: 18.09.2016).
  2. Михаил Ганюшкин. Вам TUDA // Открытые системы.СУБД. — 2013. — № 2. — С. 27–29. URL: http://www.osp.ru/os/2013/02/13034552 (дата обращения: 18.09.2016).

Александр Смирнов (Alexander.Smirnov@Thinkbiganalytics.com) — евангелист Hadoop, компания Teradata, подразделение Think Big (Москва); Дамир Гайнанов (damir@dc.ru) — руководитель кафедры аналитики Больших Данных и методов видеоанализа, Уральский федеральный университет им. Б.Н. Ельцина (Екатеринбург).

 
Купить номер с этой статьей в PDF