Реализация алгоритма анализа данных на графовых структурах

Структура программы

Разрабатываемый алгоритм будет внедрен в существующую систему анализа реляционных данных, для этого необходимо ознакомиться с её архитектурой.

 На рисунке 18 изображена архитектура системы.

Рисунок 18 – Структура программы

Данная схема содержит инструменты и методы анализа данных, которые будут интегрированы по результатам реализации алгоритма.

На схеме, отражающей архитектуру программы, можно выявить следующие ключевые инструменты:

1. Angular – платформа для разработки мобильных и настольных веб-приложений, написанная на языке TypeScript, в данной работе отвечает за визуализацию интерфейса.

2. Neo4j – платформа графовых баз данных, созданная специально для хранения не только данных, но и связей между ними. Подключение приложения

к данной платформе осуществляется через драйвер JDBC, при помощи которого производится обработка запросов для получения данных графов.ApacheDruid

 

 

представляет собой столбчатое хранилище, реализованное на основе OLAP–модели, куб которой строится по измерениям и мерам, при помощи которых строятся диаграммы.

3. SpringFramework – комплексная модель программирования и конфигурации современных корпоративных приложений на основе языка Java –на любой платформе развертывания.

Так как в основе приложения используется язык Java, это означает, что мы можем подключить любую базу данных, которая поддерживает JDBC–driver. Neo4jподдерживает подключение по jdbc– драйверу, следовательно для подключения платформы Neo4j необходимоописать подключение в дополнении к абстрактным классам драйвера.

Описание программного обеспечения

Список используемых при разработке алгоритма и написании кода программы, программных обеспечений включает в себя:

1. IntelliJIDEA – интегрированная среда разработки программного обеспечения, список языков программирования которой включает в себя язык Java и Typescript, используемые в работе.

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

3. Neo4jDesktop – настольное приложение, которое позволяет управлять и администрировать локальные базы данных Neo4j. Его использование обусловлено тем, что при установке предоставляется Neo4jEnterpriseEdition–лицензия, которая открывает доступ к полному функционалу графовой базы данных.

4. Neo4jBrowserпредоставляет возможность взаимодействия с данными графов с полными CRUDвозможностями.

Тестирование

В данном подразделе рассматривается программная реализация методов алгоритма, а также проводится тестирование основных функций системы.

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

Подключение графовой СУБД

Для того, чтобы получить данные с платформы Neo4j, для началанеобходимо создать подключение, данные о подключение необходимо ввести в форму, которая изображена на рисунке 19.

Рисунок 19 – Форма подключения к графовой БД

Необходимо выбрать из списка баз «Neo4j» и ввести данные подключения к базе: хост, порт, имя пользователя и пароль. Далее необходимо нажать «Проверка достоверности», запустится процесс валидации базы, будет проверена корректность введённых данных и возвращён ответ «Допустимое соединение», если данные верны и подключение допустимо, иначе ответ будет «Проверьте корректность введённых данных» или «Сервер недоступен» если база находится в инактиве.

Валидация базы данных происходит при помощи проверочного запроса, выполняемого при помощи метода:

getTestQuery(JdbcConnectInformation jdbcConnectInformation) {return "MATCH (N) RETURN N LIMIT 10";}

где jdbcConnectInformation является объект с введенными пользователем данными.

Код классов отвечающих за подключение к базе данных Neo4jнаходится в приложении А.

При нажатии кнопки готово подключение сохраняется и добавляется в список подключенных баз данных (рисунок 20), а метаданные о базе сохраняются в базу данных PostgreSQL.

Рисунок 20 – Список подключенных баз данных

Визуализация графа

Самым важным в анализе данных на графа является непосредственное отображение его вершин и связей.

Рассмотрим компонент визуализации графа и его ключевые методы. Одной из ключевых функций являетсяметод ngOnInit, который представлен на рисунке 21.

Рисунок 21 – Инициализация графа

Данный метод отвечает за инициализацию компонента графа. Внутри данного метода можно наблюдать способ получения объекта графа из d3service, в котором инициализирован метод getForceDirectedGraphна вход, которому подаются массивы вершин и их связей, а также options–настройки графа, которые включают ширину и высоту панели отображения.

