Библиотека моделирования на графах

Материал из BrSTU Robotics Wiki
Перейти к: навигация, поиск

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

Автор: Anton Kabysh 17:37, 15 июня 2012 (MSK) Обсуждение

Введение

Графово-ориентированная модель представления данных (Graph Data Representation Model - GDRM) является одной из самых органичных и элегантных структур для представления любых данных и их взаимосвязи. Особенно подходит для представления сильно связанных данных и в тех случаях, когда отразить связи в данных так же важно, как и сами данные.

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

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

Базовые концепции

                        The evolution and diversity of existent db-models show that there is no silver bullet for data modeling.

Существует множество моделей граф-ориентированных моделей представления данных, как теоретических так и их практических реализаций. Введение в теоретические модели можно найти в обзоре Survey of Graph Database Models. Частичный обзор практических проектов приведен в разделе ниже, в разделе "Родственные проекты".

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

Узлы и отношения между ними

Фундаментальные блоки для графово-ориентированных моделей – это узлы (Node) и отношения (Relationship) между ними. Как узлы, так и вершины могут уметь свойства (Properties). Узлы чаще всего представляют сущности, но в зависимости от предметной области для этой цели могут быть использованы и отношения. У узлов есть числовой идентификатор - индекс.

Nodes.png

Рассмотрим простейший граф с одной вершиной и одним свойством:

Simple Node.png

Отношения организуют вершины в произвольные структуры, что позволяет придать графу графу вид списка, дерева, или любой другой. Отношение может объединять множество узлов (Nodes), но всегда имеет начальный узел (Start Node), конечный узел (End Node) и тип. Отношения могут так же иметь свойства, как и узлы. Каждое отношение имеет тип (RelationshipType), который уникальным образом идентифицируется по строковому имени (name).

Relationships.png

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

Рассмотрим примеры отношений. Бинарное отношение «знает» (KNOWS) включает два узла. Унарное отношение «Я» (МЕ) относится только к одной вершине. Отношение BRSTU_ROBOTICS включает в себя 5 вершин, и может расти или уменьшаться. Любое многомерное отношение стоит рассматривать как совокупность бинарных отношений между всеми попарно-входящими в него узлами. Удаление одного узла не ведет к удалению всего отношения до тех пор, пока узлов больше 2-х.

Binary.png Unary.png NAry.png

Свойства

Как узлы, так и отношения могут иметь свойства (Properties). Свойства – это пары ключ-значение, где ключом может быть любой объект, реализующий интерфейс Property, а значением любой из объектов, подходящий по ключу. Ключ имеет имя, но оно не является строгим для идентификации ключа. В качестве ключа не может быть null, но отсутствие значения по ключу может играть аналогичную роль.

Properties.png

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

Графово-ориентированная модель представления данных

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

Graph.png

Граф, с показанной структурой (только в качестве ребер - бинарные направленные дуги) и обладающий таблицами свойств, ассоциированных с вершинами и ребрами называется в науке Propery Graph.

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

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

Идентификаторы

Модель памяти

Граф в памяти может быть представлен десятками различных способов - матрицами, списками, и т.д. Каждый способ представления подходит для своих случаев и имеет как достоинства, так и недостатки. С каждым графом ассоциирована модель памяти (MemoryModel), которая определяет, как именно граф представлен в памяти. Модель памяти состоит из раздельных контейнеров для хранения узлов, отношений, свойств, обращающихся через стандартные интерфейсы.

MemoryModel.png

Например, количество опорных точек не фиксировано и для их представления требуется универсальная модель памяти, а вот вершины в цепи Маркова имеют только 2-3 связи и для них подходит совсем другая, более экономная и оптимизированная модель памяти. Таким образом, можно подобрать модель памяти под задачу, динамически поменять её во время работы или написать модель памяти/порт к уже существующей реализации граф-ориентированных модели представления данных в стороннем, open-source проекте.

Объектно-ориентированные графы

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

Объектно-ориентированный граф (Graph<V,E>), это такой граф, где в соответствие каждому узлу (Node) поставлен объект - вершина (Vertex). Для каждой связи (Link) между вершинами так же ставится в соответствие некоторый объект, представляющий данную связь (Edge). Объекты являются своего рода метками, ассоциированными с узлами и связями графа, которые их однозначно определяют.

Таким образом, объектно-ориентированный граф Graph<V,E> - это множество объектов вершин (V) и множество объектов связей между ними (E). Узел (Node) в таком случае, является представлением вершины в графе, а связь (Link) представлением соединения между вершинами. Объектно-ориентированные графы очень близки по своим свойствам к понятию графа, принятом в математике. Поскольку, на вершинах и связях графа могут находится произвольные объекты, объектно-ориентированные графы являются унивесальным инструментов задания связи между объектами в программе.

