1126 KB0 KB0 KB2015Batagelj, VladimirPraprotnik, SelenaXVIII, 111 str., 30 cmCOBISSID:17296217PID:https://repozitorij.uni-lj.si/IzpisGradiva.php?id=95858URN:URN:NBN:SI:doc-EQJZZ19HslS. Praprotnikvisokošolska delaalgoritemalgorithmAnalizacentrality measureconnectivityČasovna omrežjačasovne količinečasovno omrežjeDisertacijedosegljivostgrouplatencymere pomembnostinasiljepolkolobarpotovalni časpovezanostiPython libraryPythonska knjižnicareachabilitysemiringskupinatemporal networktemporal quantityviolenceRazvoj skupin v omrežjih| doktorska disertacija|In the thesis we describe a new algebraic approach to the temporal network analysis based on the notion of temporal quantities. We define semirings for the analysis of temporal networks with zero latency and zero waiting time and semirings for the analysis of temporal networks where the latency is given. For temporal networks with zero latency and zero waiting time we present algorithms for the efficient operations with temporal quantities and for the computation of chosen centrality measures that are generalized cases of centrality measures for static networks. We describe the computation of degree, clustering coefficients, closeness, betweenness and recursive measures of centrality. We explain the eigenvector centrality, the Katz centrality measure, the Bonacich ?$\alpha$? and ?$(\alpha,\beta)$? centralities, the HITS (hubs and authorities) centrality, and the pageRank centrality. We define activity and attraction coefficients in temporal networks. Centrality measures allow us to identify groups of important vertices. With a review / comparison of the vertices from the groups we get an insight into their roles through time. We present the algorithm for computing the closure of a temporal network over an absorptive semiring and for computing the temporal reachability of nodes. We also describe the procedure for computing temporal weak and strong connectivity components using the appropriate closure. This approach can also be used for the analysis of groups that are determined by other equivalence relations on the given network. The described procedures are available as a Python library TQ. We tested the algorithms on real networks, the Franzosi's violence network and the Reuters terror news networkV disertaciji vpeljemo nov algebraičen pristop k analizi časovnih omrežij, ki temelji na časovnih količinah nad ustreznim polkolobarjem. Definiramo polkolobarje za analizo časovnih omrežij brez potovalnega in čakalnega časa in polkolobarje za analizo časovnih omrežij, ko potovalni in čakalni časi niso ničelni. Za omrežja brez potovalnih in čakalnih časov razvijemo algoritme za učinkovito računanje s časovnimi količinami in za izbrane mere pomembnosti, ki so posplošitve mer za analizo statičnih omrežij. Opišemo izračun stopnje vozlišč, nakopičenosti, dostopnosti in vmesnosti ter rekurzivnih mer pomembnosti. Razdelamo postopke za izračun mere pomembnosti glede na lastne vektorje sosednostne matrike omrežja, Katzove pomembnosti in Bonacichevih pomembnosti ?$\alpha$? in ?$(\alpha,\beta)$?. Opišemo tudi postopka HITS (kazala in viri) in pageRank. Definiramo dejavnost in privlačnost vozlišč. Mere pomembnosti nam omogočajo identifikacijo skupine najpomembnejših vozlišč omrežja in z njihovim pregledom / primerjavo vpogled v spreminjanje njihove vloge skozi čas. Povemo, kako izračunamo ovojnico nad absorpcijskimi polkolobarji in z njeno uporabo časovno dosegljivost. S pomočjo dosegljivosti izračunamo časovno razbitje na šibke in krepke komponente. Opisani pristop lahko uporabimo za analizo skupin, ki so določene s poljubno drugo časovno ekvivalenčno relacijo na danem omrežju. Opisani postopki so dostopni kot Pythonska knjižnica TQ. Algoritme preizkusimo na realnih omrežjih, Franzosijevem omrežju nasilja v Italiji in omrežju Reutersovih novic o terorističnem napadu 11. septembraTEXTvisokošolska delatheses and dissertationsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza v Ljubljani, Fakulteta za matematiko in fiziko