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

Введение

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

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

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

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

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

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

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

Суть технологии (идеальная модель функционирования, ради которой началась разработка технологии)

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

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

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

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

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

Модели ансамблей сложных сетей (графов)

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

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

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

$MG=\left\langle V,MV,E,ME\right\rangle$, где $MG$ – метаграф; $V$ – множество вершин метаграфа; $MV$ – множество метавершин метаграфа; $E$ – множество ребер метаграфа; $ME$ – множество метаребер метаграфа.

Вершина метаграфа характеризуется множеством атрибутов:

$v_{i}=\left\{atr_{k}\right\},v_{i}\in V$, где $v_{i}$ – вершина метаграфа; $atr_{k}$ – атрибут.

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

$e_{i}=\left\langle v_{S},v_{E},eo,\left\{atr_{k}\right\}\right\rangle ,e_{i}\in E,eo=true|false$, где где $e_{i}$ – ребро метаграфа; $v_{S}$ – исходная вершина (метавершина) ребра; $v_{E}$ – конечная вершина (метавершина) ребра; $eo$ – признак направленности ребра ($eo=true$ – направленное ребро, $eo=false$ – ненаправленное ребро); $atr_{k}$ – атрибут.

Фрагмент метаграфа:

$MG_{i}=\left\{ev_{j}\right\},ev_{j}\in (V\cup E\cup MV\cup ME)$, где $MG_{i}$ – фрагмент метаграфа; $ev_{j}$ – элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

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

Метавершина метаграфа:

$mv_{i}=\left\langle \left\{atr_{k}\right\},\left\{ev_{j}\right\}\right\rangle ,mv_{i}\in MV,ev_{j}\in (V\cup E^{eo=false}\cup MV\cup ME^{eo=false})$, где $mv_{i}$ – вершина метаграфа; $atr_{k}$ – атрибут, $ev_{j}$ – элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

Таким образом, метавершина в дополнение к свойствам вершины включает вложенный фрагмент метаграфа. При этом ребра и метаребра этого фрагмента могут быть только ненаправленными, $eo=false$.

Метаребро метаграфа:

$me_{i}=\left\langle v_{S},v_{E},eo,\left\{atr_{k}\right\},\left\{ev_{j}\right\}\right\rangle ,e_{i}\in E,eo=true|false,ev_{j}\in (V\cup E^{eo=true}\cup MV\cup ME^{eo=true})$, где $me_{i}$ – метаребро метаграфа; $v_{S}$ – исходная вершина (метавершина) ребра; $v_{E}$ – конечная вершина (метавершина) ребра; $eo$ – признак направленности метаребра ($eo=true$ – направленное метаребро, $eo=false$ – ненаправленное метаребро); $atr_{k}$ – атрибут; $ev_{j}$ – элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

Таким образом, метаребро в дополнение к свойствам ребра включает вложенный фрагмент метаграфа. При этом ребра и метаребра этого фрагмента могут быть только направленными, $eo=true$.

Определения метавершины и метаребра являются рекурсивными, так как элементы $ev_{j}$ могут быть, в свою очередь, метавершинами и метаребрами. Метавершина является формализмом описания данных, а метаребро – формализмом описания процессов.

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

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

Пример описания метаграфа показан на рис. 1. Данный метаграф содержит вершины, метавершины и ребра. На рис. 1 показаны три метавершины: $mv_{1}$, $mv_{2}$ и $mv_{3}$. Метавершина $mv_{1}$ включает вершины $v_{1},v_{2},v_{3}$ и связывающие их ребра $e_{1},e_{2},e_{3}$. Метавершина $mv_{2}$ включает вершины $v_{4},v_{5}$ и связывающее их ребро $e_{6}$. Ребра $e_{4},e_{5}$ являются примерами ребер, соединяющих вершины $v_{2}$-$v_{4}$ и $v_{3}$-$v_{5}$, включенные в различные метавершины $mv_{1}$ и $mv_{2}$. Ребро $e_{7}$ является примером ребра, соединяющего метавершины $mv_{1}$ и $mv_{2}$. Ребро $e_{8}$ является примером ребра, соединяющего вершину $v_{2}$ и метавершину $mv_{2}$. Метавершина $mv_{3}$ включает метавершину $mv_{2}$, вершины $v_{2},v_{3}$ и ребро $e_{2}$ из метавершины $mv_{1}$ а также ребра $e_{4},e_{5},e_{8}$, что показывает холоническую структуру метаграфа.

Рис. 1 - На изображении показан пример описания метаграфа