Примечательно, между узлами в объектно-ориентированном графе могут существовать как связи (Link) так и отношения (Relationship). И тот и другой вид соединений одинаково подходит для траверса (обхода) графа во всех направлениях. Связи и отношения используются для задания разных видов организации между узлами. Связи предназначены для прямого указания что с чем соединено. Тогда как отношения предназначены указания того, что узлы находятся друг с другом в некотором смысловом отношении. Любой из этих способов является достаточным, но комбинируя два вида отношений можно выражать сколь угодно сложные связи и смысловые зависимости между узлами.

ObjectOritentedGraph.png

Связь (Link), заимствует все черты отношений (Relationship), расширяя их, но не имеет изначально заданного типа (RelationshipType). Пока этот тип не задан явно, связь не может считаться отношением между вершинами. Если этот тип задан, то связь становится отношением между всеми узами, которые она связывает. Другими словами, связь обретает смысловую метку.

Объектно-ориентированные графы так же имеют модель памяти.

Индекс

Ограничения

Применимость

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

Чаще всего, на практике GDRM используется в классических приложениях для хранения оперативных данных в удобном виде, т.е. в качестве графово-ориентированной базы данных (Graph DB-Model). Такими данными может быть социальная сеть, карта маршрутов, пространство состояний,

Вторая, более новая, область использования GDRM заключается в использовании графа в качестве сложной вычислительной сети (complex network) обладающей некоторыми математическими параметрами и свойствами. Сюда попадают модели ИИ, такие как нейронные сети, деревья решений, AGI и любая другая когнитивная архитектура искусственного интеллекта. Сети такого типа получили распространение в последнее десятилетие; к ним можно отнести социальные сети, информационную сеть [граф цитирования, или связи в многоагентной системе], биологические сети и т.д.

Родственные проекты

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

Родственные проекты, из идеи из которых были позаимствованы.

  • Neo4j.org - пожалуй, самая популярная и производительная граф-ориентированная база данных, написанная на Java. Neo4J обладает поистине уникальной моделью данных, храня объекты и связи в качестве узлов и ребер графа. По заявлениям, может поддерживать до нескольких миллиардов узлов и связей. Для запросов, которые соответствуют этой модели (например, иерархических данных) они могут быть в тысячу раз быстрее, чем альтернативные варианты. Проект активно поддерживается и расширяется. Из этого проекта были позаимствованы идеи Relationships и Properties. Они была значительно переработаны и расширены, но обратная совместимость возможна. Планируется проект для разработки порта модели памяти под эту Graph-DB студентами.
  • JUNG2 - Java Universal Network/Graph Framework - предоставляет общий и расширяемый интерфейс и реализации практически всех типов графов. В ней реализовано все для моделирования, анализа и визуализации данных, которые могут быть представлены в виде графов или сети. JUNG поддерживает различные реализации графов: ориентированные, неориентированные, псевдографы, гиперграфы, деревья, леса и т.д. В настоящее время JUNG включает в себя реализацию ряда алгоритмов из теории графов, анализа данных и анализа социальных сетей, таких как программы для кластеризации, декомпозиции, оптимизации, генерация случайных графов, статистический анализ и расчет расстояний в сети, потоков и ранжирование. Скорее всего, проект прекратил своё развитие. Из этого фреймворка позаимствована идея объектно-ориентированных графов, которая была расширена представлениями Node и Link. Со временем, планируется включить некоторую часть функциональности из JUNG в данный проект, но эти задания будут выполняться студенческими командами по необходимости.
  • Blueprints и TinkerPop Stack - комплексное решение для работы с графами. Blueprints - это совокупность основополагающих интерфейсов для графов и их реализаций, с предоставляемым back-end-ом к сторонним реализациям графов, например к Neo4j или JUNG и др. Пишут, что Blueprints - это аналог JDBC в мире графов. TinkerPop Stack - это совокупность фреймворков, совместимых с Blueprints предназначенных для его поддержки и расширения. Pipes - манипулирование потоком данных. Gremlin - язык запросов к графу, как Perl для строк. Frames - объектно-графовый маппинг на основе аннотаций. Furnace - алгоритмы для графов. Rexster - REST сервер для графов. Из этого проекта ничего не было позаимствовано т.к. он был забыт на этапе анализа и проектирования. При сравнении в наших проектах больше общих идей, чем в других: модель памяти, подключаемые реализации и т.д.
  • FlockDB - графовая база данных, используемая в Twitter для их социального графа основанная на списках смежности. Адаптирована для их задач. Ориентирована на графы, где вершины имеют очень большое количество соседей, выполняются очень частые операции над списком смежности, но траверс не идет дальше соседних вершин. Еще один потенциальный кандидат на адаптацию в модель памяти.
  • HyperGraphDB - это расширяемая, портативная, распределенная, встраиваемая система общего назначения с open-source механизмом хранения данных. Эта система разработана специально для проектов использующих возможности искусственного интеллекта и семантического веба. Может использоваться как встраиваемая, объектно-ориентированная база данных для проектов любого масштаба. Отсюда можно позаимствовать сверхсложную граф-ориентированную когнитивную модель (вероятностный гиперграф) с механизмами вывода для искусственного интеллекта. Проект требует более глубокого изучения.
  • Animotron - еще один AI-based проект, требующий более внимательного изучения, написанный в России.

