Метаграф

Название статьи — это

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

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

Порождающее множество метаграфа – это множество переменных, встречающихся в ребрах метаграфа: $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$ , то есть путь из начальной вершины в конечную не прерывается.

В монографии [4] приводится пример метаграфа, представленный на рис. 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\}>$.

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

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

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

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

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

Метаграф – это тройка множеств вершин, метавершин и ребер соответственно: $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}$ – мощность множества.

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

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

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

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

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

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

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

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

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

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

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

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

Аннотируемую метаграфовую модель предлагается использовать как средство для описания сложных сетей [8], как средство для описания семантики и прагматики информационных систем [7], как средство для описания гибридных интеллектуальных информационных систем [9]. Определим метаграф следующим образом: $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 показаны три метавершины: 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, что показывает холоническую структуру метаграфа.

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

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

Метаребро метаграфа в дополнение к свойствам ребра включает вложенный фрагмент метаграфа: $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. Метаребро содержит метавершины $\nu _{S},\dots ,\nu _{i},\dots ,\nu _{E}$ и связывающие их ребра. Исходная метавершина содержит фрагмент метаграфа. В процессе преобразования исходной метавершины $\nu _{S}$ в конечную метавершину $\nu _{E}$ происходит дополнение содержимого метавершины, добавляются новые вершины, связи, вложенные метавершины.

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

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

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

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

Определим агент-функцию следующим образом: $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}$ – множество операций, выполняемых над метаграфом.

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

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

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

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

Ссылки

• example.com