Two approaches to determining similarity of two digraphs

Journal of Computer and Systems Sciences International. 2012. Vol. 51. No. 5. P. 695–714.

Kokhov V. A.

An approach to solving the problem of determining similarity with application of a maximal common fragment of two graphs is considered. Its two main disadvantages are specified. Two new approaches to solving the problem of determining similarity of digraphs are proposedamp;: a generalized substructural-metric approach and an approach using a stratified system of matrix models of the digraph complexity. New features for investigating similarity of digraphs are formulated. The original problem of calculating similarity of layout of fragments in the digraph is formalized with account of quantitative and qualitative features of fragments of the digraph. A methodology, involving two systems of methods for solving the problem, is developed. The first system of methods takes into account the precise layout of fragments in the digraph, while the second one deals with the approximate layout of fragments. A new class of problems is distinguished, which consists in calculating similarity of digraphs with account of similarity of the layout of fragments of the specified type. An example of solving the problem of finding semantic networks that are most similar to a network-template is presented.

Keywords: semantics, matrix model, two-graphs, stratified systems, semantic network, qualitative features, first systems, directed graphs, problem solving