Метаграфы в математике — обобщение концепций графовых структур. В метаграфе есть и элементы и орграфов, и гиперграфов , сам метаграф процесса выстраивается на основе иерархического графа. Формально, метаграф определяется множество <V,MV, E, ME>, где V — множество вершин, MV — множество метавершин, E — множество ребер, ME — множество метаребер.

Метаграфовая модель А. Базу и Р. Блэннинга

Исторически монография А. Базу и Р. Блэннинга была первым источником, в котором появился термин «метаграф». В монографии даются следующие определения, характеризующие метаграфовую модель.

Порождающее множество метаграфа — это множество переменных, встречающихся в ребрах метаграфа: ${\displaystyle X=\{x_{1},x_{2},...,x_{n}\}}$ .

Ребро метаграфа ${\displaystyle e=\langle V_{e},W_{e}\rangle \in E}$ (где ${\displaystyle E}$ — множество ребер) содержит входную вершину' (invertex)' ${\displaystyle V_{e}\subset X}$ и выходную вершину (outvertex) ${\displaystyle W_{e}\subset X}$ . Входная и выходная вершины могут содержать произвольное количество элементов. Различные элементы, принадлежащие входной (выходной) вершине, называются соответственно совходами ( совыходами ).

Тогда метаграф ${\displaystyle S=\langle X,E\rangle }$ — это графовая конструкция, определяемая порождающим множеством ${\displaystyle X}$ и множеством ребер ${\displaystyle E}$ , при этом множество ребер определено на том же порождающем множестве.

Простым путем ${\displaystyle h(x,y)}$ из элемента x в элемент y это последовательность ребер ${\displaystyle \langle e_{1},e_{2},...,e_{n}\rangle }$ , такая что:

• ${\displaystyle x}$ является входной вершиной ${\displaystyle e_{1},x\in invertex(e_{1})}$ ;

• ${\displaystyle y}$ является выходной вершиной ${\displaystyle e_{n},y\in outvertex(e_{n})}$ ;

• для всех ${\displaystyle e_{i},i=1,...,n-1}$ выполняется условие: ${\displaystyle outvertex(e_{i})\cap invertex(e_{i+1})\neq \varnothing }$ , то есть путь из начальной вершины в конечную не прерывается.

В монографии приводится пример метаграфа, представленный на рис. 1, для которого приводится следующая теоретико-множественная интерпретация:

• ${\displaystyle S=<X,E>}$ ;

• ${\displaystyle X=\{Exp,Notes,Prof,Rev,Pri,Vol,Wage\}}$ ;

• ${\displaystyle E=<\{Pri,Vol\},\{Rev\}>,<\{Vol,Wage\},\{Exp\}>,<\{Rev,Exp\},\{Prof,Notes\}>,<\{Exp\},\{Notes\}>}$ .

Эмерджентность в модели А. Базу и Р. Блэннинга достигается за счет использования ребер. Понятие метавершины в данной модели отсутствует.

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

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

Отсутствие естественного механизма для описания сложных графовых структур данных привело к появлению расширений исходной модели А. Базу и Р. Блэннинга. В моделях появились новые элементы — метавершины и метаребра.

В работе появляется понятие метавершины. В этой работе даются следующие определения метаграфовой модели.

Метаграф — это тройка множеств вершин, метавершин и ребер соответственно: ${\displaystyle S=\langle V,W,E\rangle }$ , где ${\displaystyle V=\{\nu _{r}\}}$ — множество вершин метаграфа (порождающее множество); ${\displaystyle M=\{m_{q}\}}$ — множество метавершин метаграфа; ${\displaystyle E=\{e_{h}\}}$ — множество ребер метаграфа.

Метавершина метаграфа ${\displaystyle m_{q}=\{\nu _{r}\vert \nu _{r}\in V,r=1,...,N_{mq}\}}$ определяется как множество вершин ${\displaystyle \nu _{r}}$ , входящих в метавершину ${\displaystyle m_{q}}$ , где ${\displaystyle N_{mq}}$ — мощность множества.

Очень интересным следует считать следующее замечание авторов модели : «… если две или больше метавершин соответствуют одному и тому же множеству вершин, то такие вершины считаются одинаковыми и рассматривается только одна из таких метавершин». Назовем данное свойство модели свойством анти-аннотируемости, особенности которого будут рассмотрены далее.

