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