Объект tickerвызывающий метод subscribeвыполняет обновление графа при каждом изменении данных вершин и связей, включая их местоположение внутри графа.Решение коллизий (collide) и силу отталкивания (charge) инициализируются в simulation (рисунок 22).

Рисунок 22 – Настройка положения вершин графа

При инициализации simulationрешаются проблема перекрывания вершин друг другом путём расчета радиуса каждой из вершин, а также силы отталкивания вершин друг от друга chargeValue.

Результатом запуска симуляции, объект которого инициализирован в методе getForceDirectedGraph изображён на рисунке 23.

Рисунок 23 – Отображение вершин и связей графа

При нажатии на выпадающее меню «Графовая БД» появляется список с доступными к подключению базы данных. При выборе какого-либо графа происходит процесс получения графа из БД.

Кластеризация

Рассмотрим компонент визуализации результатов алгоритма кластеризации. Поиск сообществ в графах производится путём выполнения запроса, изображенного на рисунке 24.

Рисунок 24 – Кластеризация методов SCC

Результатом выполнения данного запроса является пара: идентификатор вершины и номер кластера, по которому выполняется присвоение цвета определенной группе вершин.

Результат кластеризации изображен на рисунке 25.

Рисунок 25 – Результат выполнения кластеризации.

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

Ранжирование

Рассмотрим компонент визуализации результатов алгоритма ранжирования. Расчёт рангавершин в графах производится путём выполнения запроса, изображенного на рисунке 26.

Рисунок 26 – Ранжирование вершин графа

Результатом выполнения данного запроса является пара: идентификатор вершины и еёранг, по которому выполняется присвоение радиуса определенной вершины.

Результат ранжирования изображен на рисунке 27.

Рисунок 27 – Результат выполнения ранжирования.

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

Поиск кратчайшего пути

Рассмотрим компонент визуализации результатов алгоритма поиска кратчайшего пути. Поиск кратчайшего пути между вершинами в графах производится путём выполнения запроса, изображенного на рисунке 28.

Рисунок 28 – Поиск кратчайшего пути

Результатом выполнения данного запроса является полный список вершин, которые включают найденный путь.

Результат ранжирования изображен на рисунке 29.

Рисунок 29 - Результатпоиска кратчайшего пути.

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

Группировка результатов

Результаты анализа данных при группировке результатов сохраняются в csvформате, рассмотрим метод их сохранения в файл (рисунок 30).

Рисунок 30 – Метод сохранения результатов

В данном методе на вход поступает массив строк, формат элементов которой представляется в виде строки «алгоритм,граф,наименование,результат», каждый элемент записывается в файл results.csvпри помощи класса FileWriter.

Далее необходимо создать источник по данным из файла results.csv, для этого необходимо загрузить файл, после чего появится форма предварительного просмотра данных (рисунок 31).

Рисунок 31 – Форма просмотра импортированных данных

Далее данные загружаются в столбчатое хранилище ApacheDruid, после того как наш файл загружен, это можно определить по статусу (рисунок 32)

Рисунок 32 – Статус загрузки данных

После того, как данные были успешно загружены можно создать диаграмму с результатами анализа данных по конкретному алгоритму и графам (рисунок 33).

Рисунок 33 – Диаграмма результатов анализа данных

На данном рисунке предоставлены результаты по поиску кратчайшего пути на трех графах, которые сгруппированы по наименованию улиц (ось х) и результат выполнения алгоритма (ось у) – расстояние.

Выводы по главе 4

В данной главебыло проведено тестирование методов анализа данных, а также рассмотрены методы визуализации и приведено их описание.

В результате тестирования было выявлено, что программа позволяет выполнять все описанные раннее методы анализа данных и отображает их результаты на графе. Следовательно программа работает корректно, и задача визуализации данных выполнена.

 

ЗАКЛЮЧЕНИЕ

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

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

В ходе разработки алгоритма была составлена математическая модель и выполнено проектирование и моделирование.

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

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