Algoritmi otkrivanja zajednice u modelu graf baze podataka za sustav preporuke

undergraduate thesis

• Title (english): Community detection agotihms in graph database model for a recommender system
• Author: Lovro Malojčić
• Mentor: Mario Brčić (mentor)
• Committee member: Mario Brčić (predsjednik povjerenstva)
• Committee member: Mihael Kovač (član povjerenstva)
• Committee member: Kristijan Poje (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-05, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Sustavi preporuke temeljeni na kolaborativnom filtriranju (engl. collaborative filtering
recommender system) za identifikaciju sličnih proizvoda koriste algoritme za otkrivanje
zajednica (engl. community detection algorithms) u grafovima. S tim ciljem je u ovom radu
provedena analiza tih algoritama za pronalaženje zajednica bez preklapanja. Analizirani
algoritmi su: Louvain, Leiden, širenje oznaka, infomap i Constant Potts Model. Algoritmi
su provedeni nad stvarnim grafovima od kojih su neki pohranjeni u graf bazu podataka, a
to su karate klub, firentinske obitelji, glavni gradovi svijeta i Amazon proizvodi te nad
sintetičkim LFR grafovima. Dobivene zajednice uspoređene su po unutrašnjim metrikama
modularnosti i provodnosti te vanjskim metrikama normalizirane F1 vrijednosti i
normaliziranom uzajamnom sadržaju informacija.

Abstract (english)

Collaborative filtering recommender systems use algorithms for community detection in
graphs to identify similar products. This study analyzes community detection algorithms
for crisp communities for this purpose. The analyzed algorithms include Louvain, Leiden,
label propagation, infomap, and Constant Potts Model. These algorithms were applied to
real-world graphs, some of which were stored in a graph database, including the karate
club, Florentine families, world capitals, Amazon products, as well as synthetic LFR
graphs. The obtained communities were compared using internal metrics such as
modularity and conductance, as well as external metrics such as normalized F1 score and
normalized mutual information.

• Keywords: teorija grafova; detekcija zajednica; analiza algoritama; Python; CDLib
• Keywords (english): graph theory; community detection; algorithm analysis; Python; CDLib
• Language: croatian
• URN:NBN: urn:nbn:hr:168:462358
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:17:40