20.500.12556/RUL-150269 Uporaba preiskovalne ekvivalence za pohitritev sodobnih algoritmov za problem podgrafnega izomorfizma Using exploratory equivalence to speed up state-of-the-art algorithms for the subgraph isomorphism problem Pri problemu podgrafnega izomorfizma se ukvarjamo z iskanjem pojavitev podanega vzorčnega grafa v podanem tarčnem grafu. Gre za pomemben problem na področju analize grafov, saj nastopa v vseh panogah, kjer nas zanimajo vzorci v grafih, na primer v kemiji ali pri analizi socialnih omrežij. Ker pa je problem podgrafnega izomorfizma NP-poln, so raziskave usmerjene v iskanje algoritmov, ki dobro delujejo vsaj v večini praktičnih primerov. Kot se izkaže, pa so mnogi od teh algoritmov neučinkoviti pri vzorčnih grafih z velikim številom avtomorfizmov (simetrij). V diplomski nalogi bomo pokazali, kako je mogoče obstoječe algoritme pohitriti z uporabo preiskovalne ekvivalence, ekvivalenčne relacije na množici vozlišč grafa, ki temelji na množici avtomorfizmov. Na podlagi preiskovalne ekvivalence vzorčnega grafa je namreč mogoče definirati množico omejitev, s katerimi lahko zmanjšamo nabor kandidatnih preslikav, ki jih moramo obravnavati pri iskanju primerkov vzorčnega grafa v tarčnem grafu. Obstoječe algoritme za reševanje problema podgrafnega izomorfizma smo nadgradili tako, da uporabljajo preiskovalno ekvivalenco. Svoje razširitve smo na več javno dostopnih zbirkah grafov primerjali z izhodiščnimi algoritmi. Izboljšave algoritmov smo objavili v obliki javno dostopnega modula v okviru obstoječe knjižnice za reševanje problema podgrafnega izomorfizma. The problem of subgraph isomorphism is concerned with finding the occurrences of a given pattern graph in a given target graph. This is an important problem in the area of graph analysis, for it finds its use whenever one is interested in searching for graph patterns, e.g., in chemistry or in social network analysis. However, since the subgraph isomorphism problem is NP-complete, research is focused on discovering algorithms that work well in a majority of practical cases. As it turns out, though, many of those algorithms are inefficient when given a pattern graph with a large number of automorphisms (symmetries). In this thesis, we will show how to speed up existing algorithms using a concept called exploratory equivalence, an equivalence relation on the graph’s vertex set that is based on the set of automorphisms. In particular, knowing exploratory equivalence of the pattern graph enables us to define a set of constraints that can be used to reduce the set of candidate mappings to be considered when searching for the occurrences of the pattern graph in the target graph. We improved the selected existing algorithms for the subgraph isomorphism problem in such a way that they make use of exploratory equivalence. We tested and evaluated our enhancements on multiple publicly available datasets. We published improvements of the algorithms in the form of a publicly available module within an existing library for solving the subgraph isomorphism problem. podgrafni izomorfizem graf preiskovalna ekvivalenca algoritem simetrija optimizacija subgraph isomorphism graph exploratory equivalence algorithm symmetry optimization true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2023-09-15 12:55:01 2023-09-15 12:55:06 2023-10-18 11:10:06 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36694 168897795 Kuhar_Jon_-_Uporaba_preiskovalne_ekvivalence_za_pohitritev_sodobnih_algoritmov_za_problem_podgra.pdf Kuhar_Jon_-_Uporaba_preiskovalne_ekvivalence_za_pohitritev_sodobnih_algoritmov_za_problem_podgra.pdf 1 F6C5AA69CBD9C07F499BDD9D3EBE72EF 0cd425c946d5c86de557bc228df5433615499dbdc8a15f49f9238d3641ef3f3f 54c93d4f-53b6-11ee-9ef6-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=174836 Fakulteta za računalništvo in informatiko 0 0 0