Search

Analiza društvenih mreža postala je vrlo dinamično i unosno područje pojavom online društvenih mreža i povećanjem kapaciteta za njihovu obradu. Otkrivanje zajednica jedno je od najvažnijih područja unutar analize društvenih mreža. U ovom radu, predstavljen je pojam društvene mreže, njene karakteristike, pojam zajednice u kontekstu društvenih mreža i problematika procjene njihove kvalitete. Nadalje, napravljena je usporedba Girvan-Newman, Label Propagation i Clauset-Newman-Moore algoritama za otkrivanje zajednica. Analiza je provedena u dva dijela: prvo na umjetno generiranim mrežama proizvedenih Lancichinetti-Fortunato-Radicchi metodom, a potom na stvarnim podacima s društvene mreže Twitter. The arrival of online social networks and the increase in the capacity to process them has caused social network analysis to become a very dynamic and lucrative field. Community detection is one of the most important areas of social network analysis. This thesis presents the notion of a social network, its characteristics, the notion of community in the context of social networks and the problem of assessing their quality. Furthermore, a comparison of Girvan-Newman, Label Propagation and Clauset-Newman-Moore community detection algorithms was made. The analysis was performed in two parts: first on artificially generated networks produced by the Lancichinetti-Fortunato-Radicchi benchmark, and then on real data from the social media network Twitter.

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.