Modifikacije algoritma za propagaciju oznaka koje rješavaju problem prepoznavanja zajednica u usmjerenom acikličkom grafu

diplomski rad

• Naslov (engleski): Modifications of the label propagation algorithm that solve the problem of community detection in acyclic digraph
• Autor: Dorian Kablar
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Lana Horvat Dmitrović (član povjerenstva)
• Član povjerenstva: Mate Puljiz (č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: 2023-06-27, Hrvatska

Sažetak

Teorija grafova je grana matematike s brojnim primjenama u teoriji kompleksnih mreža, području kojem pripada i problem prepoznavanja zajednice. Problem prepoznavanja zajednice odnosi se na pronalaženje prirodne podjele mreže na grupe čvorova takve da postoji mnogo veza unutar zajednice, a nekoliko (manje) veza među grupama. U ovoj temi obradit će se problem prepoznavanja zajednica u usmjerenim acikličkim grafovima i, konkretnije, kurikulnim grafovima. Kurikulni grafovi su grafovi koji predstavljaju nastavne jedinice i njihovu međusobnu povezanost. Predstavit će se osnovni pojmovi teorije grafova te relevantni matematički rezultati. Opisat će se primjeren matematički model za problem prepoznavanja zajednica. Obradit će se tri modifikacije algoritma za propagaciju oznaka koje rješavaju problem prepoznavanja zajednica u usmjerenom acikličkom grafu. Algoritmi će se implementirati, testirati i usporediti. Izradit će se računalna aplikacija s grafičkim sučeljem prikladnim za crtanje grafova, i provođenje eksperimenata sa implementiranim algoritmima. Implementirani algoritmi primijenit će se za rješavanje problema grupiranja pojmova u nastavne cjeline.

Sažetak (engleski)

Graph theory is a branch of mathematics with numerous applications in the theory of complex networks, which includes the problem of community detection. The problem of community detection involves finding a natural division of a network into groups of nodes such that there are many connections within the group and few (or less) connections between groups. In this thesis, we will address the problem of community detection in a directed acyclic graph and, more concrete, curriculum graphs. Curriculum graphs are graphs that represent teaching units and dependencies between them. This paper will cover the basic concepts of graph theory and relevant mathematical results. We will describe a suitable mathematical model for the problem of community detection. We will present three modifications of label propagation algorithms that solve the problem of community detection in directed acyclic graphs. The algorithms will be implemented, tested, and compared. An web-application with a graphical interface suitable for graph drawing and doing the experiments with implemented algorithms. The implemented algorithms will be applied to solve the problem of grouping concepts into teaching units.

• Ključne riječi: teorija grafova; prepoznavanje zajednica; usmjereni aciklički grafovi; propagacija oznaka
• Ključne riječi (engleski): graph theory; community detection; directed acyclic graphs; label propagation
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:116571
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:10:25