Машинное представление больших графовых моделей

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

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 08.02.2022
Размер файла 5,1 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Машинное представление больших графовых моделей

А.С. Бождай1, С.В. Прошкин2

1,2Пензенский государственный университет, Пенза, Россия

Аннотация

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

Ключевые слова: машинное представление графов, большие графы, структуры данных, графовые БД, большие данные, программные фреймворки

Введение

Большие объемы данных, разнородность и недостаточная структуризация - основные проблемы при проектировании информационных моделей современных информационных систем. Кроме того, представление данных в значительной мере зависит от специфики предметных областей. Социально-экономические сферы преимущественно связаны с индивидуализированными, хорошо различимыми объектами. Подобные дискретно-сетевые структуры удобно представлять графовыми моделями. Учитывая тот факт, что современные информационно-аналитические системы оперируют большими данными (Big Data), графовые хранилища информации также приобретают статус «больших». При этом для обеспечения требуемой производительности традиционные матричные и списочные форматы представления графов требуют существенной модификации. Кроме того, в последнее время появились и альтернативные идеи представления графовых структур, учитывающие специфику больших данных. Цель данной статьи заключается в рассмотрении наиболее перспективных современных представлений больших графов с учетом следующих основных факторов:

- адекватности представления (полного и правильного описания моделируемого процесса и явления);

- ресурсоемкости (получаемые структуры данных должны быть экономичны с точки зрения занимаемой памяти или допускать распределенное хранение);

- алгоритмизации (возможности алгоритмической обработки при решении задач как численной, так и символьной специфики).

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

Основная часть

Граф - математический объект, состоящий из двух множеств Є = (V, Е). Одно из них - конечное множество (V), его элементы называются вершинами графа. Другое множество (Е) состоит из пар инцидентных (связанных) вершин, эти пары называются ребрами графа [1, 2]. Под большим графом, будем понимать графы, количество вершин/ребер которых превышает 105 единиц [3].

Представление графа в памяти компьютера (формат хранения) влияет на общую производительность графовых алгоритмов и объем требуемых емкостных ресурсов.

При работе с графами, количество вершин/ребер которых достигает порядка миллиона и более единиц, применение известных способов машинного представления сопряжено с определенными трудностями. Как было отмечено ранее, традиционные матричные и списочные структуры данных - не самое оптимальное решение для хранения больших графов. Матрицы в таких случаях оказываются сильно разряженными, т.е. содержат большое количество нулевых элементов. Кроме того, при таком формате хранения возникает проблема быстрого доступа к данным.

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

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

Фрагмент графа, представленный списком смежности, отображен на рис. 1.

Рис. 1. Фрагмент графа и его представление в виде списочной структуры

Рис. 2. Фрагмент графа и его представление в виде матричной структуры

Матрица смежности графа - это двоичная квадратная матрица (рис. 2), количество строк и столбцов которой равна количеству вершин графа, а значение «1» в ячейке матрицы показывает наличие ребра между двумя вершинами, соответствующими индексу столбца и строки данной ячейки.

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

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

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

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

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

- если большинство элементов матрицы - нули, то целесообразно хранить только ненулевые значения вместе с их координатами;

- если матрица симметрична (симметрия относительно главной/побочной диагонали), то можно разбить матрицу на части элементов, хранить половину частей, а остальные вычислять из симметрии.

Мультисписок - базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит данные и одну или две ссылки на следующий и/или предыдущий узел списка [4]. В виде мультисписков чаще всего представляются разряженные матрицы.

Мультисписок хранит только ненулевые элемента (рис. 3), а значит, является довольно эффективной структурой для хранения разряженных матриц. Каждый элемент мультисписка является элементом двух списков (список-строка/список-столбец).

Матрица представлена списками (т + п), где т - число строк, п - число столбцов. Элементы мультисписка хранят номер строки и номер столбца, значения матрицы, а также ссылки на следующий элемент в строке и в столбце. Такая структура характерна только для односвязных списков.

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

Рис. 3. Фрагмент графового представления с использованием многомерных списков

Для хранения графов больших размеров также используют специализированное ПО, распределенные фреймворки, графовые базы данных (БД). Рассмотрим основные из них.

Neo4j называется графовой базой данных, поскольку она эффективно реализует графовую модель свойств вплоть до уровня хранилища. База данных использует указатели для навигации и обхода графа. В отличие от обработки графов или библиотек в памяти, Neo4j также предоставляет полные характеристики базы данных, включая соответствие транзакций ACID (Atomicity, Consistency, Isolation, Durability), поддержку кластеров и отработку отказа во время выполнения, что делает его пригодным для использования графов для данных в производственных сценариях.

Neo4j использует специализированный способ моделирования данных. Модель данных предусматривает два типа сущностей: вершины и ребра. Сущности могут обладать набором свойств. В Neo4j наборы данных могут принимать различные виды: например, вершина «Черненко К. У.» связана ребром «является предшественником» с вершиной «Андропов Ю. В.», при этом обе эти вершины связаны ребром типа «занимал должность» с вершиной «Генеральный секретарь». Отсутствие жестко заданной модели данных позволяет добавлять новые связи в модель или изменять наборы данных уже существующих.

