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

Question

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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