Интересно, что для задания ребер, авторы модели вводят понятие узла метаграфа ${\displaystyle m\nu \in (V\cup M)}$ , принадлежащего объединённому множеству вершин и метавершин. Ребро определяется как ${\displaystyle e_{h}=\langle m\nu _{out},m\nu _{in}\rangle }$ , то есть характеризуется исходящим и входящим узлами метаграфа. Но использование понятия узла для создания иерархических метавершин авторами модели не предлагается.

Иерархическая метаграфовая модель с метавершинами и метаребрами

В работе появляется не только понятие метавершины, но также понятия метаребра и иерархии вершин.

Метаграф в модели определяется как ${\displaystyle S=\langle X,X_{M},E,E_{M}\rangle }$ , где ${\displaystyle X}$ — множество вершин метаграфа (порождающее множество); ${\displaystyle X_{M}}$ — множество метавершин метаграфа; ${\displaystyle E}$ — множество ребер метаграфа; ${\displaystyle E_{M}}$ — множество метаребер метаграфа, заданных на множестве ${\displaystyle X_{M}\cup X}$ .

Таким образом, под метаребром в данной модели понимается ребро, которое может соединять вершину и метавершину или две метавершины.

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

В данной модели множество вершин ${\displaystyle X}$ рассматривается как иерархическое, вводится индекс ${\displaystyle i}$ , определяющий уровень вложенности вершины.

Свойство анти-аннотируемости авторами модели не утверждается и не опровергается. При этом, приводимые в статье примеры неявно используют свойство анти-аннотируемости.

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

Аннотируемая метаграфовая модель

Аннотируемая метаграфовая модель расширяет идеи исходной модели А. Базу и Р. Блэннинга и идеи работы . Содержание работы на момент появления первой версии аннотируемой метаграфовой модели было нам неизвестно.

Аннотируемую метаграфовую модель предлагается использовать как средство для описания сложных сетей , как средство для описания семантики и прагматики информационных систем , как средство для описания гибридных интеллектуальных информационных систем . Определим метаграф следующим образом: ${\displaystyle S=\langle V,MV,E,ME\rangle }$ где ${\displaystyle MG}$ — метаграф; ${\displaystyle V}$ — множество вершин метаграфа; ${\displaystyle MV}$ — множество метавершин метаграфа; ${\displaystyle E}$ — множество ребер метаграфа; ${\displaystyle ME}$ — множество метаребер метаграфа.

Вершина метаграфа характеризуется множеством атрибутов : ${\displaystyle \nu _{i}=\{atr_{k}\},\nu _{i}\in V}$ где ${\displaystyle \nu _{i}}$ — вершина метаграфа; ${\displaystyle atr_{k}}$ — атрибут.

Ребро метаграфа характеризуется множеством атрибутов, исходной и конечной вершиной и признаком направленности: ${\displaystyle e_{i}=\langle \nu _{S},\nu _{E},eo,\{atr_{k}\}\rangle ,e_{i}\in E,eo=true\vert false,}$ где ${\displaystyle e_{i}}$ — ребро метаграфа; ${\displaystyle \nu _{S}}$ — исходная вершина (метавершина) ребра; ${\displaystyle \nu _{E}}$ — конечная вершина (метавершина) ребра; ${\displaystyle eo}$ — признак направленности ребра ( ${\displaystyle eo=true}$ — направленное ребро, ${\displaystyle eo=false}$ — ненаправленное ребро); ${\displaystyle atr_{k}}$ — атрибут.

Фрагмент метаграфа в общем виде может содержать произвольные вершины (метавершины) и ребра (метаребра): ${\displaystyle MG_{i}=\{e\nu _{j}\},e\nu _{j}\in (V\cup E\cup MV\cup ME)}$ , где ${\displaystyle MG_{i}}$ — фрагмент метаграфа; ${\displaystyle e\nu _{j}}$ — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

Метавершина метаграфа в дополнение к свойствам вершины включает вложенный фрагмент метаграфа: ${\displaystyle m\nu _{i}=\langle \{atr_{k}\},\{e\nu _{j}\}\rangle ,m\nu _{i}\in MV,e\nu _{j}\in (V\cup E\cup MV\cup ME)}$ , где ${\displaystyle m\nu _{i}}$ — вершина метаграфа; ${\displaystyle atr_{k}}$ — атрибут, ${\displaystyle e\nu _{j}}$ — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

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

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

