Otkrivanje zajednica u grafu

master's thesis

• Title (english): Discovering communities in a graph
• Author: Luka Naglić
• Mentor: Zlatko Drmač (mentor)
• Committee member: Zlatko Drmač (predsjednik povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Committee member: Eduard Marušić-Paloka (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-09-24, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu obrađeni su osnovni koncepti polinomijalnih algoritama otkrivanja zajednica u grafu, tj. particije skupa čvorova danog grafa da bi posjedovao nekakvu interpretaciju. Obrađena je osnovna teorija grafova potrebna za razumijevanje opisanih algoritama te ostalih koncepata otkrivanja zajednica. Svi opisani algoritmi temelje se na hijerarhijskom pretraživanju. Glavna ideja hijerarhijskog pretraživanja je iz particije skupa čvorova generirati novu particiju čvorova. Dva su pristupa hijerarhijskom pretraživanju: aglomerativni i raščlambeni pristup. Aglomerativni je pristup koji u svakoj iteraciji povećava broj particija za jedan, a raščlambeni onaj koji u svakoj iteraciji smanjuje broj particija za jedan. Opisani su najpoznatiji algoritmi oba pristupa, a to su Ravaszov i Girvan-Newmanov. Također je opisan i pohlepni algoritam optimiziranja modularnosti, koji se može prilagoditi obama pristupima. Rezultat algoritama hijerarhijskog pretraživanja je niz famlija zajednica. Nizovi familija zajednica prikazani su dendrogramima. Efikasnost neoptimiziranih, ali ekvivalentnih Python implementacija svih opisanih algoritama, kao i kvaliteta rezultata vrednovana modularnošću, napravljena je na nasumično generiranim grafovima uz pomoć NetworkX biblioteke.

Abstract (english)

This article deals with polynomial algorithms for community detection in networks which satisfy some useful interpretation when applied. The basic theory necessary for the understanding of community detection algorithms is explained, as well as some community detection algorithms and properties. The algorithms described are part of a concept called hierarchical clustering. The main focus of hierarchical clustering is transforming of a vertex partition into a new vertex partition, thus creating a hierarchy. There are two approaches, one of which is agglomerative, and the other divisive. The agglomerative approach attempts to increase the number of partitions by one at each iteration, whereas the divisive approach attempts to do the opposite, decreasing the number of partitions by one at each iteration. We have described the best known examples of algorithms for each approach – the Ravasz and the Girvan-Newman algorithm, respectively. Apart from that, we have described a greedy algorithm for optimizing modularity which can be implemented in both approaches. The result of hierarchical clustering is a family of community series, which we have visualized by using dendrograms. The efficiency of the non-optimal, but equivalent Python implementation of the algorithms decribed above, as well as the quality of the results measured by modularity has been conducted on randomly generated networks, with the help of a Python library called NetworkX.

• Keywords: polinomijalni algoritmi; hijerarhijsko pretraživanje; aglomerativni pristup; raščlambeni pristup; Ravaszov pristup; Girvan-Newmanov pristup; NetworkX biblioteka
• Keywords (english): polynomial algorithms; hierarchical clustering; agglomerative approach; divisive approach; Ravasz algorithm; Girvan-Newman algorithm; NetworkX library
• Language: croatian
• URN:NBN: urn:nbn:hr:217:930707
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Embargoed access; Embargo expiration date: 2023-11-02
• Created on: 2021-11-02 13:25:03