20.500.12556/RUL-108344 Primerjalna analiza metod za odkrivanje skupnosti v usmerjenih omrežjih magistrsko delo Comparative analysis of methods for community detection in directed networks Magistrsko delo sodi na področje analize omrežij in obravnava problem odkrivanja skupnosti v omrežjih. Rešitev tega problema igra ključno vlogo pri analizi in razumevanju strukture velikih omrežij. Posebno pozornost posvetimo upoštevanju smeri povezav pri odkrivanju skupnosti. V praksi so smeri povezav, zaradi težavnosti obravnave, pogosto zanemarjene, kar lahko vodi do izgube pomembnih informacij, ki jih vsebujejo usmerjena omrežja. Podrobna analiza problema na intuitivnem kot tudi formalnem nivoju podaja bralcu celosten pregled problema in obstoječih metod za njegovo reševanje. Poleg obravnave usmerjenosti, dodatno težo problema predstavlja nejasna definicija skupnosti kot tudi naloge odkrivanja skupnosti. S pomočjo nekaj glavnih analiziranih pristopov reševanja raziskujemo razsežnosti definicije skupnosti. Dodatno predstavimo še nekaj skrbno izbranih metod: Louvain, Leiden, Infomap in OSLOM, pri vsaki pa del opisa namenimo prilagoditvi metode za upoštevanje smeri in uteži povezav. Pomemben del dela predstavlja empirična primerjava analiziranih metod s pomočjo umetno generiranih in realnih omrežij. Primerjava je izvedena na različnih nivojih, in sicer metode primerjamo na podlagi števila odkritih skupnosti, točnosti, stabilnosti ter modularnosti. In this work we present an important part of network analysis, the problem of community detection. Hidden community structure, which we aim to reconstruct using community detection methods, contains important information about the underlying graph structure. The main focus of this work is to analyze the consideration of edge direction, which is usually ignored because of its complicated nature. We offer an exhaustive review of the problem and corresponding methods on intuitive as well as on formal level. An additional difficulty we face is the unclear definition of the problem. We explore various views of the problem definition with the detailed analysis including the presentation of the main approaches dealing with the problem. Additionally, we focus on four different methods, each dealing with directed and weighted networks on its own way. Methods we include are the well-known Louvain method, Leiden, Infomap and OSLOM. An important part of the work is the empirical comparative analysis of the presented methods based on a number of detected communities, accuracy, stability and value of modularity in synthetic as well as in real networks. struktura skupnosti skupnost razbitje usmerjena omrežja modularnost optimizacija community structure community partition directed networks modularity optimization true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2019-06-28 13:34:30 2019-06-28 13:34:37 2024-05-30 11:11:49 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.1 96075 18665049 760.pdf 760.pdf 1 F6C9632767DC4551EF8146B9B5363660 7cbeeac87cfa15ab5f944c4faad08172b0ab77cfc6f13eb9b3dec46439773c42 a020beec-a1b6-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=119300 762.pdf 762.pdf 1 7AD65310F665A7BB5F909738FB7FD5C1 f48a33a9ddb18f05177256f1c58d7cb99ccb5c35c50b53aee6da6ed0ba6dca22 a02f011e-a1b6-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=119301 Fakulteta za matematiko in fiziko 0 0 0