TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Comparing large graphs efficiently by margins of feature vectors

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut1699-1710
Sivumäärä12
JulkaisuApplied Mathematics and Computation
Vuosikerta188
Numero2
DOI - pysyväislinkit
TilaJulkaistu - 15 toukokuuta 2007
Julkaistu ulkoisestiKyllä
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.