Komparativna analiza algoritama za otkrivanje zajednica u društvenim mrežama

diplomski rad

• Naslov (engleski): Comparative Analysis of Community Detection Algorithms in Social Networks
• Autor: Petar Ilijašić
• Mentor: Siniša Srbljić (mentor)
• Član povjerenstva: Siniša Srbljić (predsjednik povjerenstva)
• Član povjerenstva: Goran Delač (član povjerenstva)
• Član povjerenstva: Marin Šilić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2017-07-04, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

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.

Sažetak (engleski)

The early 1990s of the 20. the century is marked as begining of the development of social networks. Home computers have become part of every household, bringing the number of users on social networks grew more and more. The development of technology, the home computers became capable of producing a large amount of data. The first social networks were in the form of a platform for communication, while today's social networks have achieved a great user capacity and production data, different semantics. The data can describe the personal preferences of the user, information about the education and the like. This situation has led to the problem of grouping large amounts of data with regard to the criteria that you want. Manually processing large amounts of data is time-consuming and exhaustively. Currently the most widely used algorithms for detecting communities in social networks have Edge, propagation betweeness Label, Fastgreedy, Walktrap, Spinglass, Infomap, the Leading eigenvector and Multilevel. The speed, the accuracy of the detected number of communities and modularity are the values that are observed for each algorithm. The algorithms are tested over the computer-generated networks and social network with social platform Facebook. For computer generated social networks it has been used Girvan-Newman's evaluation system and its generalization, Lancichinetti-Fortunato-Radicchi evaluation system. After conducting the test concluded that the algorithms of Multilevel and Walktrap the best algorithms according to their working properties. The worst performance was showed by Spinglass and Infomap algorithms due to lack of accuracy of the data, despite the short run time. On actual social network Spinglass shows a good performance, but I can carry out calculations of graphs with isolated nodes. An Edge betweeness algorithm requires most of the time, and the quality of the performance depend on the complexity of the graph, i.e., the greater the number of nodes, it is less accurate. Knowledge of the General behaviour of the algorithm against large data set allows scholars a quality way of work and a clever selection of who will help him when he met with a large data set, which from day to day, the development of technology is getting bigger.

• Ključne riječi: zajednica; otkrivanje; algoritam; podaci; analiza; usporedba
• Ključne riječi (engleski): community; detection; algorithm; data; analysis; comparison
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:430758
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-13 20:57:24