Određivanje minimalnog nezavisnog dominantnog skupa primjenom grafovskih neuronskih mreža

diplomski rad

• Naslov (engleski): Minimal independent dominating set calculation based on graph neural networks
• Autor: Marko Kozlik
• Mentor: Stjepan Bogdan (mentor)
• Član povjerenstva: Stjepan Bogdan (član povjerenstva)
• Član povjerenstva: Matko Orsag (član povjerenstva)
• Član povjerenstva: Tamara Petrović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2024-08-28, Hrvatska

Sažetak

Cilj ovog diplomskog rada je razviti metodu za određivanje minimalnog nezavisnog dominantnog skupa (MIDS)
u općenitim grafovima zasnovanu na grafovskim neuronskim mrežama (GNN). Za postizanje ovog cilja,
potrebno je najprije proučiti matematičku definiciju i svojstva MIDS-a, kao i postojeće metode za njegovo
pronalaženje. Nadalje, potrebno je upoznati se s osnovnim modelima grafovskih neuronskih mreža i napraviti
kratak pregled područja njihovih primjena u optimizacijskim problemima. U sljedećem koraku treba generirati
skup podataka koji će se sastojati od velikog broja različitih grafova i njihovih MIDS, a služit će za treniranje
vlastitog ili nekog od postojećih modela GNN-a. Razvijena metoda validirat će se uspoređujući točnost i brzinu s
postojećim metodama te će se razmotriti njena potencijalna primjena na stvarne probleme poput određivanja
najutjecajnijih čvorova u više-agentskim sustavima.

Sažetak (engleski)

The goal of this thesis is to develop a method for determining the minimum independent dominant set (MIDS) in
general graphs based on graph neural networks (GNN). To achieve this goal, it is first necessary to study the
mathematical definition and properties of MIDS, as well as existing methods for finding it. Furthermore, it is
necessary to become familiar with the basic models of graph neural networks and to make a brief overview of
the field of their applications in optimization problems. In the next step, a data set should be generated, which
will consist of a large number of different graphs and their MIDS, and will be used to train a custom or one of the
existing GNN models. The developed method will be validated by comparing the accuracy and speed with
existing methods, and its potential application to real problems such as determining the most influential nodes in
multi-agent systems will be considered.

• Ključne riječi: MIDS; GNN
• Ključne riječi (engleski): MIDS; GNN
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:967425
• Studijski program: Naziv: Informacijska i komunikacijska tehnologija; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije (mag. ing. inf. et comm. techn.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2024-10-12 21:10:11