prikaz prve stranice dokumenta Modificirani Girvan-Newmanov algoritam
Access restricted to students and staff of home institution
master's thesis
Modificirani Girvan-Newmanov algoritam
Split: University of Split, University of Split, Faculty of science, 2021. urn:nbn:hr:166:765024
Mandalinić, Katarina
University of Split
Faculty of Science
Department of Mathematics

Institutional repository: Repository of Faculty of Science

Cite this document

Mandalinić, K. (2021). Modificirani Girvan-Newmanov algoritam (Master's thesis). Split: University of Split, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:166:765024

Mandalinić, Katarina. "Modificirani Girvan-Newmanov algoritam." Master's thesis, University of Split, Faculty of Science, 2021. https://urn.nsk.hr/urn:nbn:hr:166:765024

Mandalinić, Katarina. "Modificirani Girvan-Newmanov algoritam." Master's thesis, University of Split, Faculty of Science, 2021. https://urn.nsk.hr/urn:nbn:hr:166:765024

Mandalinić, K. (2021). 'Modificirani Girvan-Newmanov algoritam', Master's thesis, University of Split, Faculty of Science, accessed 02 December 2024, https://urn.nsk.hr/urn:nbn:hr:166:765024

Mandalinić K. Modificirani Girvan-Newmanov algoritam [Master's thesis]. Split: University of Split, Faculty of Science; 2021 [cited 2024 December 02] Available at: https://urn.nsk.hr/urn:nbn:hr:166:765024

K. Mandalinić, "Modificirani Girvan-Newmanov algoritam", Master's thesis, University of Split, Faculty of Science, Split, 2021. Available at: https://urn.nsk.hr/urn:nbn:hr:166:765024

Metadata
TitleModificirani Girvan-Newmanov algoritam
Title (english)Modified Girvan-Newman algorithm
AuthorKatarina Mandalinić
MentorTanja Vojković (mentor)
Committee memberTanja Vojković (predsjednik povjerenstva)
Committee memberJurica Perić (član povjerenstva)
Committee memberAljoša Šubašić (član povjerenstva)
GranterUniversity of Split
Faculty of Science
(Department of Mathematics)
Split
Defense date and country2021-07-21, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
Kompleksne mreže često predstavljaju stvarne kompleksne sustave kao što su Internet i društvene mreže te zbog toga imaju mnoga netrivijalna topološka svojstva, a jedno od njih je struktura zajednice. Michelle Girvan i Mark Newman 2002. godine predstavljaju jedan od najznačajnijih algoritama u području detekcije zajednica u kompleksnim mrežama - Girvan-Newman algoritam. Predstavljeni algoritam u svakom koraku računa međupoloženost bridova i uklanja onaj brid kojemu je vrijednost međupoloženosti najveća. Cilj ovog rada je predstaviti modificirani Girvan-Newman algoritma u kojem se svi bridovi s najvećom međupoloženošću uklanjaju odjednom. Iterativno uklanjanje bridova dovodi do različitih podjela mreže na zajednice stoga se uvodi modularnost kao mjera kvalitete podjele mreže na zajednice. Algoritam je testiran na tri različite društvene mreže. Modifikacija dovodi do bržeg raspada mreže na zajednice, a rezultat ne ovisi o tome koji je brid uklonjen u prethodnom koraku već o samoj strukturi početne mreže.
Abstract (english)
Complex networks often represent real complex systems such as the Internet and social networks. As a result, they have many non-trivial topological features, one of which being community structure. In 2002, Michelle Girvan and Mark Newman proposed one of the most significant algorithms in the field of community detection - the Girvan-Newman algorithm. The algorithm calculates the edge betweenness and removes the edge with the highest betweenness value. The goal of this thesis is to present a modified version of the Girvan-Newman algorithm in which all edges with the highest betweenness value are removed at once. Iterative removal of edges leads to different divisions of a network into communities which is why modularity is used to measure the quality of division of a network into communities. The algorithm was tested on three different social networks. The algorithm modification leads to faster separation of the network into communities and result depends only on the structure of the initial network rather than which edge was removed in the previous step.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:166:765024
Study programmeTitle: Mathematics; specializations in: major in pure mathematics, major in computing, major in teaching, major in statistics and computing
Course: major in computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
Created on2021-08-25 11:43:03