Пример описания метаребра метаграфа представлен на рис. 2. Метаребро содержит метавершины $v_{S},...v_{i},...v_{E}$ и связывающие их ребра. Исходная метавершина содержит фрагмент метаграфа. В процессе преобразования исходной метавершины $v_{S}$ в конечную метавершину $v_{E}$ происходит дополнение содержимого метавершины, добавляются новые вершины, связи, вложенные метавершины.

Рис. 2 - Пример описания метаребра метаграфа

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

Сравнение метаграфовой модели с моделью гиперграфа

В этом разделе мы рассмотрим модель гиперграфа и сравним ее с метаграфовой моделью.

Рассмотрим формализованную модель гиперграфа в соответствии с [9]:

$HG=\left\langle V,HE\right\rangle ,he_{j}=\left\{v_{i}\right\},v_{i}\in V,he_{j}\in HE$, где $HG$ – гиперграф; $V$ – множество вершин гиперграфа; $HE$ – множество непустых подмножеств $V$, называемых гиперребрами; $v_{i}$ – вершина гиперграфа; $he_{j}$ – гиперребро гиперграфа.

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

Пример описания гиперграфа показан на рис. 3. Данный ненаправленный гиперграф включает три гиперребра: $he_{1},he_{2},he_{3}$. Гиперребро $he_{1}$ включает вершины $v_{1},v_{2},v_{4},v_{5}$. Гиперребро $he_{2}$ включает вершины $v_{2}$ и $v_{3}$. Гиперребро $he_{3}$ включает вершины $v_{4}$ и $v_{5}$. Гиперребра $he_{1}$ и $he_{2}$ имеют общую вершину $v_{2}$. Все вершины гиперребра $he_{3}$ также являются вершинами гиперребра $he_{1}$.

Рис.3 - Пример описания ненаправленного гиперграфа

Сравнивая рис. 1 и 3, можно отметить некоторые сходства между метавершиной и гиперребром. Но эти сходства достаточно условны. Если гиперребро гиперграфа может включать только вершины, то метавершина метаграфа может включать как вершины (метавершины), так и ребра (метаребра).

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

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

Необходимо отметить, что некоторые современные СУБД реализуют концепцию иерархического гиперграфа, который можно определить следующим образом:

$HHG=\left\langle V,HE\right\rangle ,he_{j}=\left\{v_{i}\right\},v_{i}\in V\cup HE,he_{j}\in V\cup HE$, где $HHG$ – иерархический гиперграф; $V$ – множество вершин гиперграфа; $HE$ – множество гиперребер гиперграфа; $v_{i}$ – вершина гиперграфа; $he_{j}$ – гиперребро гиперграфа.

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

Вершина может рассматриваться как частный случай «пустого» гиперребра. Гиперребро рассматривается как множество (коллекция) вершин, которое в случае направленного гиперграфа может быть упорядоченным.

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

Сравнение метаграфовой модели с моделью гиперсети

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

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

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

Гиперсетевая модель (по Дж. Джонсону) предложена профессором Джеффри Джонсоном. Несмотря на то, что основная монография профессора Дж. Джонсона [10] вышла в 2013 году (значительно позже работ профессора В.К. Попкова), необходимо отметить, что профессор Дж. Джонсон в этой монографии ссылается на свои работы еще 1970-х годов, в том числе, опираясь на еще более ранние статьи своего учителя профессора Рональда Аткина. В качестве математического аппарата используются в основном методы топологии (симплициальные комплексы, топологические пространства), метод Q-анализа (предложенный профессором Рональдом Аткиным). Модель применяется в основном в области социологии.

Рассмотрим определение абстрактной гиперсети (по В.К. Попкову) в соответствии с [11].

Пусть даны гиперграфы $PS\equiv WS_{0},WS_{1},WS_{2},...WS_{k}$. Гиперграф $PS$ или $WS_{0}$ называется первичной сетью. Гиперграф $WS_{i}$ называется вторичной сетью i-го порядка.

Пусть также задана последовательность отображений между сетями различных уровней $\left\{\Phi _{i}\right\}:WS_{k}--^{\Phi _{K}}\to WS_{K-1}--^{\Phi _{K-1}}\to ...WS_{1}--^{\Phi _{1}}\to PS$.

Тогда иерархическую абстрактную гиперсеть порядка K можно определить как $AS^{K}=\left\langle PS,WS_{1},...,WS_{K};\Phi _{1},...,\Phi _{K}\right\rangle$.

Эмерджентность в гиперсети (по В.К. Попкову) возникает при переходе между уровнями за счет использования отображений между «слоями» гиперребер.

Эмерджентность в гиперсети (по Дж. Джонсону) возникает при переходе между уровнями за счет возникновения гиперсимплексов.

