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

master's thesis

• Title (english): Minimal independent dominating set calculation based on graph neural networks
• Author: Marko Kozlik
• Mentor: Stjepan Bogdan (mentor)
• Committee member: Stjepan Bogdan (član povjerenstva)
• Committee member: Matko Orsag (član povjerenstva)
• Committee member: Tamara Petrović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-08-28, Croatia

Abstract

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.

Abstract (english)

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.

• Keywords: MIDS; GNN
• Keywords (english): MIDS; GNN
• Language: english
• URN:NBN: urn:nbn:hr:168:967425
• Study programme: Title: Information and Communication Technology; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije (magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-10-12 21:10:11