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

undergraduate thesis

• Title (english): Community Detection in Social Networks Using the Igraph Library
• Author: Daniel Čuturilo
• Mentor: Goran Delač (mentor)
• Committee member: Goran Delač (predsjednik povjerenstva)
• Committee member: Marin Šilić (član povjerenstva)
• Committee member: Klemo Vladimir (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2018-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: analiza zajednica; društvene mreže; zajednice; modularnost; knjižnica igraph; skupovi podataka
• Keywords (english): community detection; social networks; communities; modularity; igraph library; datasets
• Language: croatian
• URN:NBN: urn:nbn:hr:168:862142
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 19:49:09