В монографии [10] профессор Дж. Джонсон дает формальное определение гиперсимплекса через достаточно сложную цепочку определений, которые мы здесь не приводим. В статье [3] профессор К.В. Анохин приводит удачное неформальное определение гиперсимплекса: «основание гиперсимплекса содержит множество элементов одного уровня, а его вершина образуется описанием их отношений и приобретает интегральные свойства, делающие ее элементом сети более высокого уровня». Интересным является факт, что в своей модели когнитома [3], профессор К.В. Анохин использует модель гиперсети (по Дж. Джонсону).

Примеры гиперсетей по В.К. Попкову и по Дж. Джонсону представлены на рис. 4 и 5.

Рис. 4 - Пример гиперсети (по В.К. Попкову)

Рис. 5 - Пример гиперсети (по Дж. Джонсону)

На рис. 5 первичная сеть PS образуется вершинами гиперребер $he_{1}$ и $he_{2}$. Первый уровень вторичной сети образуется вершинами гиперребра $he_{3}$. Штрихпунктирной линией выделен гиперсимплекс $hv_{3}-hv_{4}-hv_{5}$.

Таким образом, в обеих моделях гиперсеть является конструкцией, содержащей слои гиперграфов, при этом только соседние слои могут быть «сцеплены». Разница между моделями состоит в том, как «сцепляются» слои. В модели В.К. Попкова «сцепление» производится за счет отображений Ф. В модели Дж. Джонсона «сцепление» производится за счет использования гиперсимплексов.

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

Рассмотрим отличия между моделью гиперсети и моделью метаграфа.

В соответствии с определением гиперсеть является «послойным» описанием графов. Предполагается, что слои-гиперграфы идут последовательно и имеют регулярную структуру. Метаграф позволяет с помощью метавершин группировать произвольные элементы, наличие регулярных уровней не обязательно, что делает подход метаграфов более гибким. Фактически, каждый гиперсимплекс может быть представлен отдельной метавершиной.

Гиперсеть состоит из разнородных элементов (гиперграфов и отображений по В.К. Попкову, гиперграфов и гиперсимплексов по Дж. Джонсону). Метаграф позволяет с помощью метавершин обеспечивать связь как между элементами одного уровня, так и между элементами различных уровней (при этом, не обязательно соседних). Это делает метаграфовый подход более унифицированным и удобным в описании, так как для описания используются не разнородные структуры (гиперграфы и отображения), а только метавершины (и связи, как элементы метавершин). Метаграфовый подход позволяет рассматривать сеть не только в виде «горизонтальных» слоев, но и в виде «вертикальных» колонок.

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

По результатам сравнения моделей можно сделать следующие выводы:

• Модель гиперсети фактически представляет собой попытку описания «сверху вниз» (по уровням), а модель метаграфа попытку описания «снизу вверх» (путем «выращивания» метавершин из более простых элементов).
• Модель метаграфа является более простой в описании, так как состоит из однородных элементов (метавершин и связей, как элементов метавершин).
• Модель метаграфа является более гибкой, так как не требует регулярности уровней. Произвольный подграф может быть превращен в метавершину.

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

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

Модель многоуровневой сети и ее сравнение с другими моделями

Модель многоуровневой сети представляет собой попытку исследователей-математиков перейти от сложных сетей в трактовке 1 к сложным сетям в трактовке 2. Детальный обзор модели приведен в работах [4, 12, 13].

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

В работе [13] дается следующее формализованное описание многоуровневой сети:

$MN=\left\langle \left\{G_{1},...,G_{L}\right\},\left\{E_{ij}\subset X_{i}\times X_{j},i,j,\in \left\{1,...,L\right\},i\neq j\right\}\right\langle ,G_{K}=\left\langle X_{K},E_{K}\right\rangle$

В приведенной формуле $\left\{G_{1},...,G_{L}\right\}$ – семейство плоских графов $G_{K}=\left\langle X_{K},E_{K}\right\rangle$, где $X_{K}$ – множество вершин графа $G_{K},E_{K}$ – множество ребер графа $G_{K}$.

Множество $\left\{G_{1},...,G_{L}\right\}$ называется уровнями в многоуровневой сети MN.

Граф GK может быть направленным или ненаправленным, взвешенным или невзвешенным, а также мультиграфом.

Каждый элемент $E_{ij}\subset X_{i}\times X_{j},i,j,\in \left\{1,...,L\right\},i\neq j$ является множеством связей между вершинами графов уровней i и j. Условие $i\neq j$ говорит о запрете циклических связей на одном уровне, связи могут быть только между элементами соседних уровней.

Пример многоуровневой сети представлен на рис. 6. Сеть содержит три уровня $G_{1},G_{2},G_{3}$. В данном примере каждый уровень является плоским ненаправленным графом. Ребра графов $E_{K}$ показаны сплошными линиями. Примеры связей $E_{ij}$ между уровнями показаны пунктирными линиями.

