20.500.12556/RUL-132171 Izboljšave dinamičnega algoritma za iskanje maksimalne klike v proteinskem grafu z uporabo strojnega učenja Improvements to the dynamic algorithm for finding maximum clique in a protein graph using machine learning Iskanje maksimalne klike spada med dobro raziskane NP-polne probleme. Za praktično uporabnost algoritmov za iskanje maksimalne klike morajo biti ti dovolj hitri na ciljni domeni grafov. V zadnjih letih je bilo narejenega veliko napredka na področju strojnega učenja na grafih. V magistrskem delu uporabimo moderne pristope strojnega učenja na grafih za pohitritev dinamičnega algoritma za iskanje maksimalne klike. Pohitritve testiramo na različnih vrstah grafov s poudarkom na različnih vrstah proteinskih grafov. Ugotovimo, da so pohitritve možne in jih lahko dosežemo z dobro izbiro modela za strojno učenje. Ugotovimo tudi, da pohitritve niso velike, vendar pa so konsistentne na skoraj vseh predstavljenih grafih. Finding maximum clique is a well-researched NP-complete problem. For the practical applicability of algorithms for finding the maximum clique, they must be fast enough on the target domain of graphs. There has been a lot of progress made in recent years in the field of machine learning on graphs. In the master's thesis we use modern approaches to machine learning on graphs to speed up the dynamic algorithm for finding the maximum clique. Speedups are tested with different types of graphs with an emphasis on different types of protein graphs. We find that speeding up the maximum clique search is possible and can be achieved with a good choice of machine learning model. We also find that the speedups are not large but are consistent on almost all the graphs presented. proteinski graf maksimalna klika strojno učenje protein graph maximum clique machine learning true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2021-10-15 08:00:10 2021-10-15 08:00:13 2022-09-12 04:11:21 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 28141 82279427 Reba_Kristjan_-_Izboljsave_dinamicnega_algoritma_za_iskanje_maksimalne_klike_v_proteinskem_grafu.pdf Reba_Kristjan_-_Izboljsave_dinamicnega_algoritma_za_iskanje_maksimalne_klike_v_proteinskem_grafu.pdf 1 17895B87903A912F6DF1D6B01DCD6F49 a9c123e1edd4ef3fa29cada7b2e22ab7322ce2b5b773cfc008e0f57fbdfa13f5 2865846c-2d7d-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=149715 Fakulteta za računalništvo in informatiko 0 0 0