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

master's thesis

• Title (english): Modifications of the label propagation algorithm that solve the problem of community detection in acyclic digraph
• Author: Dorian Kablar
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Committee member: Mate Puljiz (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-27, Croatia

Abstract

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.

Abstract (english)

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.

• Keywords: teorija grafova; prepoznavanje zajednica; usmjereni aciklički grafovi; propagacija oznaka
• Keywords (english): graph theory; community detection; directed acyclic graphs; label propagation
• Language: croatian
• URN:NBN: urn:nbn:hr:168:116571
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:10:25