20.500.12556/DKUM-70968 Implementacija metod iskanja najkrajše poti za optimizacijo povezovanja v socialnih omrežjih Implementation of the shortest path problem methods for edge optimization in social networks V magistrskem delu predstavljamo problem iskanja najkrajše poti v socialnih omrežjih na podlagi pregleda, analize in implementacije metod iskanja najkrajše poti. Izdelan je bil sistematičen pregled literature kot podlaga za identificiranje najpogosteje uporabljenih metod iskanja najkrajše poti v analizi socialnih omrežij. Predstavljena je implementacija dveh poglavitnih metod iskanja najkrajše poti: Dijkstrov in Bellman-Fordov algoritem. Na podlagi implementacije sta bila izvedena eksperiment učinkovitosti delovanja algoritmov in primerjalna analiza. Na praktičnem primeru realnega socialnega omrežja je prikazana uporaba tradicionalnih metod iskanja najkrajše poti za izračun metrik v analizi socialnih omrežij. Ugotovljeno je bilo, da se Dijkstrov algoritem zaradi preprostejše implementacije izvaja hitreje kot Bellman-Fordov algoritem. Na velikih socialnih omrežjih se za hitrejše iskanje najkrajše poti uporabljajo hevristični pristopi in združevanje vozlišč v skupine. Prav tako Dijkstrov in Bellman-Fordov algoritem za iskanje najkrajše poti v socialnih omrežjih ne podpirata nekaterih vrst komunikacijskih povezav med uporabniki. In the master's thesis we present the shortest path problem in social networks based on the examination, analysis and implementation of the methods for finding the shortest path. A systematic literature overview has been elaborated as the basis for identifying the most commonly used methods for finding the shortest path in the social network analysis. The implementation of two main shortest path problem methods is presented: Dijkstra and Bellman-Ford algorithm. An experiment and a comparative analysis on the performance of algorithms was performed based on the algorithms implementation. Behaviour of the shortest path problem methods is shown with the practical example of the real social network for the calculation of the social network analysis metrics. It was found, that Dijkstra algorithm is faster, than Bellman-Ford algorithm, due to simpler implementation. On large social networks, heuristic approaches and grouping of nodes are used for faster search of shortest paths. Additionally, Dijkstra and Bellman-Ford algorithm, for finding the shortest path, do not support some types of communication edges between users in social networks. problem iskanja najkrajše poti Dijkstrov algoritem Bellman-Fordov algoritem socialno omrežje analiza socialnih omrežij Shortest path problem Dijkstra algorithm Bellman-Ford algorithm Social network Social network analysis true true false T. Hertiš Slovenski jezik Angleški jezik Magistrsko delo/naloga 2018-06-25 18:45:20 2018-07-17 14:17:46 2022-08-01 20:12:40 2019-07-11 18:25:53 2018 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.738.021(043.2) 21587222 URN:SI:UM:DK:WUE37ZEX MAG_Hertis_Tadej_2018.pdf MAG_Hertis_Tadej_2018.pdf 1 753F4785939D5D94BAD7D4CFAA3321FC bccc78aaedb963f699e433ed901ccedf5f1cbc58228d16911b25cb24c2b9188f 1afc632c-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/1f108d7d-84ba-4d60-bfd3-6f82d01347d0 https://dk.um.si/Dokument.php?lang=slv&id=126518 MAG_Hertis_Tadej_2018.zip MAG_Hertis_Tadej_2018.zip 1 059D2E62EC8BC70F4352F24F66045E26 573c604198a68ea2866c56f1199f97bfad9a2deedb14d982073f66259f2537fb 11c741de-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/c9acfaf9-ed4b-4eb3-a6a6-01ccebd01d10 https://dk.um.si/Dokument.php?lang=slv&id=126126 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0