Поиск схожих подграфов в невзвешенном неориентированном графе посредством вычисления изоморфных путевых наборов

Аннотация

Тема поиска подграфов в суперграфе является до сих пор актуальной и фундаментальной задачей. Так как графы являются наиболее удачными моделями, как для визуализации, так и для обработки сложных взаимосвязей, представленных в виде семантических сетей, как например, исходный код программ. Одной из важнейших задач анализа таких моделей данных является, задача поиска схожих подграфов. Существующие на данный момент методы, предложения и подходы, базируются на поиске изоморфных подграфов, в том числе, в виде промежуточных результатов, что не дает возможность находить подграфы по общей части с искомым графом в виде частичного графа. Представленный алгоритм работает на основе построения и анализа путевых наборов графов, по оригинальным алгоритмам построения путевого каркаса и итерационного алгоритма поиска наикратчайших путей между двумя вершинами и находит схожие подграфы в суперграфе G, выделяя общую часть с искомым графом Q в виде частичного графа F^Q, которая, в конечном счете, проходит проверку на изоморфизм.