Interested Article - Модели данных на основе сложных графов

Введение

Сложные сети и сложные графы

В настоящее время модели на основе сложных сетей находят все более широкое применение в различных областях науки от математики и информатики до биологии и социологии. Основополагающими русскоязычными статьями являются работы И.А. Евина [1], О.П. Кузнецова и Л.Ю. Жиляковой [2]. Профессор К.В. Анохин [3] предлагает рассматривать сложные сети как основу для построения комплексных биологических моделей.

Термины «сложная сеть» или «комплексная сеть», которые являются различными переводами англоязычного термина «complex network») и термин «сложный граф» (англ. «complex graph») часто употребляются как синонимы. В работе [4, стр. 14] отмечается, что термин «сложная сеть», как правило, употребляется для обозначения реальной исследуемой системы, в то время как термин «сложный граф» обычно используют для обозначения математической модели такой системы.

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

Плоские графы (сети) очень большой размерности. Такие сети могут включать миллионы и более вершин. Ребра, соединяющие вершины, могут быть ненаправленными или направленными. Иногда используется модель мультиграфа, в этом случае две вершины могут соединяются не одним, а несколькими ребрами. Именно такую модель в литературе чаще всего называют «сложной сетью». Исследования данной модели проводятся в основном специалистами в области математики. Исследователи рассматривают такие параметры как распределение количества связей между вершинами, выделение сильно связанных подграфов. Часто для связей вводится количественная метрика, которая обычно трактуется как расстояние между вершинами. Активно исследуются динамические модели, в которых к существующей сложной сети случайным образом добавляются вершины и ребра. Такие модели представляют интерес при изучении социальных сетей, глобальных компьютерных сетей, различных социологических и биологических моделей. Но они не очень хорошо помогают при описании сложных моделей данных.
Сложные графы, в которых используется сложное (комплексное) описание вершин, ребер и/или их расположения. Часто в таких моделях отказываются от плоского расположения вершин и ребер. Именно подобные модели могут быть наиболее полезны при описании сложных моделей данных. На сегодняшний день известны четыре подобных модели: гиперграф, гиперсеть, метаграф и многоуровневая сеть (которая является упрощенным вариантом гиперсети). В настоящее время в литературе еще не появился единый «собирательный термин» для моделей такого класса. Авторы моделей, как правило, используют собственные названия для каждой модели, не всегда даже указывая на родство предлагаемой модели со сложными графами (сетями). Для подобного класса моделей можно предложить такой «собирательный термин» как «ансамбли сложных сетей (графов)». Для гиперсетевой и метаграфовой моделей может быть использован термин «сложные сети (графы) с эмерджентностью», так как данные модели реализуют принцип эмерджентности, хорошо известный в общей теории систем.

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

Возникновение идеи

Возникновение математических моделей сложных графов можно отнести ко второй половине XX века. Первые работы по гиперграфам можно отнести к 1960-м годам. Теория гиперсетей развивалась независимо в 1970-1980 годы В.К. Попковым (в СССР) и Р. Аткиным и Дж. Джонсоном (в Великобритании). Первые работы А. Базу и Р. Блэннинга по метаграфам появились в 1990-е годы. Идея использования сложных графовых моделей в качестве моделей данных СУБД находится в начале развития. В настоящее время в наиболее развитых графовых СУБД, таких как GRAKN.AI, HypergraphDB реализована лишь иерархическая гиперграфовая модель данных. Более сложные гиперсетевая и метаграфовая модели данных ждут своей реализации.

Суть технологии

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

Ожидаемые приемущества

Основным преимуществом графовых моделей данных является возможность моделирования основных понятий (концептов) предметной области и связей между ними. Традиционное описание на основе плоских графов (flat graphs) обладает рядом недостатков:

Невозможность обобщения (укрупнения) понятий путем выделения фрагментов графа.
Слабые возможности для аннотирования фрагментов графов знаний дополнительными информационными элементами.
Слабые возможности связи нескольких графовых моделей между собой. Фактически такая связь означает появление ансамбля графовых моделей как надстройку над графовой моделью.

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

Модели ансамблей сложных сетей

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