Мера подобия графа с неизвестным соответствием узла

Question

Как измерить сходство между двумя графами G1 и G2 с равным или неравным числом узлов, где соответствие между узлами графиков неизвестно. Например, узел A в G1 переместился в середину G2. Существует ли какой-либо алгоритм измерения сходства, который возвращает

sim(G1,G1)=1 sim(G1,G2)=1 sim(G1,G3)=some number between 0 and 1

, где 1 обозначает наибольшее сходство, а 0 обозначает самое низкое сходство.

Answer 1

Поскольку вы не знаете соответствия узлов, один простой подход - определить сигнатуру графа как отсортированный массив, содержащий степени всех узлов. Затем найдите самую длинную общую подпоследовательность из двух сигнатур, где «общее» не обязательно означает, что все «элементы равны», но что они достаточно близки. Поскольку сигнатуры являются отсортированными массивами, проблема еще проще. А затем каким-то образом вычислить расстояние между двумя версиями самой длинной «общей» подпоследовательности. Кроме того, вы можете учитывать некоторые оценки, касающиеся узлов, которые не являются его частью.