Об измерении сходства между узлами дерева

Аннотация

В данной работе выполнен обзор мер сходства между вершинами графа. Описаны меры, основанные на расстоянии, и меры структурной эквивалентности. Показано, что большинство из них вырождаются, если их непосредственно применять к узлам дерева. Предложена скорректированная мера сходства, основанная на расстоянии, а также новый метод представления узлов дерева бинарными векторами, основанный на использовании матрицы предков. Показано, что применение обычных мер сходства к этому представлению даёт желаемые нетривиальные результаты.