Рис. 6 - Пример многоуровневой сети

При условии $L=1$ многоуровневая сеть превращается в обычную одноуровневую сеть.

В работе [4] для многоуровневой сети MN вводится операция проекции на одноуровневую сеть:

$proj(MN)=\left\langle X^{proj},E^{proj}\right\rangle$

$X^{proj}=\bigcup _{k=1}^{L}X_{k},X_{k}\subset G_{k}$

$E^{proj}=(\bigcup _{k=1}^{L}E_{k})\cup (\bigcup _{1\leq i\neq j\leq L}),E_{k}\subset G_{k}$

Проекция proj(MN) многоуровневой сети MN является одноуровневой сетью (плоским графом). Множеством вершин графа $X^{proj}$ является объединение множеств вершин графов $G_{k}$, соответствующих уровням сети. Множеством ребер графа $E^{proj}$ является объединение множеств ребер между вершинами на соответствующих уровнях сети $E_{K}$ и связей между уровнями $E_{ij}$.

В работе [4] также отмечается, что частным случаем многоуровневых сетей являются мультиплексные сети (англ. multiplex network). В этом случае связи между слоями разрешены только для одноименных вершин графов (вершин с одинаковыми индексами). Формально это ограничение может быть записано следующим образом:

$E_{ij}=\left\{\left\langle x_{k}^{i},x_{k}^{j}\right\rangle ,x_{k}\in X\right\},i,j\in \left\{1,...,L\right\},i\neq j$

Это означает что связь в мультиплексной сети может быть установлена только между одноименными элементами $x_{k}$ (у обоих элементов одинаковый индекс k) расположенными на соседних уровнях i и j.

В качестве примера рассмотрим рисунок 6. Например, связь $X_{2}-X_{2}$ между уровнями $G_{1}-G_{2}$ не нарушает условия мультиплексности сети, так как соединены одноименные элементы (с одинаковыми индексами). Но связь $X_{1}-X_{4}$ между уровнями $G_{1}-G_{2}$ нарушает условие мультиплексности сети, так как соединены разноименные элементы (с различными индексами).

Сравним модель многоуровневой сети и гиперсетевую модель. Как и гиперсетевая модель, модель многоуровневой сети является послойной.

Если в гиперсетевой модели на каждом уровне применяются гиперграфы, то в многоуровневой сети уровнем является более простая модель – обычный плоский граф. Связи между уровнями $E_{ij}$ можно рассматривать как частный случай отображения Ф в гиперсети на основе модели В.К. Попкова.

Таким образом, модель многоуровневой сети можно считать частным упрощенным случаем гиперсетевой модели в интерпретации В.К. Попкова.

Если каждый слой многоуровневой сети считать метавершиной, то данную модель можно рассматривать как частный случай метаграфовой модели.

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

Преобразование метаграфовой модели на основе мультиагентного подхода

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

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

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

Определим агент-функцию следующим образом:

$ag^{F}=\left\langle MG_{IN},MG_{OUT},AST\right\rangle$, где $ag^{F}$ – агент-функция; $MG_{IN}$ – метаграф, который выполняет роль входного параметра агента-функции; $MG_{OUT}$ – метаграф, который выполняет роль выходного параметра агента-функции; $AST$ – абстрактное синтаксическое дерево агента-функции, которое может быть представлено в виде метаграфа.

Определим метаграфовый агент следующим образом:

$ag^{M}=\left\langle MG_{D},R,AG^{ST}\right\rangle ,R=\left\{r_{j}\right\}$, где $ag^{M}$ – метаграфовый агент; $MG_{D}$ – метаграф данных и знаний, на основе которого выполняются правила агента; $R$ – набор правил (множество правил $rj$); $AG^{ST}$ – стартовое условие выполнения агента (фрагмент метаграфа, который используется для стартовой проверки правил, или стартовое правило).

Структура правила метаграфового агента:

$r_{i}:MG_{j}\to OP^{MG}$, где $r_{i}$ – правило; $MG_{j}$ – фрагмент метаграфа, на основе которого выполняется правило; $OP^{MG}$ – множество операций, выполняемых над метаграфом.

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

Отметим, что правила метаграфового агента можно разделить на замкнутые и разомкнутые.

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

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

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

Пример представления метаграфового агента в виде фрагмента метаграфа приведен на рис. 7.

Рис. 7 - Представление метаграфового агента в виде фрагмента метаграфа

Метаграфовый агент представлен в виде метавершины метаграфа. В соответствии с определением, он связан с метаграфом $MG_{1}$, на основе которого выполняются правила агента. Данная связь показана с помощью ребра $e_{4}$.