Neo4j работает с двумя типами кэширования: объектный и файловый. Файловый напрямую обрабатывает данные с жесткого диска, что увеличивает и скорость чтения, и скорость записи. Объектный кэш отвечает за хранение различных объектов графа (вершины, ребра, свойства). Использование двух типов кэширования позволяет достичь максимальной производительности в БД. Объекты графа хранятся в специализированном формате. За счет этого увеличивается скорость обхода графа [5].

Компоненты, которые составляют Neo4j-модель графа:

- узлы - это сущности в графе. Они могут содержать любое количество атрибутов (пар ключ-значение), называемых свойствами. Узлы могут быть помечены метками [6, 7];

- отношения, обеспечивают направленные, именованные, семантически релевантные связи между двумя узловыми сущностями. Отношение всегда имеет направление, тип, начальный узел и конечный узел. Как и узлы, отношения так же могут иметь свойства. В большинстве случаев отношения имеют количественные свойства, такие как вес, затраты, расстояния, рейтинги, временные интервалы или сильные стороны. Благодаря эффективному способу хранения связей два узла могут совместно использовать любое количество или тип связей без ущерба для производительности. Хотя они хранятся в определенном направлении, отношения всегда могут эффективно перемещаться в любом направлении [8].

Широкое распространение в области хранения графовых БД получила платформа для работы с большими данными Hadoop.

Hadoop - это свободно распространяемый набор программных продуктов и фрейм- ворков для проектирования и администрирования систем на основе больших данных. Эта основополагающая технология хранения и обработки больших данных [6, 7].

Среди наиболее известных и значимых продуктов Hadoop можно выделить:

Hadoop Common - набор программных библиотек и утилит для поддержки инфраструктурных решений с распределенным представлением больших данных.

HDFS (Hadoop Distributed File System - распределенная файловая система) - технология хранения файлов, реализуемая в виде распределенного кластера, состоящего из нескольких узлов (рис. 4). Входные файлы разбиваются на блоки с последующим распределением по нескольким сетевым узлам (серверам). При этом для каждого блока создается некоторое количество копий (реплик), размещаемых на других узлах (так называемая репликация данных на случай выхода из строя отдельных узлов).

Рис. 4. Принцип работы файловой системы HDFS [9]

YARN (Yet Another Resource Negotiator) - набор системных утилит, обеспечивающих общую координацию, совместное использование, масштабирование и надежность работы распределенных приложений.

MapReduce - платформа, реализующая концепцию распределенных вычислений на сетевых кластерах.

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

Наиболее популярным фреймворком с открытым исходным кодом для работы с большими графами является GraphX. В GraphX используется вычислительный механизм Apache Spark [10], за счет которого достигаются высокие показатели производительности при обработке графов в оперативной памяти. Тем не менее, GraphX не предназначен специально для решения задач оптимального хранения графов. Главное назначение этого инструмента - аналитика на основе графовых моделей.

Важное достоинство GraphX - простота масштабирования за счет использования вычислительных средств Spark. Граф представляется в виде двух наборов данных (вершины и ребра), выраженных специализированными для Spark распределенными таблицами RDD (Resilient Distributed Dataset), которые могут быть созданы на основе текстовых файлов, таблиц в реляционных СУБД и других источников данных, поддерживаемых Spark.

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

Заключение

Таким образом, выбор форматов машинного представления больших графов обуславливается двумя важнейшими факторами: емкостными требованиями при хранении и скоростными требованиями при анализе и реализации графовых алгоритмов. При реализации настольных программно-аналитических систем, развернутых на базе одного ПК, хорошим решением выглядит использование графовой модели данных N004). Если требуется обрабатывать графы порядка 109 и более вершин, то наиболее приемлемый выход, связан с кластеризованными решениями, основанными на распределенных файловых системах и концепции параллельных вычислений MapReduce. Одним из таких возможных решений является программная библиотека GraphX, предоставляющая разработчику возможность горизонтального масштабирования при обработке и анализе больших графовых моделей.

Список литературы

граф списочное матричное представление данные

1. Алексеев В. Е., Захарова Д. В. Теория графов : учеб. пособие. Н. Новгород : Нижегородский гос. университет, 2017. 119 с.

2. Оре О. Теория графов. М. : Наука, 1980. 336 с.

3. Визуализация больших графов. URL: https:// habr.com (дата обращения: 20.04.2021).

4. Cormen T., Leiserson Ch., Rivest R., and Stein Cl. Introduction to Algorithms. 2nd edition. London : The MIT Press, 2001. 226 p.

5. Габриелян Г. А. Графовая база данных Neo4j для проектирования высоконагруженных систем // Студенческий электронный научный журнал. 2018. № 11. URL: https://sibac.info(дата обращения: 20.04.2021).

6. Hadoop. URL: https://rn.habr.com(дата обращения: 21.04.2021).

