Title Otkrivanje zajednica u grafu 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 Defense date and country 2021-09-24, Croatia Scientific / art field, NATURAL SCIENCES 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
... More 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. Less 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
... More 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. Less 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 Type of resource Text File origin Born digital Access conditions Open access Terms of use Created on 2021-11-02 13:25:03
