Community structure is an important property of complex networks, since it reveals the organization of the network and relationships between its members. Therefore, the analysis of community structure and development of effective procedures for its detection has been one of the main focuses of network theory. Numerous methods have been proposed for detecting community structure in networks \cite{article7}. This thesis presents a heuristic community detection algorithm based on label propagation. Due to its simplicity and low time complexity, label propagation algorithm should be the first option to provide a better understanding of the network community structure before examining other more complex alternatives.
We give a brief introduction to graphs and networks, different clustering metrics and related work in the field of network community detection. Next, we present the basic approach of label propagation algorithm, discuss advantages and disadvantages, and review extensions of the method, focusing mainly on consensus clustering and fast consensus clustering. The aforementioned algorithms are implemented in a Python programming library, which is available at: \url{
https://github.com/damir1407/label-propagation}. Furthermore, we evaluate these three network clustering methods on different synthetic and real-world networks, and present the results. The thesis is concluded with a summary of the presented methods and directions for future work.
| Jezik: | Slovenski jezik |
|---|
| Naslov: | Primerjava algoritmov za odkrivanje skupnosti v omrežjih na osnovi izmenjave oznak |
|---|
| Izvleček: |
|---|
Struktura skupnosti je pomembna lastnost kompleksnih omrežij, saj razkrije organizacijo omrežja in razmerja med njegovimi člani. Zato sta analiza skupnosti in razvoj učinkovitih načinov za njihovo odkrivanje dva izmed pomembnih žarišč teorije omrežij. V literaturi so predlagani številni načini za odkrivanje strukture skupnosti v omrežjih~\cite{article7}. V tej diplomski nalogi je predstavljen hevrističen algoritem za odkrivanje skupnosti, ki temelji na izmenjavi oznak. Zaradi njegove enostavnosti in nizke časovne zahtevnosti, bi moral biti algoritem za izmenjavo oznak prva izbira pri zagotavljanju boljšega razumevanja strukture skupnosti v omrežjih, pred proučevanjem drugih, bolj zapletenih alternativ.
Začnemo s kratkim uvodom v grafe in omrežja, različne metrike gručenja in raziskave, ki se nanašajo na področje odkrivanja skupnosti v omrežjih. Potem predstavimo osnovne pristope algoritma za izmenjavo oznak, razpravljamo o njegovih prednostih in pomanjkljivostih, ter pregledamo razširitve metode s poudarkom na konsenznem gručenju in hitrem konsenznem gručenju. Zgoraj omenjeni algoritmi so implementirani v programski knjižnici za Python, ki je na voljo na: \url{ https://github.com/damir1407/label-propagation}. V nadaljevanju ocenimo učinkovitost teh treh metod gručenja omrežij na različnih sintetičnih in resničnih omrežjih ter predstavimo rezultate. Diplomsko nalogo zaključimo s povzetkom predstavljenih metod in predlogi za prihodnje delo.
|
| Ključne besede: | Kompleksno omrežje, Odkrivanje skupin, Izmenjava oznak, Konsenzno gručenje, Programska knjižnica |
|---|
