NetworkX: приблизительный / неточный изоморфизм подграфа для неориентированных взвешенных графов
Учитывая два графика (A и B), я пытаюсь определить, существует ли подграф B, который соответствует A с данным порогом, основываясь на разнице в весах ребер. То есть, если я возьму сумму разности между каждой парой связанных ребер, она будет ниже заданного порога. Метки вершин не согласуются между A и B, поэтому я просто полагаюсь на вес ребер.
A будет несколько меньше (например, максимум 10), а B будет больше (например, максимум 200).
1 ответ
Я считаю, что один из этих двух пакетов может помочь:
Инструментарий сопоставления графиков в MATLAB "реализует сопоставление спектральных графов с аффинным ограничением (SMAC), опционально с бистохастической нормализацией Кронекера". На веб-странице говорится, что он "обрабатывает графики разных размеров (сопоставление подграфа)" http://www.timotheecour.com/software/graph_matching/graph_matching.html
Алгоритм, используемый в наборе инструментов для сопоставления графиков в MATLAB, основан на алгоритме, описанном в статье Тимоти Кур, Правин Сринивасан и Цзянбо Ши под названием "Сопоставление сбалансированных графов". Статья была опубликована в NIPS 2006.
Кроме того, существует второй инструментарий под названием Graph Matching Toolkit (GMT), который, кажется, может иметь поддержку сопоставления с ошибочным подграфом, так как он поддерживает сопоставление с ошибками графом. Вместо того, чтобы использовать спектральный метод, у него есть различные методы вычисления расстояния редактирования, и затем у меня сложилось впечатление, что он находит лучшее соответствие, давая argmax минимального расстояния редактирования. Если он явно не поддерживает сопоставление подграфа и вас не интересует эффективность, вы можете просто выполнить поиск по всем подграфам B и использовать GMT, чтобы попытаться найти совпадения этих подграфов в A. Или, возможно, вы можете просто выполнить поиск по подмножеству подграфы Б. http://www.fhnw.ch/wirtschaft/iwi/gmt
К сожалению, ни один из них, кажется, не в Python, и они также не поддерживают формат графика networkx. Но я полагаю, что вы сможете найти конвертер, который изменит представление графа networkx на что-то пригодное для использования этими инструментами. Затем вы можете запустить наборы инструментов и вывести желаемые соответствия подграфа.