NetworkX: Приблизительный/неточный изоморфизм подграфов для ненаправленных взвешенных графов

Question

Учитывая два графика (A и B), я пытаюсь определить, существует ли подграф B, который соответствует A заданному порогу, основанному на различии в весах ребер. То есть, если я возьму сумму разницы между каждой парой связанных ребер, она будет ниже заданного порога. Ярлыки вершин не согласуются между A и B, поэтому я просто полагаюсь на веса ребер.

A будет несколько небольшим (например, макс. 10), а B будет больше (например, макс. 200).

Answer 1

Я считаю, что одна из этих двух пакетов могут помочь:

графа Matching Toolbox в MATLAB «реализует спектральное согласование графа с аффинным ограничением (СМАК), необязательно с Кронекером бистохастических нормализацией». В нем говорится на веб-странице, что «обрабатывает графики различных размеров (соответствия подграф)» http://www.timotheecour.com/software/graph_matching/graph_matching.html

Алгоритм, используемый в графике Matching Toolbox в среде MATLAB основан на алгоритме, описанном в статье по Timothee Кур, Praveen Шринивасана, и Jianbo Ши под названием сбалансированного соответствия графика. Статья была опубликована в NIPS 2006.

Кроме того, имеется второй набор инструментов под названием Graph Matching Toolkit (GMT), который, похоже, может поддерживать совместимость с ошибками подграфа, поскольку он поддерживает совместимость с ошибками , Вместо того, чтобы использовать спектральный метод, он имеет различные методы вычисления расстояния редактирования, и тогда у меня сложилось впечатление, что он находит наилучшее соответствие, предоставляя argmax минимального расстояния редактирования. Если он явно не поддерживает подграфовое сопоставление, и вы не заботитесь об эффективности, вы можете просто искать все подграфы B и использовать GMT, чтобы попытаться найти совпадения этих подграфов в A. Или, может быть, вы могли бы просто найти подмножество подграфы B. http://www.fhnw.ch/wirtschaft/iwi/gmt

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