Метаграфовый агент содержит множество вложенных метавершин, соответствующих правилам (правило 1 – правило N). Каждая метавершина правила содержит вершины антецедента и консеквента. В данном примере с антецедентом правила связана метавершина данных $mv_{2}$, что показано ребром $e_{2}$, а с консеквентом правила связана метавершина данных $mv_{3}$, что показано ребром $e_{3}$. Условия срабатывания антецедента и множество действий консеквента задаются в виде атрибутов соответствующих вершин.

Стартовое условие выполнения агента задается с помощью атрибута «start=true». Если стартовое условие задается в виде стартового правила, то данным атрибутом помечается метавершина соответствующего правила, в данном примере это правило 1. Если стартовое условие задается в виде стартового фрагмента метаграфа, который используется для стартовой проверки правил, то атрибутом «start=true» помечается ребро, которое связывает стартовый фрагмент метаграфа с метавершиной агента, в данном примере это ребро $e_{1}$.

В зависимости от условий, метаграфовый агент может решать следующие задачи:

• первичное развертывание, создание системы агентов более низкого уровня;
• изменение системы нижнего уровня (изменение внутренней структуры агентов, изменение связей между агентами, удаление агентов).

Если набор метаграфовых агентов привязан к фрагменту метаграфа (метавершине), то такую структуру будем называть «активным метаграфом». Активный метаграф содержит как метаграфовое описание данных, так и правила обработки данных, заданные в виде агентов.

Подобные структуры часто используются в информатике. В качестве примера можно рассмотреть класс объектно-ориентированного языка программирования, который содержит данные и методы их обработки. Другим примером является таблица реляционной СУБД с привязанным набором триггеров для обработки записей таблицы. Активный метаграф позволяет комбинировать данные и средства их обработки для подхода на основе сложных сетей.

Пример описания структуры нейронной сети на основе метагрАфового подхода

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

Описание структуры нейронной сети с помощью метаграфов

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

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

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

Рис. 8 - Структура метаграфовых агентов для действий с нейронной сетью

Агент создания нейросети ($ag^{MC}$) реализует правила создания начальной топологии нейросети. Данный агент содержит как правила создания отдельных нейронов, так и правила соединения нейронов в нейросеть. Данный агент, в частности, создает абстрактные синтаксические деревья агентов-функций $\phi ^{F}$ и $\psi ^{F}$.

Агент изменения нейросети ($ag^{MO}$) содержит правила изменения топологии сети в процессе работы. Это особенно важно для сетей с изменяемой топологией таких, как SOINN.

Агент обучения нейросети ($ag^{ML}$) реализует один из алгоритмов обучения. При этом в результате обучения измененные значения весов записываются в метаграфовое представление нейросети. Возможна реализация нескольких алгоритмов обучения с использованием различных наборов правил для агента $ag^{ML}$.

Агент запуска нейросети ($ag^{MR}$) реализует запуск и работу обученной нейросети в штатном режиме.

Отметим, что агенты могут работать как независимо, так и совместно. При обучении сети SOINN агент $ag^{ML}$ может вызывать правила агента $ag^{MO}$ для изменения топологии в процессе обучения.

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

Описание модели персептрона на основе метаграфового подхода

Описание персептрона с использованием метаграфового подхода показано на рис. 9.

Рис. 9 - Описание персептрона с использованием метаграфового подхода

В соответствии с моделью Ф. Розенблатта [14], классический персептрон состоит из S, A и R элементов.

Слой сенсоров (S) представляет собой набор входных сигналов. Ассоциативный слой (А) включает набор промежуточных элементов, которые активизируются, если одновременно активизируется некоторый набор (образ) входных сигналов. Сумматор (R) активизируется, если одновременно активизируется некоторый набор А-элементов.

В соответствии с обозначениями, принятыми в [15], значение сигнала на А-элементе может быть представлено в виде предиката $\phi (S)$, а значение сигнала на сумматоре в виде предиката $\psi (A,W)$. Под предикатом в [15] понимается функция, принимающая только два значения «0» и «1».

В зависимости от конкретного вида персептрона, вид предикатов $\phi (S)$ и $\psi (A,W)$ может быть различным. Как правило, с помощью предиката $\phi (S)$ проверяется, что суммарный входной сигнал от сенсоров не превышает некоторый порог. Также с помощью предиката $\psi (A,W)$ проверяется, что взвешенная сумма от А-элементов не превышает некоторого порога, где W – вектор весов.

В нашем случае конкретный вид предикатов не важен, важно то, что $\phi (S)$ и $\psi (A,W)$ являются обычными функциональными зависимостями, которые на программном уровне могут быть представлены в виде абстрактного синтаксического дерева.

