Naslov
Komparativna analiza algoritama za otkrivanje zajednica u društvenim mrežama
(Comparative Analysis of Community Detection Algorithms in Social Networks)

Autori
Ilijašić, Petar

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
04.07

Godina
2017

Stranica
68

Mentor
Srbljić, Siniša

Neposredni voditelj
Delač, Goran

Ključne riječi
zajednica ; otkrivanje ; algoritam ; podaci ; analiza ; usporedba
(community ; detection ; algorithm ; data ; analysis ; comparison)

Sažetak
Početkom devedesetih godina 20. stoljeća je započeo razvoj društvenih mreža. Kućna računala su postala dio svakog kućanstva, čime je broj korisnika na društvenim mrežama sve više rastao. Razvojem tehnologije, kućna računala su postala sposobna proizvoditi veliku količinu podataka. Prve društvene mreže su bile u obliku platformi za komunikaciju, dok su današnje društvene mreže ostvarile veliki kapacitet korisnika te proizvodnju podataka različite semantike. Podaci mogu opisivati osobne preference korisnika, podatke o obrazovanju i slično. Takvo stanje je dovelo do problema grupiranja velike količine podataka s obzirom na željene kriterije. Ručno procesuiranje velike količine podataka je dugotrajno i iscrpno. Trenutno najkorišteniji algoritmi za detekciju zajednica u društvenim mrežama su Edge betweeness, Label propagation, Fastgreedy, Walktrap, Spinglass, Infomap, Leading eigenvector i Multilevel. Brzina, točnost otkrivenog broja zajednica i modularnosti su vrijednosti koje su promatrane za svaki algoritam. Algoritmi su testirani nad računalno generiranim mrežama i društvenoj mreži sa društvene platforme Facebook. Pri stvaranju računalno generiranih društvenih mreža se koristio Girvan-Newmanov sustav vrednovanja te njegova generalizacija, Lancichinetti-Fortunato- Radicchi sustav vrednovanja. Nakon provođenja testiranja je zaključeno da su algoritmi Multilevel i Walktrap najbolji algoritmi prema njihovim radnim svojstvima. Najlošija radna svojstva su pokazala algoritmi Spinglass i Infomap zbog nedostatka točnosti podataka, unatoč kratkom vremenu izvođenja. Na stvarnoj društvenoj mreži Spinglass pokazuje dobra radna svojstva, ali ne može provoditi izračune nad grafovima sa izoliranim čvorovima. Algoritam Edge betweeness zahtjeva najviše vremena, a kvaliteta radnih svojstava ovise o kompleksnosti grafa, odnosno što je veći broj čvorova, to je manje točan. Poznavanje općeg načina ponašanja algoritma nad velikim skupom podataka omogućuje znanstvenicima kvalitetan način rada te pametan odabir koji će mu pomoći kada se susreće sa velikim skupom podataka, koji iz dana u dan razvojem tehnologije postaje sve veći.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA