Python implementation of algorithms for analyzing graph similarity

W wielu dziedzinach nauki powszechnie używa się grafowej reprezentacji danych w celach przedstawienia ich charakteru, opracowania strategii działania lub zbadanie podobieństwa do innego obiektu. Niniejsza praca przedstawia często stosowane podejścia do badania podobieństwa grafów w zależności od ich struktur i rozmiaru, które pozwalają na znajdywanie zadowalającej odpowiedzi w optymalnym okresie czasu. W przypadku dużych grafów znalezienie dokładnej wartości jest trudne, dlatego często stosuje się miary określające strukturę i cechy grafu, których wybór zależy od istotnych w danym przypadku właściwości - obejmują m.in badanie wierzchołków i wyodrębnianie ważnych podgrafów. Dla małych grafów możliwe jest zastosowanie badanie odległości edycyjnej tj. liczby operacji, których należy dokonać, aby “zamienić” jeden graf w drugi. Metody wyliczające tę wartość bazują często na algorytmie A*.

Graph representation of data is frequently used in many fields in order to define its character, plan a strategy of actions or to compare its similarity to another object. The thesis presents commonly used approaches to analyze graph similarity depending on their structure and size, which allows us to find satisfactory answer in an acceptable time period. It is very time-consuming to find the precise value when comparing large graphs, which is why measures describing its structure and characteristics are more often used. They include, among others, analyzing vertices and finding important subgraphs. For small graphs it is possible to apply methods finding graph edit distance value, i.e. number of operations needed to transform one of the given graphs into another. Many of such techniques are based on the A* algorithm.