Otkrivanje zajednica u društvenim mrežama primjenom knjižnice igraph

završni rad

• Naslov (engleski): Community Detection in Social Networks Using the Igraph Library
• Autor: Daniel Čuturilo
• Mentor: Goran Delač (mentor)
• Član povjerenstva: Goran Delač (predsjednik povjerenstva)
• Član povjerenstva: Marin Šilić (član povjerenstva)
• Član povjerenstva: Klemo Vladimir (č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: 2018-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: analiza zajednica; društvene mreže; zajednice; modularnost; knjižnica igraph; skupovi podataka
• Ključne riječi (engleski): community detection; social networks; communities; modularity; igraph library; datasets
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:862142
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-13 19:49:09