С точки зрения метаграфов, описание персептрона представляет собой метавершину (показана на рис. 9 в виде двойного прямоугольника). Входные сигналы S, промежуточные сигналы A’ и выходной сигнал R’ (пассивные данные) показаны на рис. 9 в виде окружностей. Агенты-функции, соответствующие А-элементам и R-элементам, показаны на рис. 9 в виде прямоугольников.

Представим рассмотренную структуру персептрона в виде комбинации агентов-функций, что показано на рис. 10.

Рис. 10 - Представление персептрона в виде агентов-функций

Предикаты $\phi (S)$ и $\psi (A,W)$ представлены в виде метавершин (показаны на рис. 10 в виде пунктирных овалов). На основе рис. 10 можно описать персептрон в виде комбинации агентов-функций:

$\phi ^{F}=\left\langle S,A',AST^{\phi }\right\rangle$

$\psi ^{F}=\left\langle \left\langle \left\{\phi ^{F}\right\},W\right\rangle ,R',AST^{\psi }\right\rangle$

А-элемент может быть представлен в виде агента-функции $\phi ^{F}$. Входным параметром является вектор значений S, выходным параметром вектор значений A’.

Описание персептрона эквивалентно описанию агента-функции $\psi ^{F}$. Входным параметром является метаграфовое представление кортежа, содержащего описание А-элементов в виде агентов-функций $\phi ^{F}$ и вектора W. Выходным параметром является значение выходного сигнала R’.

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

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

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

Использование моделей сложных графов в существующих программных продуктах

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

Neo4j

По состоянию на январь 2019 года СУБД Neo4j [16] занимает первое место в рейтинге используемости графовых СУБД [17].

Платформа Neo4j предназначена как для транзакционной обработки графов, так и для графовой аналитики. На русском языке выпущена книга по работе с данной СУБД [18]. СУБД Neo4j обладает развитым языком запросов «Cypher».

Основной моделью данных в Neo4j является «граф свойств» (англ. «Property Graph» или «Labeled-Property Graph»), который обладает следующими характеристиками [19]:

1. Граф свойств является плоским графом, содержащим вершины и ребра (связи).
2. Связи могут быть ненаправленными или направленными. Две вершины могут быть соединены несколькими связями, то есть граф свойств является мультиграфом.
3. К вершинам, а также к связям, могут быть привязаны свойства (англ. «properties») в формате «ключ-значение». Поскольку свойства фактически являются переменными с заданными значениями, то можно говорить о том, что присвоенное значение определяет тип данных свойства.
4. К вершинам, а также к связям, могут быть привязаны метки (англ. «labels»), которые обычно рассматриваются как система тэгов. Таким образом, в графе свойств вершины и связи могут быть помечены тэгами.

Если модель графа свойств соответствует характеристикам 1-3, то ее называют «Property Graph», а если характеристикам 1-4, то ее называют «Labeled-Property Graph». Данное различие не является существенным, так как метки могут быть смоделированы в виде свойств с отсутствующими значениями, то есть характеристика 4 может быть получена из характеристики 3.

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

В документации Neo4j [19] выражена позиция разработчиков СУБД по отношению к гиперграфам. Разработчики Neo4j признают, что использование гиперребер может сделать описание графовой модели более компактным. При этом они приводят пример, в котором гиперребро представляется в виде комбинации обычных ребер, снабженных атрибутами. Из этого примера авторы делают вывод о том, что граф свойств по сравнению с гиперграфом позволяет описывать информацию более детально. С точки зрения плоских графов это справедливо, так как невозможно снабдить различные фрагменты гиперребра различными атрибутами.

Но, оставаясь в парадигме плоских графов, разработчики Neo4j рассматривают гиперребро гиперграфа не как возникновение эмерджентности, а как сложную и потому «ненужную» связь в плоском графе. Подобный подход затрудняет моделирование сложных графов с эмерджентностью в СУБД Neo4j.

HyperGraphDB

В качестве предпосылки для создания проекта HyperGraphDB [20], разработчики называют требования к хранению и обработке сложных графовых моделей, возникающие в системах искусственного интеллекта. В частности, речь идет о проекте в области искусственного интеллекта OpenCog.

Модель данных HyperGraphDB детально описана в [21]. Как следует из названия, в HyperGraphDB в качестве модели данных используется модель, основанная на направленных иерархических гиперграфах. Рассмотрим характеристики модели данных в соответствии с [21]:

1. В HyperGraphDB вершина или гиперребро называются «атомами» (англ. «atoms»).
2. Каждому атому ставится в соответствие «целевое множество» (англ. «target set») связанных (вложенных) элементов. Поскольку используются направленные гиперграфы, то целевое множество упорядочено.
3. Если целевое множество является пустым, то такой атом соответствует вершине гиперграфа и называется «узлом» (англ. «node»).
4. Если целевое множество не является пустым, то такой атом соответствует гиперребру гиперграфа и называется «связью» (англ. «link»).
5. Каждый атом является ключом в паре «ключ-значение». Каждому атому ставится в соответствие значение. Для значения задается тип данных.

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