Сравнение

Представленные проекты просто титаны, имеют работающую и проверенную функциональность и признание в программистском мире. Казалось бы, разрабатывать что-то новое не имеет смысла. Итак, рассмотрим, какое место занимает наш проект среди них:

  • С Neo4j. Наш фреймворк имеет аналогичную графовую модель, что и Neo4j (немного адаптированную), но и расширяет её обобщая на объектно-ориентированные графы. Клиент может работать с графами как на уровне GDRM/Neo4j, так и на более высоком уровне объектно-ориентированных графов. С другой стороны, Neo4j - это промышленная система энтерпрайз уровня, с доказанной эффективностью и устойчивостью 24/7 и малыми требованиями к памяти. Neo4j рассматривается как основная реализация модели памяти для нашего фреймворка уровня встроенной граф-ориентированной базы данных для программных агентов.
  • C JUNG2. Наш фреймворк лучше чем JUNG, т.к. поддерживает явное выделение Node/Link/Relationship на графе, что форсирует клиентов работать на конкретных узлах, что в свою очередь форсирует быть данные и операции на столько локальными, на сколько это возможно. Напротив, JUNG не имеет переменных моделей памяти и хранит данные в одной глобальной таблице, и время всех операций растет тем больше, чем больше граф. С другой стороны, JUNG лучше тем, что имеет много реализаций алгоритмов и средств для визуализации графа.
  • С Blueprints. Оба фреймворка в конце концов будут похожи. Наш фреймворк лучше тем, что он использует другие, более современные паттерны для модуляризации кода, и итоговое API будет намного лаконичнее. Так же, в нашем фреймворке модель памяти рассматривается как составленная отдельных из компонент, каждая из которых имеет свою область ответственности, а не монолитная, как в Blueprints. Композитная модель памяти позволяет собирать итоговую модель из разных компонент. Например, делегировать обработку свойств на Key/Value базу данных, а графовую структуру хранить в памяти. С другой стороны, Blueprints ушел далеко вперед и имеет целостный стек решений и сильное комьюнити.
  • С когнитивными архитектурами. Наш фреймворк пока не имеет решений в этой области, но их потенциальное появление возможно. Отметим лишь, что существующие фреймворки когнитивных архитектур как правило имеют громадное, сверхсложное API, сопоставимое со сложностью задачи. В данных проектах необходимо разобраться, что бы понять, какую проблему и каким образом они решают. А дальше уже предпринимать какие либо решения.

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

Исходя из рассмотренного, цели будущие цели фреймворка:

  1. Предоставить интерфейсы, аналогично Blueprints, что бы мы могли опираться на проверенные и надежные реализации графов сторонних библиотек, т.к. некоторые вещи гарантированно сделаны лучше другими людьми.
  2. Сфокусироваться на областях, которые обошли вниманием существующие проекты: многоагентные графовые системы, графовые модели в робототехнике (графы соседства, байесовские сети доверия, деревья решений и т.д).
  3. Сохранение максимальной простоты и компактности с фокусом на предоставление решений. К сожалению, большинство существующих решений, за редкими исключениями, имеют просто колоссально огромные API.
  4. Большинство мировых проектов сфокусированы на обработке графовых данных в миллионы и миллиарды записей. Такие большие количества нам просто не нужны и вместо этого наш фреймворк сфокусируется на типовых и простых моделях, применимых наиболее часто. Банальные прямые графы, марковские процессы принятия решений и т.д.

Roadmap

  • M11 - Constraint Framework
  • M12 - Visitor Framework
  • M13 - Traversal Framework
  • M14 - Туториал, документация и примеры
  • M15 - Graph Visualization (using processing)
  • Релиз (approx. февраль 2013).