Сопоставление нечетких графов

У меня есть нечеткий граф G=(V, E), где V — набор вершин, а E — набор ребер. Каждая вершина является нечеткой вершиной, то есть у нее есть свойство со связанной с ней функцией принадлежности (каким-то образом сохраненной в вершине). Каждое ребро является нечетким ребром, это означает, что оно имеет свойство со связанной с ним функцией принадлежности (каким-то образом сохраненной в ребре). Делая это, G является нечетким графом с точки зрения ребер и вершин.

Учитывая G и G2, еще один нечеткий граф с разным (или равным) количеством ребер и/или вершин, мне нужно сравнить оба графа нечетким способом. Я хочу проверить, является ли G2 подграфом или G (или наоборот). Есть ли какой-то алгоритм решения этой проблемы?


graph algorithm fuzzy subgraph
person Néstor    schedule 11.06.2019    source источник
comment
Кажется, я тебя не понимаю... @Yonlif   -  person Néstor    schedule 11.06.2019
comment
Функция каким-то образом хранится в вершине/ребре. Итак, при сравнении двух узлов/ребер вы можете вызвать его, чтобы проверить значение узла/ребра для его сравнения. @Йонлиф   -  person Néstor    schedule 11.06.2019
comment
О, теперь я понял! Нужно ли учитывать время вычисления функции?   -  person Yonlif    schedule 11.06.2019
comment
Ну и алгоритм должен быть максимально быстрым, но это не главная цель. Что касается функции принадлежности, она должна быть O(1), так что не беспокойтесь об этом. @Йонлиф   -  person Néstor    schedule 11.06.2019
comment
Итак, у каждой вершины есть функция, которая может быть передана другой вершине и возвращает логическое значение, указывающее, является ли вторая вершина членом первой?   -  person Richard    schedule 15.06.2019
comment
Что такое функция принадлежности? Какова сигнатура этих функций и что они вычисляют? Изоморфизм подграфов тривиально равен O(n), если вершины и ребра помечены.   -  person Gene    schedule 15.06.2019
comment
@Richard каждая вершина и каждое ребро имеют функцию принадлежности (en.wikipedia.org/wiki/Membership_function_ (математика)), связанный с нечетким множеством, которое он представляет. Эта функция вернет значение (обычно от 0 до 1), которое будет использоваться для сравнения узлов/ребер. Два узла будут похожи, если они имеют одинаковое значение своих функций принадлежности. Сравнение должно быть нечетким.   -  person Néstor    schedule 15.06.2019
comment
@Gene, взгляните, пожалуйста, на мой предыдущий комментарий.   -  person Néstor    schedule 15.06.2019
comment
@Néstor Что вы подразумеваете под «нечетким сравнением»? Насколько я понимаю, вам нужно знать, есть ли идеальное совпадение между G и G2. Что, если, например. совпадение 1-почти идеальное? или 2-вблизи и т.д.?   -  person hidefromkgb    schedule 15.06.2019
comment
@hidefromkgb У вас может быть конкретная/четкая информация или нечеткая информация. Мне нужно сравнить оба графика нечетким способом: en.wikipedia.org/wiki/Fuzzy_logic На самом деле мне не нужно идеальное совпадение, мне нужно знать, насколько похожи оба графа или насколько один граф является подграфом другого.   -  person Néstor    schedule 15.06.2019
comment
@Néstor Я понимаю, что такое нечеткая логика. Чего я не знаю, так это термина «нечеткое сравнение». Насколько «нечетко» похожи, например. граф в форме треугольника и граф в форме квадрата?   -  person hidefromkgb    schedule 15.06.2019
comment
@hidefromkgb Нечеткость в узлах и ребрах, а не в графе. Представьте себе два тривиальных графа, G1 и G2 с одним узлом в каждом. Оба узла представляют нечеткий цвет. Узел в G1 имеет степень принадлежности к красному цвету 0,7. Узел в G2 имеет степень принадлежности к красному цвету 0,7. G2 является подграфом G1 с паросочетанием 1,0. Та же ситуация, но теперь узел в G2 имеет степень принадлежности к красному цвету 0,5. G2 является подграфом G1 со степенью соответствия X, где 0,0 ‹ X ‹ 1,0.   -  person Néstor    schedule 15.06.2019
comment
@Néstor Итак, какова метрика сходства, по которой вычисляется X? Это, например, exp(–abs(e₁ – e₂)) или, скажем, 2cot⁻¹(abs(e₁ – e₂))/π, или даже дельта Дирака? И потом, как эта метрика масштабируется за пределы одного узла графа? Эти две вещи имеют решающее значение для разработки алгоритма, так как без них мы не сможем ответить, лучше ли, например, охватить все узлы, но получить метрику ‹1.0 на любом из них, или охватить меньше узлов, но поддерживать строгое значение 1.0 и все такое прочее.   -  person hidefromkgb    schedule 15.06.2019
comment
Давайте продолжим обсуждение в чате.   -  person Néstor    schedule 15.06.2019
comment
Я создал чат на основе предложения stackoverflow, взгляните на мой предыдущий комментарий @hidefromkgb   -  person Néstor    schedule 16.06.2019

Ответы (2)


arrow_upward
2
arrow_downward

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

Но у вас не графики, у вас нечеткие графики. Я не знаю, существует ли явный алгоритм, но я бы попробовал два подхода:

  1. Если вы можете определить членство как вероятность, вы можете сначала найти «максимальное сходство», предполагая обычные графики (P{is member}=1), а затем попытаться найти какое-то отношение, используя Байесовские сети (если ациклические) или более общим способом с использованием Марковские случайные поля.

  2. Вы можете определить метрику между нечеткими графами, используя методы Монте-Карло. В качестве примера просто пройдитесь по двум графикам и остановитесь, когда один шаг даст какую-то разницу. Количество шагов — это показатель. Запустите n раза и получите max, avg,... Окончательный алгоритм сильно зависит от того, имеет ли ваша функция принадлежности состояние, вы знаете "максимальное сходство" и так далее...

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

В любом случае удобство использования определенной метрики субъективно (если вы не объясните требования, любая метрика может быть действительной).

person josejuan    schedule 16.06.2019

arrow_upward
1
arrow_downward

Это может быть полезно: Подход сопоставления нечетких графов в анализе разведывательных данных и поддержании постоянной ситуационной осведомленности< /а>

Подход для приблизительного сопоставления подграфов в нечетком RDF-графе

person Elegant Code    schedule 21.06.2019