Метаграф
Эту статью предлагается удалить. |
Метаграфы в математике — обобщение концепций графовых структур. В метаграфе есть и элементы и орграфов, и гиперграфов, сам метаграф процесса выстраивается на основе иерархического графа. Формально, метаграф определяется множество <V,MV, E, ME>, где V — множество вершин, MV — множество метавершин, E — множество ребер, ME — множество метаребер.
Метаграфовая модель А. Базу и Р. Блэннинга
Исторически монография А. Базу и Р. Блэннинга[1] была первым источником, в котором появился термин «метаграф». В монографии даются следующие определения, характеризующие метаграфовую модель.
Порождающее множество метаграфа — это множество переменных, встречающихся в ребрах метаграфа: .
Ребро метаграфа (где — множество ребер) содержит входную вершину' (invertex)' и выходную вершину (outvertex) . Входная и выходная вершины могут содержать произвольное количество элементов. Различные элементы, принадлежащие входной (выходной) вершине, называются соответственно совходами (совыходами).
Тогда метаграф — это графовая конструкция, определяемая порождающим множеством и множеством ребер , при этом множество ребер определено на том же порождающем множестве.
Простым путем из элемента x в элемент y это последовательность ребер , такая что:
- является входной вершиной ;
- является выходной вершиной ;
- для всех выполняется условие: , то есть путь из начальной вершины в конечную не прерывается.
В монографии[2] приводится пример метаграфа, представленный на рис. 1, для которого приводится следующая теоретико-множественная интерпретация:
- ;
- ;
- .
Эмерджентность в модели А. Базу и Р. Блэннинга достигается за счет использования ребер. Понятие метавершины в данной модели отсутствует.
В целом можно отметить, что данный вариант метаграфовой модели более подходит для описания направленных процессов, чем для описания сложных графовых структур данных.
Метаграфовая модель с метавершинами
Отсутствие естественного механизма для описания сложных графовых структур данных привело к появлению расширений исходной модели А. Базу и Р. Блэннинга. В моделях появились новые элементы — метавершины и метаребра.
В работе[3] появляется понятие метавершины. В этой работе даются следующие определения метаграфовой модели.
Метаграф — это тройка множеств вершин, метавершин и ребер соответственно: , где — множество вершин метаграфа (порождающее множество); — множество метавершин метаграфа; — множество ребер метаграфа.
Метавершина метаграфа определяется как множество вершин , входящих в метавершину , где — мощность множества.
Очень интересным следует считать следующее замечание авторов модели[4]: «… если две или больше метавершин соответствуют одному и тому же множеству вершин, то такие вершины считаются одинаковыми и рассматривается только одна из таких метавершин». Назовем данное свойство модели[3] свойством анти-аннотируемости, особенности которого будут рассмотрены далее.
Интересно, что для задания ребер, авторы модели[3] вводят понятие узла метаграфа , принадлежащего объединённому множеству вершин и метавершин. Ребро определяется как , то есть характеризуется исходящим и входящим узлами метаграфа. Но использование понятия узла для создания иерархических метавершин авторами модели не предлагается.
Иерархическая метаграфовая модель с метавершинами и метаребрами
В работе[5] появляется не только понятие метавершины, но также понятия метаребра и иерархии вершин.
Метаграф в модели[5] определяется как , где — множество вершин метаграфа (порождающее множество); — множество метавершин метаграфа; — множество ребер метаграфа; — множество метаребер метаграфа, заданных на множестве .
Таким образом, под метаребром в данной модели понимается ребро, которое может соединять вершину и метавершину или две метавершины.
Важной особенностью данной модели является то, что авторы вводят понятие вложенного метаграфа, который, как полагают авторы, является «обобщением обычных графов, гиперграфов и метаграфов»[5].
В данной модели множество вершин рассматривается как иерархическое, вводится индекс , определяющий уровень вложенности вершины.
Свойство анти-аннотируемости авторами модели не утверждается и не опровергается. При этом, приводимые в статье примеры неявно используют свойство анти-аннотируемости.
Необходимо отметить, что относительно небольшая по объёму работа[5] цитируется в большинстве более поздних статей по тематике метаграфов, что с нашей точки зрения говорит о важности центрального вопроса данной статьи — описания иерархий в метаграфовой модели.
Аннотируемая метаграфовая модель
Аннотируемая метаграфовая модель расширяет идеи исходной модели А. Базу и Р. Блэннинга[2] и идеи работы[5]. Содержание работы[3] на момент появления первой версии аннотируемой метаграфовой модели[6] было нам неизвестно.
Аннотируемую метаграфовую модель предлагается использовать как средство для описания сложных сетей[7], как средство для описания семантики и прагматики информационных систем[6], как средство для описания гибридных интеллектуальных информационных систем[8]. Определим метаграф следующим образом: где — метаграф; — множество вершин метаграфа; — множество метавершин метаграфа; — множество ребер метаграфа; — множество метаребер метаграфа.
Вершина метаграфа характеризуется множеством атрибутов: где — вершина метаграфа; — атрибут.
Ребро метаграфа характеризуется множеством атрибутов, исходной и конечной вершиной и признаком направленности: где — ребро метаграфа; — исходная вершина (метавершина) ребра; — конечная вершина (метавершина) ребра; — признак направленности ребра ( — направленное ребро, — ненаправленное ребро); — атрибут.
Фрагмент метаграфа в общем виде может содержать произвольные вершины (метавершины) и ребра (метаребра): , где — фрагмент метаграфа; — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.
Метавершина метаграфа в дополнение к свойствам вершины включает вложенный фрагмент метаграфа: , где — вершина метаграфа; — атрибут, — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.
Наличие у метавершин собственных атрибутов и связей с другими вершинами является важной особенностью метаграфов. Это соответствует принципу эмерджентности, то есть приданию понятию нового качества, несводимости понятия к сумме его составных частей. Фактически, как только вводится новое понятие в виде метавершины, оно «получает право» на собственные свойства, связи и т. д., так как в соответствии с принципом эмерджентности новое понятие обладает новым качеством и не может быть сведено к подграфу базовых понятий.
Таким образом, метаграф можно охарактеризовать как «сложный граф с эмерджентностью» или «сложную сеть с эмерджентностью», то есть фрагмент сети, состоящий из вершин и связей, может выступать как отдельное целое.
Пример описания метаграфа показан на рис. 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, что показывает холоническую структуру метаграфа.
Отметим, что в отличие от[3], в данной модели не выполняется свойство анти-аннотируемости. Одинаковый набор вершин и ребер может быть включен в несколько различных метавершин, которые могут представлять различные ситуации и быть аннотированы различными атрибутами.
Также, в предлагаемой нами модели, метавершина может включать как вершины, так и ребра.
Метаребро метаграфа в дополнение к свойствам ребра включает вложенный фрагмент метаграфа: где — метаребро метаграфа; — исходная вершина (метавершина) ребра; — конечная вершина (метавершина) ребра; — признак направленности метаребра ( — направленное метаребро, — ненаправленное метаребро); — атрибут; — элемент, принадлежащий объединению множеств вершин (метавершин) и ребер (метаребер) метаграфа.
Пример описания метаребра метаграфа представлен на рис. 3. Метаребро содержит метавершины и связывающие их ребра. Исходная метавершина содержит фрагмент метаграфа. В процессе преобразования исходной метавершины в конечную метавершину происходит дополнение содержимого метавершины, добавляются новые вершины, связи, вложенные метавершины.
Таким образом, иерархическому метаребру из модели[5] соответствует обычное ребро в предлагаемой нами модели. А под метаребром понимается последовательность изменения метавершин метаграфа.
Если метавершины предназначены прежде всего для описания данных и знаний, то метаребра предназначены в большей степени для описания процессов. Таким образом, метаграфовая модель позволяет в рамках единой модели описывать данные, знания и процессы.
Использование агентов для обработки аннотируемой метаграфовой модели
Аннотируемая метаграфовая модель предназначена для описания данных. Рассмотрим способ преобразования метаграфовой модели на основе мультиагентного подхода. В предлагаемом подходе используются два вида агентов: агент-функция и метаграфовый агент.
Определим агент-функцию следующим образом: где — агент-функция; — метаграф, который выполняет роль входного параметра агента-функции; — метаграф, который выполняет роль выходного параметра агента-функции; — абстрактное синтаксическое дерево агента-функции, которое может быть представлено в виде метаграфа.
Определим метаграфовый агент следующим образом: где — метаграфовый агент; — метаграф данных и знаний, на основе которого выполняются правила агента; — набор правил (множество правил ); — стартовое условие выполнения агента (фрагмент метаграфа, который используется для стартовой проверки правил, или стартовое правило).
Структура правила метаграфового агента: где — правило; — фрагмент метаграфа, на основе которого выполняется правило; — множество операций, выполняемых над метаграфом.
Антецедентом правила является фрагмент метаграфа, консеквентом правила является множество операций, выполняемых над метаграфом.
Отметим, что правила метаграфового агента можно разделить на замкнутые и разомкнутые.
Разомкнутые правила не меняют в правой части правила фрагмент метаграфа, относящийся к левой части правила. Можно разделить входной и выходной фрагменты метаграфа. Данные правила являются аналогом шаблона, который порождает выходной метаграф на основе входного.
Замкнутые правила меняют в правой части правила фрагмент метаграфа, относящийся к левой части правила. Изменение метаграфа в правой части правил заставляет срабатывать левые части других правил. Но при этом некорректно разработанные замкнутые правила могут привести к зацикливанию метаграфового агента. Таким образом, метаграфовый агент позволяет генерировать один метаграф на основе другого (с использованием разомкнутых правил) или модифицировать метаграф (с использованием замкнутых правил).
Литература
- 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.
Примечания
- ↑ Basu A., Robert W. Blanning. Metagraphs and their applications. — New York: Springer, 2007. — С. 14.
- ↑ 1 2 Basu A., Robert W. Blanning. Metagraphs and their applications. — New York: Springer, 2007.
- ↑ 1 2 3 4 5 Глоба, Л. С. Метаграфы как основа для представления и использования баз нечетких знаний / Л. С. Глоба, М. Ю. Терновой, Е. С. Штогрина
- ↑ Глоба, Л. С. Метаграфы как основа для представления и использования баз нечетких знаний / Л. С. Глоба, М. Ю. Терновой, Е. С. Штогрина — С. 238.
- ↑ 1 2 3 4 5 6 Астанин С. В., Драгныш Н. В., Жуковская Н. К. Вложенные метаграфы как модели сложных объектов // Инженерный вестник Дона, 2012, № 4.
- ↑ 1 2 Самохвалов Э. Н., Ревунков Г. И., Гапанюк Ю. Е. Использование метаграфов для описания семантики и прагматики информационных систем.
- ↑ Черненький В. М., Терехов В. И., Гапанюк Ю. Е. Представление сложных сетей на основе метаграфов
- ↑ Черненький В. М., Гапанюк Ю. Е., Ревунков Г. И., Терехов В. И., Каганов Ю. Т. Метаграфовый подход для описания гибридных интеллектуальных информационных систем.