7. Новые инструменты Hadoop. URL: https://www.osp.ru(дата обращения: 20.04.2021).

8. Neo4j Graph Database Platform. URL: https://neo4j.com(дата обращения: 19.04.2021).

9. Новые методы работы с большими данными: победные стратегии управления в бизнес- аналитике : науч.-практ. сб. / под ред. А. В. Шмида. М. : ПАЛЬМИР, 2016. 528 с.

10. Введение в Apache Spark. URL: https://habr.com(дата обращения: 21.04.2021).

Размещено на Allbest.ru

...

Подобные документы

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

    курсовая работа [29,2 K], добавлен 09.02.2011

  • Этапы статистического анализа данных, приемы и методы его проведения. Ключевые положения закона больших чисел в теории вероятностей, его общий смысл. Теорема Бернулли - простейшая форма закона больших чисел. Количество данных, способы его измерения.

    реферат [112,3 K], добавлен 03.03.2014

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

    курсовая работа [827,2 K], добавлен 19.04.2011

  • Изучение в реальных условиях способов представления знаний во Всемирной сети. Представления данных в интернет и способы эффективной публикации данных. Конфигурация Web-сервера на виртуальном хостинге. Настройка и отладка работы сайтов на разных CMS.

    отчет по практике [947,2 K], добавлен 09.02.2012

  • Классы и группы моделей представления знаний. Состав продукционной системы. Классификация моделей представления знаний. Программные средства для реализации семантических сетей. Участок сети причинно-следственных связей. Достоинства продукционной модели.

    презентация [380,4 K], добавлен 14.08.2013

  • Анализ современных технологий моделирования организационных систем. Основные понятия теории мультимножеств и операции над ними. Использование мультимножеств для представления UFO-моделей. Представление операций над UFO-моделями в Microsoft Excel.

    дипломная работа [1018,4 K], добавлен 17.03.2012

  • Разработка программного продукта, позволяющего автоматизировать деятельность предприятия. Автоматизация ввода и обработки больших объемов информации. Формирование выходной документации. Установка системы и порядок работы с дистрибутивом. Обзор алгоритма.

    курсовая работа [3,6 M], добавлен 18.02.2013

  • Формы представления моделей: модели материальные и модели информационные. Формализация текстовой информации, представление данных в табличной форме. Граф как совокупность точек, соединённых между собой линиями. Упорядочение информации в форме графа.

    реферат [2,5 M], добавлен 10.04.2010

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

    курсовая работа [397,5 K], добавлен 09.08.2015

  • Фрагментарная обработка больших объектов в мультимедийных базах данных (прямой доступ к отдельным фрагментам хранимого объекта). Двухуровневое разбиение полей большого размера. Древовидное представление данных. Части объекта, определяемые поддеревом.

    презентация [93,4 K], добавлен 11.10.2013

  • Применение теории графов и алгоритмов на графах среди дисциплин и методов дискретной математики. Граф как совокупность двух множеств. Основные способы численного представления графа. Элементы и изоморфизмы графов. Требования к представлению графов в ЭВМ.

    курсовая работа [162,2 K], добавлен 04.02.2011

  • Сущность данных и информации. Особенности представления знаний внутри ИС. Изучение моделей представления знаний: продукционная, логическая, сетевая, формальные грамматики, фреймовые модели, комбинаторные, ленемы. Нейронные сети, генетические алгоритмы.

    реферат [203,3 K], добавлен 19.06.2010

  • Базы данных как совокупность структур, предназначенных для хранения больших объемов информации и программных модулей. Анализ способов создания базы данных для учета книг личной библиотеки, особенности использования языка программирования C++Builder.

    курсовая работа [8,1 M], добавлен 10.01.2014

  • Характеристика сущности микропроцессора - программного устройства обработки данных, выполняемого средствами микроэлектронных технологий в корпусе одной или же нескольких больших интегральных схем. Изучение общей структуры микропроцессоров и их видов.

    контрольная работа [113,5 K], добавлен 05.09.2010

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

    статья [170,5 K], добавлен 01.05.2010

  • Основные понятия теории графов. Ценность системного подхода. Представления операций во времени. Структурно-лингвистическое (знаковое) моделирование. Формы и средства графического представления информации. Методы формализованного представления систем.

    курсовая работа [2,2 M], добавлен 15.06.2015

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

    курсовая работа [33,1 K], добавлен 21.07.2012

  • Система управление базами данных, реляционная модель. Принципы взаимодействия между клиентскими и серверными частями. Трехуровневая модель технологии "клиент-сервер". Фрактальные методы сжатия больших объемов данных. Анализ концепции хранилища данных.

    курс лекций [265,0 K], добавлен 05.06.2009

  • Функционально законченное программное управляемое устройство обработки информации, в виде одной или нескольких больших или сверхбольших интегральных схем. Функции микропроцессора Pentium, основные параметры. Технология гиперконвейерной обработки.

    учебное пособие [1,1 M], добавлен 09.02.2009

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

    курсовая работа [1,3 M], добавлен 20.10.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.