Интересной особенностью HyperGraphDB является наличие встроенного в СУБД языка Prolog (диалект TuProlog). Интеграция модели данных с интерпретатором Prolog реализована следующим образом:

1. Модель данных HyperGraphDB (множество атомов) рассматривается интерпретатором Prolog как собственная база знаний.
2. Правила вывода Prolog, хранящиеся в СУБД, позволяют осуществлять запросы к базе знаний.

Таким образом, СУБД HyperGraphDB позволяет моделировать сложные графы с эмерджентностью на основе модели иерархических гиперграфов. Для обработки данных используется язык Prolog.

GRAKN.AI

Проект GRAKN.AI [22] на сегодняшний день является одной из наиболее интересных и перспективных платформ для обработки сложных графов. Авторы утверждают, что моделью данных в их платформе являются графы знаний (англ. «knowledge graphs»).

Модель знаний GRAKN.AI [23] представлена в виде схемы на рис. 11. Основным понятием модели знаний является понятие концепта (англ. «Concept»). К концептам относятся типы данных (англ. «Type»), конкретные объекты данных (англ. «Thing», необходимо отметить, что этот термин взят из моделей описания онтологий), и правила обработки данных (англ. «Rule»).

Рис. 11 - Модель знаний системы GRAKN.AI

Для моделирования знаний в GRAKN.AI используется концепция вещь-свойство-отношение. Поэтому к объектам данных относятся вещь или сущность (англ. «Entity»), свойство или атрибут (англ. «Attribute») и отношение (англ. «Relationship»). К типам данных относятся соответствующие типы данных «EntityType», «AttributeType» и «RelationshipType».

Все виды концептов являются элементами графа знаний и участвуют в построении информационной модели. В GRAKN.AI используется традиционный для СУБД подход, когда сначала создается схема данных, а затем она заполняется конкретными объектами. В качестве языка описания данных используется язык «Graql», который является как языком описания данных (DDL, Data Definition Language), так и языком манипулирования данными (DML, Data Manipulation Language).

Работа со сложными графами в GRAKN.AI [24] напоминает подход, используемый в HyperGraphDB. В системе GRAKN.AI используется модель иерархических гиперграфов. Иерархичность заключается в том, что в модели данных GRAKN.AI гиперребро рассматривается как вершина и может быть соединено с другими гиперребрами.

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

Прогнозируемое развитие рынка графовых СУБД

В обзоре [25] отмечается, что графовые СУБД становятся основной технологией в управлении данными для предприятий и находят применение почти в каждом секторе промышленности. Технология графовых баз данных предлагает ряд преимуществ для решения больших и сложных задач, связанных с данными, по сравнению с другими решениями баз данных.

На рис. 12 приведен график популярности СУБД в зависимости от модели данных на основании обзора [26]. Ось абсцисс является временной шкалой, по оси ординат отложена популярность в условных единицах.

Популярность СУБД в зависимости от модели данных, по годам

График показывает, что примерно с начала 2014 года, популярность графовых СУБД резко увеличивается. Интерес к графовым СУБД намного превышает интерес к СУБД на основе других моделей данных.

На сегодняшний день существует два основных прогноза увеличения объема рынка графовых СУБД и систем на их основе:

1. По оценке компании Zion Market Research [27] рынок графовых СУБД увеличится с 39 млн. долл. в 2017 году до 445 млн. долл. в 2024 году. При этом CAGR (compound annual growth rate) в диапазоне между 2018 и 2024 будет составлять 41%.
2. По оценке, приведенной в источнике [25], рынок графовых СУБД (с учетом онлайн-сервисов и приложений на основе графовых СУБД) увеличится с 821 млн. долл. в 2018 году до 2,4 млрд. долл. в 2023 году. При этом CAGR за указанный период будет составлять 24%.

Таким образом, оба прогноза говорят о значительном увеличении объема рынка графовых СУБД.

На сегодняшний день большинство графовых СУБД использует плоскую графовую модель данных на основе «графа свойств». Наиболее известной СУБД этого класса является Neo4j. Некоторые СУБД (например, HyperGraphDB и GRAKN.AI) позволяет моделировать сложные графы с эмерджентностью на основе модели иерархических гиперграфов. Для таких проектов также характерно внедрение Prolog-подобных механизмов обратного логического вывода.

С учетом значительного роста рынка графовых СУБД можно прогнозировать также увеличение интереса к графовым СУБД на основе сложных графовых моделей.

Список источников

