Community Detection in Social Networks Using Snap.py Library

U ovom završnom radu obrađen je jedan od najvažnijih problema u analizi društvenih mreža, a to je otkrivanje zajednica. Opisana je struktura društvenih mreža i mjere pomoću kojih se one analiziraju. Objašnjeni su postupci grupiranja u teoriji grafova. Proučeni su i opisani Girvan-Newman i Clauset-Newman algoritmi za otkrivanje nepreklapajućih zajednica u društvenim mrežama. Navedeni algoritmi provedeni su nad stvarnim skupom podataka te nad umjetno stvorenim skupom primjenom Watts-Strogatz modela te je dana usporedba njihovih rezultata. Opisan je pojam small-world fenomena te razvoj i svojstva Watts-Strogatz modela. This paper discusses one of the most important issuses in social network analysis which is community detection. A detailed description of a social network structure is given and measures used to analyze them. Different clustering techniques used in graph theory are also described. Steps of Girvan-Newman and ClausetNewman Moore algorithms for community detection are shown. The two algorithms are implemented in Snap.py library and evaluated on five real-world datasets as well as on generated random small-world graphs. Small-world phenomenon is described along with the evolution and characteristics of the Watts-Strogatz model.