Tampere University of Technology

TUTCRIS Research Portal

Comparing large graphs efficiently by margins of feature vectors

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)1699-1710
Number of pages12
JournalApplied Mathematics and Computation
Volume188
Issue number2
DOIs
Publication statusPublished - 15 May 2007
Externally publishedYes
Publication typeA1 Journal article-refereed

Abstract

Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance.

Keywords

  • Degree vectors, Directed and undirected graphs, Graph similarity, Similarity measures