Community Detection in Social Networks Using the Igraph Library

Jedan od najvažnijih zadataka u analizi društvenih mreža jest otkrivanje zajednica s kohezivnim grupama aktora koji su sličniji jedni drugima nego ostalim aktorima u mreži. Algoritmi otkrivanja zajednica su vrlo često korišteni u analizi svojstava društvenih mreža. U ovome radu, osam algoritama otkrivanja zajednica koji su implementirani u knjižnici igraph su vrednovani i testirani na šest skupova podataka koji predstavljaju mreže iz stvarnog svijeta. Algoritmi su uspoređeni koristeći metrike kvalitete (npr. modularnost, provodnost) i također metrike sličnosti (npr. normalizirana zajednička informacija) ako je poznata prava struktura zajednica. Nadalje, pokazana je implementacija nekoliko metrika kvaliteta i sličnosti za igraph paket za programski jezik Python. Analiza pokazuje da Multilevel algoritam daje najbolje rezultate sveukupno, a Leading eigenvector algoritam najgore.One of the most important tasks of social network analysis is to detect communities with cohesive group of actors who are more similar to each other than to the other actors in the network. Community detection algorithms are widely used to analyze the properties of social networks. In this thesis, eight community detection algorithms which are implemented in igraph library are evaluated and tested on six datasets representing real-world networks. The algorithms are compared based on quality metrics (e.g. modularity, conductance), and also similarity metrics (e.g. normalized mutual information) if the ground-truth communities are known. Furthermore, implementation of several quality and similarity metrics for igraph package for Python is shown. The study reveals that the Multilevel algorithm obtains the best results overall, while Leading eigenvector algorithm obtains the worst one