Primjena teorije grafova u analizi društvenih mreža

undergraduate thesis

• Title (english): Application of graph theory in social network analysis
• Author: David Iveković
• Mentor: Josipa Pina Milišić (mentor)
• Committee member: Josipa Pina Milišić (predsjednik povjerenstva)
• Committee member: Andrea Aglić Aljinović (član povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-30, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Analiza društvene mreže postupak je koji nam daje bolje razumijevanje određene mrežne strukture te je široko primjenjiv u različitim područjima kao što su marketing, biologija, informacijska sigurnost... Prilikom analize društvene mreže često se javlja problem identifikacije najvažnijih vrhova. U tu svrhu promatrali smo algoritme kao što su centralnost stupnja vrha, centralnost bliskosti, centralnost središnjeg položaja, centralnost svojstvenog vektora te PageRank centralnost. Za svaku centralnost dali smo mane i prednosti te smo došli do zaključka da nam centralnost svojstvenog vektora te PageRank centralnost daju najbolju informaciju o važnosti pojedinog vrha u mreži.
U društvenoj mreži vrlo je bitno podijeliti korisnike u neke manje zajednice kako bi obuhvatili ljude sa istim interesima i ponašanjima. Prošli smo kroz algoritme detekcije klika, Louvainov algoritam te Girvan-Newman alogoritam. Nakon što smo usporedili algoritme te istaknuli njihove prednosti i mane mogli smo doći do zaključka da će nam najčešće Louvainov algoritam dati najbolju podjelu mreže na zajednice.

Abstract (english)

Social network analysis is a procedure that gives us a better understanding of a certain network structure and is widely applicable in various fields such as marketing, biology, information security... When analyzing a social network, the problem of identifying the most important nodes often arises. For this purpose, we observed algorithms such as vertex degree centrality, closeness centrality, betweenness centrality, eigenvector centrality and PageRank centrality. For each centrality, we gave disadvantages and advantages, and we came to the conclusion that the centrality of the eigenvector and the PageRank centrality give us the best information about the importance of an individual vertex in the network.
In a social network, it is very important to divide users into smaller communities in order to include people with the same interests and behaviors. We went through clique detection algorithm, the Louvain algorithm and the Girvan-Newman algorithm. After comparing the algorithms and highlighting their advantages and disadvantages, we could come to the conclusion that the Louvain algorithm will most often give us the best division of the network into communities.

• Keywords: teorija grafova; društvene mreže; centralnost; detekcija zajednica
• Keywords (english): graph theory; social networks; centrality; community detection
• Language: croatian
• URN:NBN: urn:nbn:hr:168:693581
• 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: 2023-07-13 10:07:48