Граф Изоморфизм Эвристические Решения
Я пытаюсь реализовать эвристическое решение для идентификации классов изоморфных графов из заданного набора графов. В настоящее время я маркирую каждый узел мультимножеством степеней его соседей (алгоритм WL).
Это, очевидно, приводит к ложным срабатываниям в таких случаях, как регулярные графы степени. Я надеялся найти другую дешевую реализуемую (ограниченную по времени и пространству) эвристику, которая могла бы преодолеть угловые случаи алгоритма WL. По сути, я ищу пару легко реализуемых эвристик, которые между ними дают незначительные ложные срабатывания.
На какую эвристику, кроме алгоритма WL, мне следует обратить внимание?
Спасибо!
4 ответа
Я обнаружил, что алгоритм относится к категории алгоритмов Вейсфейлера-Лемана k-размерности, и он не работает с регулярными графами. Для больше здесь:
http://dabacon.org/pontiff/?p=4148
Оригинальный пост следует:
Я работал над проблемой, чтобы найти изоморфные графы в базе данных графов (содержащих химические составы).
Вкратце, алгоритм создает хэш графа, используя метод степенной итерации. Могут быть ложно-положительные коллизии хэшей, но вероятность этого чрезвычайно мала (у меня не было таких коллизий с десятками тысяч графиков).
Алгоритм работает так:
Выполните N (где N- радиус графика) итераций. На каждой итерации и для каждого узла:
- Сортировать хэши соседей узла
- Хеширование сцепленных отсортированных хэшей
- Заменить хеш узла вновь вычисленным хешем
На первом шаге на хеш узла влияют его прямые соседи. На втором шаге на хеш узла влияет соседство в 2 шагах от него. На N-м шаге на хеш узла будут влиять соседние N-прыжки вокруг него. Таким образом, вам нужно только продолжать запускать Powerhash для шагов N = graph_radius. В конце концов, хеш центра графа будет затронут всем графом.
Чтобы получить окончательный хэш, отсортируйте хеши узла последнего шага и объедините их вместе. После этого вы можете сравнить последние хеши, чтобы определить, являются ли два графа изоморфными. Если у вас есть метки, добавьте их во внутренние хэши, которые вы рассчитываете для каждого узла (и на каждом шаге).
Здесь больше предыстории:
https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF
Вы можете найти его исходный код здесь:
https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py
Ознакомьтесь с алгоритмом VF2: http://www.researchgate.net/profile/Carlo_Sansone/publication/200034365_An_Improved_Algorithm_for_Matching_Large_Graphs/links/0912f50dc9cf0a98d4000000.pdf
Есть библиотека C++, которая реализует VF2: http://mivia.unisa.it/datasets/graph-database/vflib/
Сравнение VF2 с несколькими другими алгоритмами: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.2640&rep=rep1&type=pdf
Может быть, рассмотрим наименьший цветной инвариант кратчайшего пути, обсуждаемый в этой статье: http://www.academia.edu/5111652/A_new_refinement_procedure_for_graph_isomorphism_algorithms?
Другим инвариантом, который может быть относительно дешевым для вычисления, является список циклов, частью которых является вершина. Конечно, это требует нахождения циклов в вашем графике, но для этого есть много алгоритмов.