В настоящее время модели данных на основе сложных сетей находят все более широкое применение в различных областях науки от математики и информатики до биологии и социологии. Основополагающими русскоязычными статьями являются работы И.А. Евина , О.П. Кузнецова и Л.Ю. Жиляковой . Профессор К. В. Анохин предлагает рассматривать сложные сети как основу для построения комплексных биологических моделей.
Сложные сети и сложные графы В настоящее время термины «сложная сеть» или «комплексная сеть», которые являются различными переводами англоязычного термина «complex network») и термин «сложный граф» (англ. «complex graph») часто употребляются как синонимы. В работе [4, стр. 14] отмечается, что термин «сложная сеть», как правило, употребляется для обозначения реальной исследуемой системы, в то время как термин «сложный граф» обычно используют для обозначения математической модели такой системы. Наибольшие разночтения вызывает термин «сложный» применительно к графовым моделям. Как правило, термин «сложный» трактуется в двух вариантах: Плоские графы (сети) очень большой размерности. Такие сети могут включать миллионы и более вершин. Ребра, соединяющие вершины, могут быть ненаправленными или направленными. Иногда используется модель мультиграфа, в этом случае две вершины могут соединяются не одним, а несколькими ребрами. Именно такую модель в литературе чаще всего называют «сложной сетью». Исследования данной модели проводятся в основном специалистами в области математики. Исследователи рассматривают такие параметры как распределение количества связей между вершинами, выделение сильно связанных подграфов. Часто для связей вводится количественная метрика, которая обычно трактуется как расстояние между вершинами. Активно исследуются динамические модели, в которых к существующей сложной сети случайным образом добавляются вершины и ребра. Такие модели представляют интерес при изучении социальных сетей, глобальных компьютерных сетей, различных социологических и биологических моделей. Но они не очень хорошо помогают при описании сложных моделей данных. Сложные графы, в которых используется сложное (комплексное) описание вершин, ребер и/или их расположения. Часто в таких моделях отказываются от плоского расположения вершин и ребер. Именно подобные модели могут быть наиболее полезны при описании сложных моделей данных. На сегодняшний день известны четыре подобных модели: гиперграф, гиперсеть, метаграф и многоуровневая сеть (которая является упрощенным вариантом гиперсети). В настоящее время в литературе ещё не появился единый «собирательный термин» для моделей такого класса. Авторы моделей, как правило, используют собственные названия для каждой модели, не всегда даже указывая на родство предлагаемой модели со сложными графами (сетями). Для подобного класса моделей можно предложить такой «собирательный термин» как «ансамбли сложных сетей (графов)». Для гиперсетевой и метаграфовой моделей может быть использован термин «сложные сети (графы) с эмерджентностью», так как данные модели реализуют принцип эмерджентности, хорошо известный в общей теории систем.
Далее мы рассмотрим несколько моделей сложных графов в трактовке 2 и попытаемся показать, каким образом данные модели могут быть полезны для описания моделей данных.
Возникновение идеи Возникновение математических моделей сложных графов можно отнести ко второй половине XX века. Первые работы по гиперграфам можно отнести к 1960-м годам. Теория гиперсетей развивалась независимо в 1970—1980 годы В. К. Попковым (в СССР) и Р. Аткиным и Дж. Джонсоном (в Великобритании). Первые работы А. Базу и Р. Блэннинга по метаграфам появились в 1990-е годы. Идея использования сложных графовых моделей в качестве моделей данных СУБД находится в начале развития. В настоящее время в наиболее развитых графовых СУБД, таких как GRAKN.AI, HypergraphDB реализована лишь иерархическая гиперграфовая модель данных. Более сложные гиперсетевая и метаграфовая модели данных ждут своей реализации.
Суть технологии (идеальная модель функционирования, ради которой началась разработка технологии) Возможность информационного моделирования и визуализации сложных предметных областей, более удобных по сравнению с плоскими графами.
Ожидаемые преимущества Основным преимуществом графовых моделей данных является возможность моделирования основных понятий (концептов) предметной области и связей между ними. Традиционное описание на основе плоских графов (flat graphs) обладает рядом недостатков: Невозможность обобщения (укрупнения) понятий путем выделения фрагментов графа. Слабые возможности для аннотирования фрагментов графов знаний дополнительными информационными элементами. Слабые возможности связи нескольких графовых моделей между собой. Фактически такая связь означает появление ансамбля графовых моделей как надстройку над графовой моделью. Модели данных на основе ансамблей сложных графов позволяют устранить указанные недостатки, что позволяет моделировать более сложные предметные области.
Модели ансамблей сложных сетей (графов) В этом разделе будут рассмотрены четыре модели: гиперграф, гиперсеть, метаграф и многоуровневая сеть. Далее мы покажем, что именно метаграфовая модель является наиболее гибкой и удобной для описания моделей данных. Метаграфовая модель будет рассмотрена в качестве основной модели. Другие модели будут рассмотрены в сравнении с метаграфовой моделью.
Описание метаграфовой модели данных Основополагающими работами по теории метаграфов являются работы А. Базу и Р. Блэннинга, которые в 2007 году были обобщены в виде монографии . Модель, предложенная в , в дальнейшем была адаптирована и представлена в статьях [6-8]. В данном разделе кратко рассмотрим формализованную модель метаграфа в соответствии с [6-8].
, где — метаграф; — множество вершин метаграфа; — множество метавершин метаграфа; — множество ребер метаграфа; — множество метаребер метаграфа.
Вершина метаграфа характеризуется множеством атрибутов:
, где — вершина метаграфа; — атрибут.
Ребро метаграфа характеризуется множеством атрибутов, исходной и конечной вершиной и признаком направленности:
, где где — ребро метаграфа; — исходная вершина (метавершина) ребра; — конечная вершина (метавершина) ребра; — признак направленности ребра ( — направленное ребро, — ненаправленное ребро); — атрибут.
Фрагмент метаграфа:
, где — фрагмент метаграфа; — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.
Таким образом, фрагмент метаграфа в общем виде может содержать произвольные вершины (метавершины) и ребра (метаребра) без ограничений. Ограничения вводятся на фрагменты метаграфа, входящие в метавершину и метаребро.
Метавершина метаграфа:
, где — вершина метаграфа; — атрибут, — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.
Таким образом, метавершина в дополнение к свойствам вершины включает вложенный фрагмент метаграфа. При этом ребра и метаребра этого фрагмента могут быть только ненаправленными, .
Метаребро метаграфа:
, где — метаребро метаграфа; — исходная вершина (метавершина) ребра; — конечная вершина (метавершина) ребра; — признак направленности метаребра ( — направленное метаребро, — ненаправленное метаребро); — атрибут; — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.
Таким образом, метаребро в дополнение к свойствам ребра включает вложенный фрагмент метаграфа. При этом ребра и метаребра этого фрагмента могут быть только направленными, .
Определения метавершины и метаребра являются рекурсивными, так как элементы могут быть, в свою очередь, метавершинами и метаребрами. Метавершина является формализмом описания данных, а метаребро — формализмом описания процессов.
Наличие у метавершин собственных атрибутов и связей с другими вершинами является важной особенностью метаграфов. Это соответствует принципу эмерджентности, то есть приданию понятию нового качества, несводимости понятия к сумме его составных частей. Фактически, как только вводится новое понятие в виде метавершины, оно «получает право» на собственные свойства, связи и т. д., так как в соответствии с принципом эмерджентности новое понятие обладает новым качеством и не может быть сведено к подграфу базовых понятий.
Таким образом, метаграф можно охарактеризовать как «сложный граф с эмерджентностью» или «сложную сеть с эмерджентностью», то есть фрагмент сети, состоящий из вершин и связей, может выступать как отдельное целое.
Пример описания метаграфа показан на рис. 1. Данный метаграф содержит вершины, метавершины и ребра. На рис. 1 показаны три метавершины: , и . Метавершина включает вершины и связывающие их ребра . Метавершина включает вершины и связывающее их ребро . Ребра являются примерами ребер, соединяющих вершины - и -, включенные в различные метавершины и . Ребро является примером ребра, соединяющего метавершины и . Ребро является примером ребра, соединяющего вершину и метавершину . Метавершина включает метавершину , вершины и ребро из метавершины а также ребра , что показывает холоническую структуру метаграфа.
Пример описания метаребра метаграфа представлен на рис. 2. Метаребро содержит метавершины и связывающие их ребра. Исходная метавершина содержит фрагмент метаграфа. В процессе преобразования исходной метавершины в конечную метавершину происходит дополнение содержимого метавершины, добавляются новые вершины, связи, вложенные метавершины.
Если метавершины предназначены прежде всего для описания данных и знаний, то метаребра предназначены в большей степени для описания процессов. Таким образом, метаграфовая модель позволяет в рамках единой модели описывать данные, знания и процессы.
Сравнение метаграфовой модели с моделью гиперграфа В этом разделе мы рассмотрим модель гиперграфа и сравним её с метаграфовой моделью.
Рассмотрим формализованную модель гиперграфа в соответствии с :
, где — гиперграф; — множество вершин гиперграфа; — множество непустых подмножеств , называемых гиперребрами; — вершина гиперграфа; — гиперребро гиперграфа.
Гиперграф может быть направленным или ненаправленным. Гиперребра ненаправленного гиперграфа показывают включение вершин, в то время как гиперребра направленного гиперграфа задают порядок обхода вершин.
Пример описания гиперграфа показан на рис. 3. Данный ненаправленный гиперграф включает три гиперребра: . Гиперребро включает вершины . Гиперребро включает вершины и . Гиперребро включает вершины и . Гиперребра и имеют общую вершину . Все вершины гиперребра также являются вершинами гиперребра .
Сравнивая рис. 1 и 3, можно отметить некоторые сходства между метавершиной и гиперребром. Но эти сходства достаточно условны. Если гиперребро гиперграфа может включать только вершины, то метавершина метаграфа может включать как вершины (метавершины), так и ребра (метаребра).
В соответствии с определением гиперграфа, операция иерархической вложенности для гиперребер не определена явным образом, можно говорить только о пересечении множеств вершин, вложенных в гиперребра.
Поэтому, хотя гиперграф и содержит гиперребра, но не позволяет моделировать сложные иерархические зависимости и не является полноценной «сложной сетью с эмерджентностью». В отличие от гиперграфа, метаграф позволяет естественным образом моделировать сложные иерархические зависимости и является «сложной сетью с эмерджентностью».
Необходимо отметить, что некоторые современные СУБД реализуют концепцию иерархического гиперграфа, который можно определить следующим образом:
, где — иерархический гиперграф; — множество вершин гиперграфа; — множество гиперребер гиперграфа; — вершина гиперграфа; — гиперребро гиперграфа.
Отличие иерархического гиперграфа от обычного состоит в том, что в иерархическом гиперграфе как вершина, так и гиперребро принадлежат к объединённому множеству вершин и гиперребер.