Analysis of graph similarity

Recently, there has been a growing interest in graphs as universal data structures. They are considered to be powerful and versatile tools for modeling the network of relations connecting substructures of a given object. The scope of their use is very wide. Graphs are used in fields such as computer science, mathematics, chemistry, biology, building industry and many others. No wonder that more and more processes and algorithms, for their in-depth analysis, are constantly being developed.One of the most difficult and computationally demanding issue turned out to be the problem of evaluation graphs similarity. This process, commonly referred to as the graph matching problem, seeks a compatibility between the vertices and edges of two graphs, ensuring that the match meets certain constraints. The graph matching process maps certain structures (subgraphs) of one graph to similar structures of the other graph. Based on this mapping, the final result of the similarity or dissimilarity of the graphs can be calculated.This paper focuses on the problem of graph similarity by distinguishing two categories: exact graph matching and inexact graph matching. Each of them is described in detail and relevant examples are presented, which are: isomorphism and the maximum common subgraph, as well as the edit distance and the graph edit distance. The algorithms presented in following section are optimal solutions: the ISMAGS to the maximum common subgraph problem, and the DF-GED to the graph edit distance problem. Their practical use has been presented in the created application.

Ostatnimi czasy dostrzega się rosnące zainteresowanie grafami, jako uniwersalnymi strukturami danych. Uznaje się je za potężne i wszechstronne narzędzia umożliwiające w sposób jednoznaczny modelowanie sieci relacji łączących podstruktury danego obiektu. Zakres ich wykorzystania jest bardzo szeroki. Z grafów korzysta się w dziedzinach takich jak informatyka, matematyka, chemia, biologia, budownictwo i wielu innych. Nic więc dziwnego, że nieustannie powstaje coraz więcej procesów i algorytmów pozwalających na przeprowadzanie ich dogłębnej analizy. Jednym z trudniejszych i bardziej wymagających obliczeniowo problemów okazało się zagadnienie oceny podobieństwa grafów. Proces ten powszechnie określany jako problem dopasowania grafów, szuka zgodności pomiędzy wierzchołkami i krawędziami dwóch grafów, przy zapewnieniu, że dopasowanie spełnia pewne ograniczenia. Proces dopasowania grafów mapuje więc pewne struktury (podgrafy) jednego grafu na podobne struktury grafu drugiego. Na podstawie tego mapowania można obliczyć ostateczny wynik podobieństwa lub niepodobieństwa grafów, wskazujący na ich tożsamość.W niniejszej pracy skupiono się na problemie podobieństwa grafów rozróżniając dwie kategorie: dopasowanie dokładne i dopasowanie niedokładne. W sposób szczegółowy opisano każdy z nich oraz zaprezentowano odpowiednie przykłady, jakimi są kolejno: izomorfizm i maksymalny wspólny podgraf oraz odległość edycyjna i odległość edycyjna grafu. Przedstawione w dalszej części algorytmy to optymalne rozwiązania: ISMAGS problemu maksymalnego wspólnego podgrafu, a DF-GED problemu odległości edycyjnej grafu. Ich praktyczne zastosowanie zostało zaprezentowane w stworzonym programie użytkowym.