Пример описания метаграфа показан на рис. 2. Данный метаграф содержит вершины, метавершины и ребра. На рис. 2 показаны три метавершины: mv1, mv2 и mv3 . Метавершина mv1 включает вершины v1, v2, v3 и связывающие их ребра e1, e2, e3 . Метавершина mv2 включает вершины v4, v5 и связывающее их ребро e6. Ребра e4, e5 являются примерами ребер, соединяющих вершины v2-v4 и v3-v5 , включенные в различные метавершины mv1 и mv2 . Ребро e7 является примером ребра, соединяющего метавершины mv1 и mv2 . Ребро e8 является примером ребра, соединяющего вершину v2 и метавершину mv2 . Метавершина mv3 включает метавершину mv2 , вершины v2, v3 и ребро e2 из метавершины mv1 а также ребра e4, e5, e8, что показывает холоническую структуру метаграфа.

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

Также, в предлагаемой нами модели, метавершина может включать как вершины, так и ребра.

Метаребро метаграфа в дополнение к свойствам ребра включает вложенный фрагмент метаграфа: ${\displaystyle me_{i}=\langle \nu _{S},\nu _{E},eo,\{atr_{k}\},\{e\nu _{j}\}\rangle ,e_{i}\in E,eo=true\vert false,e\nu _{j}\in (V\cup E\cup MV\cup ME)}$ где ${\displaystyle me_{i}}$ — метаребро метаграфа; ${\displaystyle \nu _{S}}$ — исходная вершина (метавершина) ребра; ${\displaystyle \nu _{E}}$ — конечная вершина (метавершина) ребра; ${\displaystyle eo}$ — признак направленности метаребра ( ${\displaystyle eo=true}$ — направленное метаребро, ${\displaystyle eo=false}$ — ненаправленное метаребро); ${\displaystyle atr_{k}}$ — атрибут; ${\displaystyle e\nu _{j}}$ — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

Пример описания метаребра метаграфа представлен на рис. 3. Метаребро содержит метавершины ${\displaystyle \nu _{S},\dots ,\nu _{i},\dots ,\nu _{E}}$ и связывающие их ребра. Исходная метавершина содержит фрагмент метаграфа. В процессе преобразования исходной

метавершины ${\displaystyle \nu _{S}}$ в конечную метавершину ${\displaystyle \nu _{E}}$ происходит дополнение содержимого метавершины, добавляются новые вершины, связи, вложенные метавершины.

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

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

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

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

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

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

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

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

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

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

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

Литература

• Chapela V., Regino Criado, Santiago Moral, Miguel Romance. Intentional risk management through complex networks analysis. — Springer, 2015: SpringerBriefs in optimization.

• Попков В. К. Математические модели связности. Новосибирск: ИВ-МиМГ СО РАН, 2006.

• Johnson J. Hypernetworks in the science of complex systems. — London, Hackensack NJ: Imperial College Press, 2013.

• Basu A., Robert W. Blanning. Metagraphs and their applications. — New York: Springer, 2007.

• Глоба, Л. С. Метаграфы как основа для представления и использования баз нечетких знаний / Л. С. Глоба, М. Ю. Терновой, Е. С. Штогрина // Открытые семантические технологии проектирования интеллектуальных систем = Open Semantic Technologies for Intelligent Systems (OSTIS-2015) : материалы V междунар. науч.-техн. конф. (Минск, 19-21 февраля 2015 года)/ редкол. : В. В. Голенков (отв. ред.) [и др.]. — Минск : БГУИР, 2015. — С. 237—240.

• Астанин С. В., Драгныш Н. В., Жуковская Н. К. Вложенные метаграфы как модели сложных объектов // Инженерный вестник Дона, 2012, № 4. URL: ivdon.ru/ru/magazine/archive/n4p2y2012/1434

• Самохвалов Э. Н., Ревунков Г. И., Гапанюк Ю. Е. Использование метаграфов для описания семантики и прагматики информационных систем. Вестник МГТУ им. Н. Э. Баумана. Сер. «Приборостроение». 2015. Выпуск № 1. С. 83-99.

• Черненький В. М., Терехов В. И., Гапанюк Ю. Е. Представление сложных сетей на основе метаграфов // Нейроинформатика-2016. XVIII Всероссийская научно-техническая конференция. Сборник научных трудов. Ч. 1. М.: НИЯУ МИФИ, 2016. C. 173—178.

• Черненький В. М., Гапанюк Ю. Е., Ревунков Г. И., Терехов В. И., Каганов Ю. Т. Метаграфовый подход для описания гибридных интеллектуальных информационных систем. Прикладная информатика. 2017. № 3 (69). Том 12. С. 57-79.

Примечания