1. Евин И.А. Введение в теорию сложных сетей //Компьютерные исследования и моделирование. 2010, Том 2, №2, с. 121-141.
2. Кузнецов О.П., Жилякова Л.Ю. Сложные сети и когнитивные науки // Нейроинформатика-2015. XVII Всероссийская научно-техническая конференция. Сборник научных трудов. Ч. 1. М.: МИФИ. 2015. С. 18.
3. Анохин К.В. Когнитом: гиперсетевая модель мозга // Нейроинформатика-2015. XVII Всероссийская научно-техническая конференция. Сборник научных трудов. Ч. 1. М.: МИФИ. 2015. С. 14-15.
4. Chapela V., Regino Criado, Santiago Moral, Miguel Romance. Intentional risk management through complex networks analysis. – Springer, 2015: SpringerBriefs in optimization.
5. Basu A., Robert W. Blanning. Metagraphs and their applications. – New York: Springer, 2007.
6. Черненький В.М., Гапанюк Ю.Е., Ревунков Г.И., Терехов В.И., Каганов Ю.Т. Метаграфовый подход для описания гибридных интеллектуальных информационных систем. Прикладная информатика. 2017. № 3 (69). Том 12. С. 57–79.
7. Черненький В.М., Терехов В.И., Гапанюк Ю.Е. Представление сложных сетей на основе метаграфов // Нейроинформатика-2016. XVIII Всероссийская научно-техническая конференция. Сборник научных трудов. Ч. 1. М.: НИЯУ МИФИ, 2016. C. 173-178.
8. Самохвалов Э.Н., Ревунков Г.И., Гапанюк Ю.Е. Использование метаграфов для описания семантики и прагматики информационных систем. Вестник МГТУ им. Н.Э. Баумана. Сер. «Приборостроение». 2015. Выпуск №1. С. 83-99.
9. Voloshin V. I. Introduction to graph and hypergraph theory. – New York: Nova Science Publishers, 2009.
10. Johnson J. Hypernetworks in the science of complex systems. – London, Hackensack NJ: Imperial College Press, 2013.
11. Попков В.К. Математические модели связности. Новосибирск: ИВМиМГ СО РАН, 2006.
12. Aleta A., Moreno Y. Multilayer Networks in a Nutshell. Режим доступа: https://arxiv.org/pdf/1804.03488.pdf (дата обращения 25.01.2019)
13. Boccaletti S., Bianconi G., Criado R., del Genio C. I., Gómez-Gardeñes J., Romance M., Sendiña-Nadal I., Wang Z., Zanin M. The structure and dynamics of multilayer networks // Physics Reports. ‒ 2014. ‒ T. 544. № 1. C. 1–122.
14. Розенблатт Ф. Принципы нейромеханики. Перцептроны и теория механизмов мозга. – Москва: Мир, 1965.
15. Минский М., Пейперт. С. Персептроны. – Москва: Мир, 1971.
16. Официальный сайт СУБД Neo4j. Режим доступа: https://neo4j.com (дата обращения 25.01.2019)
17. Рейтинг используемости графовых СУБД. Режим доступа: https://db-engines.com/en/ranking/graph+dbms (дата обращения 25.01.2019)
18. Робинсон Я., Вебер Дж., Эифрем Э. Графовые базы данных. Новые возможности для работы со связанными данными. – ДМК Пресс, 2016.
19. Описание модели данных Neo4j. Режим доступа: https://neo4j.com/blog/other-graph-database-technologies (дата обращения 25.01.2019)
20. Официальный сайт СУБД HyperGraphDB. Режим доступа: http://www.hypergraphdb.org (дата обращения 25.01.2019)
21. Borislav Iordanov, HyperGraphDB: A Generalized Graph Database. // Web-age information management / Heng Tao Shen. – Berlin: Springer, 2010. C. 25–36.
22. Официальный сайт GRAKN.AI. Режим доступа: https://grakn.ai (дата обращения 25.01.2019)
23. Модель знаний системы GRAKN.AI. Режим доступа: http://dev.grakn.ai/docs/concept-api/overview (дата обращения 25.01.2019)
24. Моделирование знаний в GRAKN.AI с использованием гиперграфов. Режим доступа: https://blog.grakn.ai/modelling-data-with-hypergraphs-edff1e12edf0 (дата обращения 25.01.2019)
25. Graph Database Market. Режим доступа: https://www.marketsandmarkets.com/PressReleases/graph-database.asp (дата обращения 25.01.2019)
26. DBMS popularity broken down by database model. Режим доступа: https://db-engines.com/en/ranking_categories (дата обращения 25.01.2019)
27. Global Graph Database Market. Режим доступа: https://www.zionmarketresearch.com/news/graph-database-market (дата обращения 25.01.2019)