Метаграф

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

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

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

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

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

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

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

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

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

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

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

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

• $S=<X,E>$;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метавершина метаграфа в дополнение к свойствам вершины включает вложенный фрагмент метаграфа: $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)$, где $m\nu _{i}$ — вершина метаграфа; $atr_{k}$ — атрибут, $e\nu _{j}$ — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

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

Рис.2. Метаграф в аннотируемой метаграфовой модели

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

Пример описания метаграфа показан на рис. 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, что показывает холоническую структуру метаграфа.

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

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

Метаребро метаграфа в дополнение к свойствам ребра включает вложенный фрагмент метаграфа: $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)$ где $me_{i}$ — метаребро метаграфа; $\nu _{S}$ — исходная вершина (метавершина) ребра; $\nu _{E}$ — конечная вершина (метавершина) ребра; $eo$ — признак направленности метаребра ($eo=true$ — направленное метаребро, $eo=false$ — ненаправленное метаребро); $atr_{k}$ — атрибут; $e\nu _{j}$ — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.

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

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

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

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

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

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

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

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

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

Структура правила метаграфового агента: $r_{i}\colon MG_{j}\to OP^{MG}$ где $r_{i}$ — правило; $MG_{j}$ — фрагмент метаграфа, на основе которого выполняется правило; $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.