On measuring of similarity between tree nodes

Abstract

In this paper, a survey of similarity measures between vertices of a graph is presented. Distance-based and structural equivalence measures are described. It is demonstrated that most of them degenerate if applied directly to the tree nodes. Adjusted path-based similarity measure is proposed as well as a new method for representing tree nodes as binary vectors that is based on using of an ancestor matrix. It is shown that application of ordinary similarity measures to this representation gives desired non-trivial results.