Fakulteta za raˇ cunalniˇ stvo in informatiko
Gaˇsper Kolbezen
Izdelava zbirke omreˇ zij slovenskega izvora
DIPLOMSKO DELO
UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE
RA ˇCUNALNIˇSTVO IN INFORMATIKA
Mentor : doc. dr. Jurij Miheliˇ c Somentor : doc. dr. Uroˇs ˇ Cibej
Dob, 2021
besedilo, slike, grafi in druge sestavine dela kot tudi rezultati diplomskega dela lahko prosto distribuirajo, reproducirajo, uporabljajo, priobˇcujejo javnosti in pre- delujejo, pod pogojem, da se jasno in vidno navede avtorja in naslov tega dela in da se v primeru spremembe, preoblikovanja ali uporabe tega dela v svojem delu, lahko distribuira predelava le pod licenco, ki je enaka tej. Podrobnosti licence so dostopne na spletni strani creativecommons.si ali na Inˇstitutu za intelektualno lastnino, Streliˇska 1, 1000 Ljubljana.
Izvorna koda diplomskega dela, njeni rezultati in v ta namen razvita program- ska oprema je ponujena pod licenco GNU General Public License, razliˇcica 3 (ali novejˇsa). To pomeni, da se lahko prosto distribuira in/ali predeluje pod njenimi pogoji. Podrobnosti licence so dostopne na spletni strani http://www.gnu.org/
licenses/.
Besedilo je oblikovano z urejevalnikom besedil LATEX.
Vrsta naloge: Diplomska naloga na univerzitetnem programu prve stopnje Raˇcunalniˇstvo in informatika
Mentor: doc. dr. Jurij Miheliˇc Somentor: doc. dr. Uroˇs ˇCibej Opis:
Zasnujte in realizirajte knjiˇznico realnih omreˇzij, ki imajo svoj izvor v slo- venskem prostoru. Razvijte orodja in uporabite ustrezne tehnologije, ki vam bodo omogoˇcile zajetje in preˇciˇsˇcenje zamiˇsljenih omreˇzij. Pri tem upora- bite prosto dostopne formate, da bodo omreˇzja uporabna ˇsirokemu krogu uporabnikov. Omreˇzja tudi analizirajte tako, da naraˇcunate pogosto upora- bljene parametre, s katerimi lahko dobimo boljˇsi vpogled v lastnosti omreˇzja.
Title: Construction of a collection of networks of Slovenian origin Description:
Design and implement a collection of real-life networks which originate in the Slovenian cultural space. Find and develop the necessary tools and appli- cations that will enable the compilation and refinement of the envisioned networks. Use open formats to make the results accessible to a large pool of possible users. Analyze the acquired networks by computing a set of com- monly used features that will give you a better insight into their structure.
Prav tako se zahvaljujem starˇsema za podporo in pomoˇc v ˇcasu ˇstudija.
Povzetek Abstract
1 Uvod 1
1.1 Ozadje in motivacija . . . 1
1.2 Pregled podroˇcja . . . 2
1.3 Struktura dokumenta . . . 3
2 Zbiranje omreˇzij 5 2.1 Grafi in omreˇzja . . . 5
2.2 Podatkovni formati . . . 7
2.3 Crpanje podatkov . . . .ˇ 14 2.4 Uporabljena orodja . . . 15
3 Izdelana omreˇzja 17 3.1 Omreˇzje Slovenskih ˇzeleznic . . . 17
3.2 Omreˇzje Ljubljanskega potniˇskega prometa . . . 19
3.3 Omreˇzji letalskega prometa . . . 21
3.4 Omreˇzje zaposlenih na Fakulteti za raˇcunalniˇstvo in informatiko . . . 25
3.5 Omreˇzje slovenskih startupov . . . 28
3.6 Omreˇzja slovenskih ˇsportnikov . . . 31
3.7 Omreˇzja spletnih strani . . . 33
3.10 Jezikovna omreˇzja . . . 49
4 Ovrednotenje dela 53
4.1 Konˇcni izdelek . . . 53 4.2 Analiza izdelanih omreˇzij . . . 54
5 Zakljuˇcek 67
Literatura 69
kratica angleˇsko slovensko
XML Extensible Markup Language Razˇsirljivi oznaˇcevalni jezik CSV Comma Separated Values Vrednosti, loˇcene z vejico ASCII American Standard Code for
Information Interchange
Ameriˇska standardna koda za izmenjavo informacij
API Application Programming In- terface
Aplikacijski programski vme- snik
JSON JavaScript Object Notation Objektni JavaScript zapis
Naslov: Izdelava zbirke omreˇzij slovenskega izvora Avtor: Gaˇsper Kolbezen
Matematiˇcni grafi so izredno zanimive matematiˇcne strukture, ker omogoˇcajo predstavitev podatkov, med katerimi obstajajo nekakˇsni odnosi oziroma po- vezave. V sklopu diplomskega dela bodo zbrani podatki iz okolja in iz njih sestavljenih ˇcim veˇc omreˇzij v obliki grafov, pri ˇcimer bo poudarek na slo- venskih omreˇzjih. Izdelana omreˇzja bodo zbrana v zbirki omreˇzij, ki bo vsebovala tako fiziˇcna kot tudi abstraktna omreˇzja. Konˇcni izdelek bo zbirka omreˇzij, predstavljenih v obliki grafov. Namen konˇcnega izdelka je pomoˇc drugim raziskovalcem in pedagogom, ki se ukvarjajo z grafi ali pa s podroˇcji, ki jih bodo pokrila izdelana omreˇzja.
Kljuˇcne besede: omreˇzja, grafi, teorija grafov, podatkovna baza.
Title: Diploma thesis template Author: Gaˇsper Kolbezen
Mathematical graphs are extremely interesting mathematical structures be- cause they allow a representation of data sets, in between the members of which, relations or connections exist. As part of this thesis, world data will be collected, and from it, as many networks as possible will be created in the form of graphs. The focus of these networks will be on Slovenian networks.
The created networks will also be collected in a database that will contain both physical and abstract networks. The final product will be a database of networks that are presented in the form of graphs. The purpose of the product is to help other researchers and educators that work with graphs or areas that the created networks cover.
Keywords: networks, graphs, graph theory, database.
Uvod
1.1 Ozadje in motivacija
Matematiˇcni graf je izredno zanimiva in uporabna matematiˇcna struktura, ki se vedno bolj uporablja tudi kot podatkovna strukutra za hrambo podatkov.
Nad grafi lahko namreˇc izvajamo veliko ˇstevilo operacij, med katerimi so nekatere edinstvene in znaˇcilne le za grafe. Eno izmed najbolj popularnih naˇcinov uporabe grafov izven samega podroˇcja matematike je modeliranje omreˇzij, predvsem fiziˇcnih, kot so na primer prometna omreˇzja.
Omreˇzja, ki so predstavljena z grafi imajo veˇc prednosti; zaradi same na- rave podatkovne strukture so idealna za enostavno vizualizacijo povezanih podatkov, saj se akterjem in povezavam med akterji lahko dodeljuje vredno- sti, kar predstavlja enostavno podajanje informacij o omreˇzju. Prav tako se lahko nad takˇsnimi omreˇzji izvaja simulacije in meritve, ki lahko koristijo veˇc podroˇcjem znanosti.
Namen diplomskega dela je zgraditi ˇcim veˇcjo zbirko omreˇzij, predsta- vljenih z grafi, pri ˇcemer bi bil poudarek na slovenskih omreˇzjih. Rezultati diplomskega dela bodo tako lahko koristili drugim raziskovalcem, ki se ukvar- jajo s podroˇcji grafov.
Izdelana omreˇzja sluˇzijo kot primeri grafov iz resniˇcnega sveta nad kate- 1
rimi se lahko izvaja, testira in optimizira operacije. Prav tako bodo rezultati v korist raziskovalcem iz podroˇcij, ki se nanaˇsajo na izdelana omreˇzja, pred- vsem tistim iz podroˇcja urbanistike, saj je veliko izdelanih omreˇzij narejenih na podlagi geografskih podatkov. Z izdelanimi omreˇzji bodo lahko izvajali simulacije in meritve nad resniˇcnimi omreˇzji.
1.2 Pregled podroˇ cja
Grafi se v povezavi z resniˇcnimi podatki uporabljajo na veˇc naˇcinov. Kot enega izmed primerov lahko navedemo modeliranje fiziˇcnih omreˇzij za po- trebe urbanistike. Nad takˇsnimi omreˇzji se nato izvajajo simulacije in meri- tve.
Praktiˇcnen primer uporabe takˇsnih omreˇzij predstavlja ˇclanek “Networks and Cities: An Information Perspective” [16], ki se ukvarja z zapletenostjo arhitekture mest glede na koliˇcino informacij potrebnih za navigacijo po njih.
Mestno omreˇzje so predstavili z grafom, kjer kriˇziˇsˇca predstavljajo toˇcke, ulice pa povezave med njimi. Enak tip omreˇzja je predstavljen tudi v diplomskem delu. Avtorji ˇclanka so nato nad temi grafi, ki predstavljajo naˇcrt mesta, iz- vajali operacije za prehajanje med vozliˇsˇci, s ˇcimer so lahko pridobili koliˇcino informacije, ki jo potrebujemo za navigacijo po mestu. Prav tako obstaja ve- liko drugih publikacij [1, 6, 10, 14], ki se ukvarjajo s podroˇcjem predstavitve in analize resniˇcnih omreˇzij s pomoˇcjo grafov.
Grafe, pridobljene iz resniˇcnih podatkov se prav tako uporablja za pre- izkuˇsanje in prilagajanje algoritmov, namenjenih analizi grafov [7, 21].
Zbiranje grafov, pridobljenih iz resniˇcnih podatkov prav tako ni nova ideja. Obstaja veˇc prosto dostopnih zbirk grafov. Med drugim ima manjˇso zbirke spletna stran programa Pajek [13], nekaj zbranih grafov ponuja repo- zitorij programa Gephi, obstaja pa tudi nekaj projektov, namenjenih prav temu podroˇcju. Med njimi bi izpostavili SNAP: Stanford Network Analysis Project [11], ki ponuja precej veliko zbirko raznih omreˇzij.
Na tem podroˇcju pa, kljub manjˇsi zbirki grafov s strani avtorjev pro-
grama Pajek, manjka slovenskih omreˇzij. Z namenom vsaj delne odprave te pomanjkljivosti je bilo v sklopu tega diplomskega dela zbranih nekaj sloven- skih omreˇzij.
1.3 Struktura dokumenta
Diplomsko delo je razdeljeno na pet delov, vsakemu izmed katerih je do- deljeno eno poglavje. Prvi del je vseboval uvod. V drugem poglavju je na kratko predstavljeno podroˇcje teorije grafov, podatkovni formati, ki so upora- bljeni za shranjevanje grafov in naˇcini pridobivanja podatkov za grafe. Prav tako so opisana orodja, ki smo jih uporabili pri izdelavi dplomskega dela.
V tretjem poglavju so predstavljena omreˇzja, izdelana v sklopu diplomskega dela in postopki njihove izdelave. ˇCetrto poglavje vsebuje predstavitev iz- delka in analizo ter primerjave izdelanih omreˇzij. Zadnje poglavje pa vsebuje povzetek rezultatov in zakljuˇcek.
Zbiranje omreˇ zij
2.1 Grafi in omreˇ zja
V sklopu diplomskega dela je bilo izdelanih veˇc slovenskih omreˇzij, katerih kljuˇcna znaˇcilnost je, da so predstavljena s strukturo matematiˇcnega grafa.
V matematiki se s to strukturo ukvarja podroˇcje teorije grafov [22]. Na tem podroˇcju je graf G definiran kot mnoˇzica vozliˇsˇc in povezav G = (V, E), kjer je V mnoˇzica vseh vozliˇsˇc in E mnoˇzica vseh povezav v grafu.
Struktura je najpogosteje predstavljena z diagramom toˇck oz. pik, ki predstavljajo vozliˇsˇca in ˇcrt, ki predstavljajo povezave. V naslednjem raz- delku bomo podali definicije nekaterih izrazov, na katerih temelji teorija gra- fov in ki so potrebni za razumevanje podroˇcja.
• Vozliˇsˇce
Vozliˇsˇce (ang. node) predstavlja toˇcko kjer se sreˇcajo povezave. V grafu predstavlja nekega akterja, stvar ali podatek, ki ga prikazujemo.
Za boljˇse razumevanje lahko vozliˇsˇcu dodamo oznake, na primer ˇcrko abecede. V vizualnem modelu grafa je predstavljen s piko.
• Povezava
Povezava (ang. edge) je matematiˇcni izraz za par vozliˇsˇc v grafu. Iz enega vozliˇsˇca lahko izhaja veˇc povezav. Brez vozliˇsˇca ni mogoˇce obli-
5
kovati povezave. Za povezavo morata biti definirana zaˇcetno in konˇcno vozliˇsˇce. V grafiˇcni predstavitvi grafa je povezava predstavljena s ˇcrto, ki povezuje dve vozliˇsˇci.
• Sosednost
V grafu sta dve vezliˇsˇci sosedni, ˇce se med njima nahaja povezava.
Tu sosednost vozliˇsˇc ohranja ena sama povezava, ki povezuje ti dve vozliˇsˇci. Podobno sta dve povezavi sosedni, ˇce se med njima nahaja skupno vozliˇsˇce. Tu sosednost povezav vzdrˇzuje enojno vozliˇsˇce, ki povezuje povezavi.
• Usmerjenost grafa
Graf je usmerjen, kadar imajo njegove povezave vhodno in izhodno vozliˇsˇce. Takˇsni grafi definirajo ne le povezave med vozliˇsˇci, ampak tudi smer povezave.
• Stopnja vozliˇsˇca
Stopnja posameznega vozliˇsˇca je definirana kot ˇstevilo vozliˇsˇcu sosednih vozliˇsˇc.
• Uteˇz
Grafe se lahko razˇsiri z vpeljavo uteˇzi, ki so pozitivna ˇstevila prirejena vsaki povezavi. Uteˇzi lahko predstavljajo moˇc povezave, neko vrednost ali pa imajo vnaprej opredeljen arbitraren pomen.
• Zanka
Zanka je povezava, ki povezuje vozliˇsˇce samo s seboj.
• Pot
Pot v grafu je definirana kot konˇcno zaporedje vozliˇsˇc, ki je podano z zaporedjem povezav tako, da sta vsaki dve zaporedni vozliˇsˇci sosedni.
V posamezni poti se nobeno izmed vozliˇsˇc ne sme ponoviti.
2.2 Podatkovni formati
Dandanes se za hranjenje grafov uporablja veˇc razliˇcnih podatkovnih forma- tov, ki se med seboj razlikujejo po namenu, ˇstevilu ponujenih funkcionalnosti in velikosti datoteke. Te razlike med formati so pravzaprav tudi glavni ra- zlog za obstoj le teh. Razliˇcni grafi imajo razliˇcno predstavljene podatke, ki zahtevajo doloˇcene funkcionalnosti.
Graf, ki vsebuje poimenovana vozliˇsˇca ali pa uteˇzi ne more biti v ce- loti shranjen v formatu, ki je namenjen samo hrambi strukture in ne pod- pira dodatnih podatkov, kot so imena vozliˇsˇc, med tem ko doloˇceni formati omogoˇcajo hrambo precej veliko dodatnih podatkov, kot je na primer hramba koordinat vozliˇsˇc za vizualizacijo grafa.
V grobem lahko podatkovne formate za hrambo in predstavitev gra- fov delimo na tekstovne in binarne formate, pri ˇcimer so tekstovni veliko bolj razˇsirjeni zaradi preprostosti in moˇznosti dodatnih funkcionalnosti. V sledeˇcem razdelku je opisanih nekaj bolj pogosto uporabljenih formatov.
2.2.1 Format GraphML
GraphML [4] je eden izmed najbolj razˇsirjenih podatkovnih formatov. Da- toteke tega formata uporabljajo konˇcnico .graphml. Format je zasnovan na razˇsirljivem oznaˇcevalnem jeziku XML in je tako vizualno podoben drugim formatom, ki so prav tako osnovani na jeziku XML.
Format podpira usmerjene, neusmerjene in meˇsane grafe, oznake in druge atribute za vozliˇsˇca, ter povezave, hierarhiˇcne grafe, hipergrafe, reference na zunanje podatke in hranjenje veˇc grafov v eni datoteki. Ena veˇcjih prednosti formatov na osnovi jezika XML je lahka berljivost datoteke s strani raznih vmesnikov zaradi razˇsirjenosti jezika XML.
Datoteka v formatu GraphML se priˇcne z definicijo uporabljene verzije XML in deklaracijo vrste dokumenta “graphml”, nato se z objektom “graph”
priˇcne graf, znotraj katerega so nato podani objekti vozliˇsˇc “node” in povezav
“edge” s svojimi atributi.
Primer datoteke lahko vidimo na sliki 2.1. Takˇsna oblika je univerzalna za vse XML formate.
<?xml v e r s i o n =”1.0” e n c o d i n g=”UTF−8”?>
<graphml xmlns=”h t t p : / / graphml . g r a p h d r a w i n g . o r g / xmlns”>
<key a t t r . name=” l a b e l ” a t t r . t y p e=” s t r i n g ” f o r =”node ” i d =” l a b e l ”/>
<key a t t r . name=”Edge L a b e l ” a t t r . t y p e=” s t r i n g ” f o r =”e d g e ” i d =” e d g e l a b e l ”/>
<key a t t r . name=”w e i g h t ” a t t r . t y p e=”d o u b l e ” f o r =”e d g e ” i d =”w e i g h t ”/>
<key a t t r . name=”x ” a t t r . t y p e=” f l o a t ” f o r =”node ” i d =”x”/>
<key a t t r . name=”y ” a t t r . t y p e=” f l o a t ” f o r =”node ” i d =”y”/>
<gr aph e d g e d e f a u l t =” u n d i r e c t e d ”>
<node i d =”0”>
<d a t a key=” l a b e l ”>node 1</data>
<d a t a key=”x ”>3.0065308</ data>
<d a t a key=”y ”>380.04883</ data>
</node>
<node i d =”1”>
<d a t a key=” l a b e l ”>node 2</data>
<d a t a key=”x”>−183.51862</ data>
<d a t a key=”y”>−187.05307</ data>
</node>
<node i d =”2”>
<d a t a key=” l a b e l ”>node 3</data>
<d a t a key=”x ”>380.53967</ data>
<d a t a key=”y”>−358.3532</ data>
</node>
<e d g e i d =”0” s o u r c e =”0” t a r g e t =”1”>
<d a t a key=”w e i g h t ”>1.0</ data>
</edge>
<e d g e i d =”1” s o u r c e =”0” t a r g e t =”2”>
<d a t a key=”w e i g h t ”>1.0</ data>
</edge>
<e d g e i d =”2” s o u r c e =”1” t a r g e t =”2”>
<d a t a key=”w e i g h t ”>1.0</ data>
</edge>
</graph>
</graphml>
Slika 2.1: Neusmerjen trikoten graf v GraphML formatu
2.2.2 Format GEXF
GEXF [8] (Graph Exchange XML Format) je, prav tako kot GraphML, osno- van na jeziku XML in mu je tako precej podoben, kar je razvidno is slike 2.2.
Datoteke tega formata uporabljajo konˇcnico .gexf. Zasnovan je bil kot ura- dni format orodja Gephi, ki je eden izmed najbolj popularnih programov za analizo grafov.
Format je nastal leta 2007, kar pomeni, da je eden izmed najnovejˇsih formatov in kot tak poskuˇsa nadgraditi obstojeˇce formate. To poskuˇsa s poenostavitvijo doloˇcenih funkcionalnosti in razˇsiritvijo drugih.
Od formata GraphML se razlikuje predvsem v omogoˇcanju samostojne definicije metapodatkov, podpori dinamiˇcnih funkcionalnosti in odsotnosti nekaterih drugih dodatnih funkcionalnosti [8, 17].
2.2.3 Format GML
GML [9] (Graph Modelling Language) je preprost tekstovni format, ki je bil ustvarjen z namenom, da bi postal univerzalen format za shranjevanje grafov.
Datoteke formata uporabljajo konˇcnico .gml, format pa ima sintakso, ki je preprostejˇsa od tistih, ki jih uporabljajo formati, zasnovani na jeziku XML. Ima sposobnost predstavitve arbitrarnih podatkovnih struktur in nima potrebe po specifiˇcnem vrstnem redu deklaracij, kar omogoˇca preprosto do- dajanje objektov.
Format GML pa zaradi preprostosti ne podpira raznih dodatnih funkcio- nalnosti, ki jih omogoˇcajo XML formati [17]. Vsak graf se priˇcne z deklaracijo objekta “graph”, znotraj katere se nahajajo morebitni dodatni podatki in pa objekti vozliˇsˇc “node” in povezav “edge” s svojimi atributi. Primer datoteke formata GML je podan na sliki 2.3.
<?xml v e r s i o n =”1.0” e n c o d i n g=”UTF−8”?>
<g e x f xmlns=”h t t p : / /www. g e x f . n e t / 1 . 3 ” v e r s i o n =”1.3”
xmlns : v i z =”h t t p : / /www. g e x f . n e t / 1 . 3 / v i z ”
xmlns : x s i =”h t t p : / /www. w3 . o r g / 2 0 0 1 /XMLSchema−i n s t a n c e ” x s i : s c h e m a L o c a t i o n=”h t t p : / /www. g e x f . n e t / 1 . 3
h t t p : / /www. g e x f . n e t / 1 . 3 / g e x f . xsd”>
<meta l a s t m o d i f i e d d a t e =”2021−08−17”>
<c r e a t o r>Gephi 0.9</ c r e a t o r>
<d e s c r i p t i o n></ d e s c r i p t i o n>
</meta>
<gr aph d e f a u l t e d g e t y p e =” u n d i r e c t e d ” mode=” s t a t i c ”>
<nodes>
<node i d =”0” l a b e l =”node 1”>
<v i z : s i z e v a l u e =”10.0”></ v i z : s i z e>
<v i z : p o s i t i o n x = ” 3 . 0 0 6 5 3 0 8 ” y =”380.04883”> </ v i z : p o s i t i o n>
</node>
<node i d =”1” l a b e l =”node 2”>
<v i z : s i z e v a l u e =”10.0”></ v i z : s i z e>
<v i z : p o s i t i o n x =”−183.51862” y=”−187.05307”></ v i z : p o s i t i o n>
</node>
<node i d =”2” l a b e l =”node 3”>
<v i z : s i z e v a l u e =”10.0”></ v i z : s i z e>
<v i z : p o s i t i o n x = ” 3 8 0 . 5 3 9 6 7 ” y=”−358.3532”></ v i z : p o s i t i o n>
</node>
</nodes>
<e d g e s>
<e d g e i d =”0” s o u r c e =”0” t a r g e t =”1”></edge>
<e d g e i d =”1” s o u r c e =”0” t a r g e t =”2”></edge>
<e d g e i d =”2” s o u r c e =”1” t a r g e t =”2”></edge>
</e d g e s>
</graph>
</ g e x f>
Slika 2.2: Neusmerjen trikoten graf v GEXF formatu
gr aph [
C r e a t o r ” Gephi ” d i r e c t e d 0 node [
i d 0
l a b e l ” node 1”
] node [
i d 1
l a b e l ” node 2”
] node [
i d 2
l a b e l ” node 3”
] e d g e [
i d 0 s o u r c e 0 t a r g e t 1 ]
e d g e [ i d 1 s o u r c e 0 t a r g e t 2 ]
e d g e [ i d 2 s o u r c e 1 t a r g e t 2 ]
]
Slika 2.3: Neusmerjen trikoten graf v GML formatu
2.2.4 Format CSV
CSV [18] je osnoven format, ki hrani le odnose med entitetami. Datoteke tega formata uporabljajo konˇcnico .csv, format pa je razˇsirjen predvsem zaradi preprostosti in univerzalnosti, saj se ga lahko pridobi iz kakrˇsnihkoli vrstiˇcnih podatkov, podatkovnih baz ali poroˇcil Microsoft Excel.
Sintaksa formata predstavlja tabelo v tekstovni obliki. Posamezne vrstice tabele so predstavljene kot vrstice v tekstovni datoteki, posamezne celice v vrstici pa so v datoteki med seboj loˇcene s posebnim znakom, najveˇckrat vejico.
V tabeli, ki jo predstavljamo, je prva celica v prvi vrstici prazna, nato pa zaporedno sledijo imena vozliˇsˇc. Prav tako so vozliˇsˇca v enakem vrstnem redu navedena v prvem stolpcu. Preostale celice v tabeli predstavljajo matriko sosednosti, kjer so navedene vse uteˇzi povezav med vozliˇsˇci. ˇCe vozliˇsˇci nista povezani, se tako v celici nahaja ˇstevilka niˇc. Primer datoteke grafa v CSV formatu se nahaja na sliki 2.4.
; 0 ; 1 ; 2 0 ; 0 ; 1 ; 1 1 ; 1 ; 0 ; 1 2 ; 1 ; 1 ; 0
Slika 2.4: Neusmerjen trikoten graf v CSV formatu
2.2.5 Format Pajek NET
Pajek NET [13] je format, ki je bil ustvarjen za uporabo s programom Pajek [2]. Je tekstovni format in datoteke formata uporabljajo konˇcnico .net. For- mat podpira le izbrane dodatne funkcionalnosti, saj je bil narejen za hra- njenje velikih grafov. Poleg osnovnih podatkov o grafih podpira le hrambo podatkov za vizualizacijo in hrambo dinamiˇcnih grafov.
Kot ˇze omenjeno, je Pajek NET precej preprost in uporabniku prijazen format. Vsak del datoteke se zaˇcne z deklaracijo razdelka. Vozliˇsˇca se zaˇcnejo
z oznaˇcbo “*Vertices”, ki ji sledi ˇstevilo vozliˇsˇc. Nato so v vrsticah lahko navedene vse oznake vozliˇsˇc.
Povezave se zaˇcnejo z oznaˇcbo “*Edges”, ki ji v vrsticah sledijo posamezni pari povezanih vozliˇsˇc z neobveznimi dodatnimi atributi. Primer datoteke Pajek NET je na sliki 2.5.
∗V e r t i c e s 3
1 ” node 1” 3 . 0 0 6 5 3 0 8 3 8 0 . 0 4 8 8 3 0 . 0 2 ” node 2” −183.51862 −187.05307 0 . 0 3 ” node 3” 3 8 0 . 5 3 9 6 7 −358.3532 0 . 0
∗Edges 1 2 1 . 0 1 3 1 . 0 2 3 1 . 0
Slika 2.5: Neusmerjen trikoten graf v formatu Pajek NET
2.2.6 Formata graph6 in sparse6
Graph6 in sparse6 [12] sta formata, ki ju je ustvaril Brendan McKay za hrambo neusmerjenih grafov na izredno kompakten naˇcin z uporabo ASCII znakov. Datoteke formata graph6 uporabljajo konˇcnico .g6, datoteke formata sparse6 pa .s6.
Graph6 je primeren za manjˇse grafe in veˇcje goste grafe. Sparse6 je bolj prostorsko uˇcinkovit za zelo velike redke grafe. Formata sta binarna, saj zakodirata velikost grafa in zgornji trikotnik matrike sosednosti kot bitni vektor, ki je nato pretvorjen v zaporedje ASCII znakov.
Zaradi narave formatov ta dva formata ne podpirata nobenih dodatnih funkcionalnosti, razen hrambe veˇc grafov v eni datoteki, kjer vsaka vrstica predstavlja en graf.
V formatu graph6 je neusmerjen trikoten graf predstavljen preprosto z ASCII zapisom ”Bw”.
2.3 Crpanje podatkov ˇ
Kljuˇcen del postopka izdelave omreˇzij je ˇcrpanje podatkov za omreˇzja (ang.
data scraping). Crpanje podatkov v tem kontekstu predstavlja postopekˇ ali metodo s katero se pridobi relevantne podatke iz izhoda, ki je rezultat nekega programa. Kar razlikuje postopek ˇcrpanja podatkov od obiˇcajnega razˇclenjevanja izhoda je, da se pri ˇcrpanju podatkov, te pridobiva iz vira, ki je namenjen prikazu podatkov uporabniku. Takˇsni podatki so tako predsta- vljeni na naˇcine, ki niso primerni za obravnavo v programih.
Najbolj osnovna in enostavna oblika ˇcrpanja podatkov je roˇcna. Ljudje ˇcrpamo podatke vsak dan, ko iz raznih virov; poroˇcil, ˇclankov ali spletnih strani kopiramo podatke za naˇso uporabo. Takˇsna oblika ˇcrpanja pa je zelo poˇcasna in neuˇcinkovita. Zato se izraz ˇcrpanje podatkov skoraj vedno nanaˇsa na avtomatizirano obliko ˇcrpanja, kjer za izvajanje tega uporabljamo razna orodja in programe, namenjene temu.
Kot preprost primer lahko vzamemo eno izmed oblik ˇcrpanja podatkov, kar je t.i. spletno ˇcrpanje (ang. web scraping), v sklopu ˇcesar uporabimo nek program za pridobivanje podatkov iz spletnih strani. Recimo, da ˇzelimo pridobiti seznam vseh slovenskih upravnih enot. Ti podatki so dostopni na spletni strani drˇzavne uprave, a so podani v uporabniku prijaznem formatu, ki pa ni primeren za izdelavo seznama.
V tem primeru se lahko posluˇzimo spletnega ˇcrpanja. Ustvarimo program, ki na spletni strani poiˇsˇce vse elemente “div”, ki imajo razred “item-title”
in se nahajajo znotraj razreda “organisation-list-item”. Nato znotraj teh elementov prebere vsebino elementa “h3”, ki vsebuje ime upravne enote in te podatke shrani v seznam. Pri izdelavi nekaterih omreˇzij smo se posluˇzili prav takˇsnega naˇcina ˇcrpanja podatkov.
Pri izdelavi diplomske naloge je bilo ˇcrpanje podatkov eden izmed treh glavnih delov postopka pri ustvarjanju omreˇzij. Druga dva sta bila doloˇcevanje in izbira omreˇzij za izdelavo in njihova izdelava. Pri izbiranju omreˇzij, ki jih bomo izdelali je bila dosegljivost podatkov za ˇcrpanje velik faktor. Veliko idej
je bilo zavrˇzenih zaradi javno nedostopnih podatkov, v doloˇcenih primerih pa ˇcrpanje podatkov sploh ni bilo potrebno, saj so bili ti ˇze podani v primerni obliki.
2.4 Uporabljena orodja
Pri izdelavi omreˇzij je bil v veliki meri uporabljen programski jezik java, nekaj dela pa je bilo opravljenega tudi s pomoˇcjo programskega jezika python. Za ˇcrpanje virov je bil uporabljen javascript v kombinaciji z okoljem Node.js.
Poleg razvojnih okolij za te jezike je bilo uporabljenih ˇse nekaj drugih orodij:
Gephi Za vizualizacijo, preverjane in analizo izdelanih omreˇzij je bila upo- rabljena programska oprema Gephi. [5] Gephi je eden izmed najbolj ˇsiroko uporabljenih odprtokodnih programov za analizo in vizualizacijo grafov.
Pajek Za analizo izdelanih omreˇzij je bilo prav tako uporabljeno orodje Pajek. [2] Pajek je bil razvit v Sloveniji s strani Vladimirja Bagatelja and Andreja Mrvarja z namenom analize velikih omreˇzij.
OpenStreetMap OpenStreetMap [15] je projekt, ki se ukvarja z izdelavo prosto dostopne zbirke geografskih podatkov sveta. Je prosto dostopna alternativa zasebnim orodjem, kot je na primer Google Maps. V sklopu dela je bilo uporabljeno veliko geografskih podatkov, pridobljenih in dostopnih preko projekta.
Overpass turbo Za pridobivanje podatkov projekta OpenStreetMap je bilo v veliki meri uporabljeno spletno orodje Overpass turbo, [19] katerega namen je prav to. Ponuja vmesnik za izdelavo in izvajanje klicev za komunikacijo z aplikacijskim programskim vmesnikom Overpass API, ki dostopa do podatkovne baze OpenStreetMap.
OSMnx OSMnx [3] je podporni paket za programski jezik python, ki je na- menjen pridobivanju, modeliranju, analizi in vizualizaciji cestnih omreˇzij
iz OpenStreetMap.
Integrirana razvojna okolja in podporni sistemi Za pisanje in izvaja- nje programov v programskem jeziku java je bilo uporabljeno razvojno okolje IntelliJ IDEA, za izvajanje programov v jeziku python je bilo uporabljeno okolje Conda, za pisanje in izvajanje programov v pro- gramskem jeziku javascript pa je bilo uporabljeno razvojno okolje Web- Storm in podporno okolje Node.js.
Izdelana omreˇ zja
Izdelava posameznih omreˇzij je potekala v treh fazah: doloˇcevanje omreˇzij za izdelavo, ˇcrpanje podatkov in izdelava grafa. Pri vseh omreˇzjih smo podatke ˇcrpali iz spletnih virov, ki pa so se med seboj razlikovali.
Pri nekaterih omreˇzjih so bili izvorni podatki na voljo v podatkovnih ba- zah, pri nekaterih v obliki tabel, pri drugih spet na drugaˇcen naˇcin. Zato smo morali za posamezna omreˇzja pogosto izdelati posebej prilagojen ˇcrpalnik vi- rov.
Prav tako so se pri izdelavi posameznih omreˇzij razlikovali postopki izde- lave grafov. Ti so se razlikovali zaradi razliˇcne oblike naˇcrpanih podatkov in zaradi razliˇcnih naˇcinov povezovanja akterjev, ki so jih predstavljala vozliˇsˇca v grafih.
Postopki izdelave omreˇzij so, skupaj z njihovimi opisi in postopki ˇcrpanja podatkov, podani v tem poglavju. Omreˇzja, za katere so bili uporabljeni isti ˇcrpalniki in postopki izdelave, so predstavljena v istih podpoglavjih.
3.1 Omreˇ zje Slovenskih ˇ zeleznic
3.1.1 Opis omreˇ zja
Najmanjˇse in prvo izdelano omreˇzje predstavlja shemo Slovenskih ˇzeleznic.
Omreˇzje je bilo izdelano z namenom spoznavanja z datoteˇcnimi formati in 17
orodji Gephi ter Pajek in je zato precej enostavno.
Graf je neusmerjen. Vozliˇsˇc v njem je 78 in predstavljajo veˇcje postaje ˇzelezniˇskega prometa, s katerih imeni so tudi oznaˇcena. Povezav med vozliˇsˇci je 79 in so doloˇcene s progami, ki teˇcejo med postajami. Zanimivo je v grafu eno osamljeno vozliˇsˇce. To je vozliˇsˇce, ki predstavlja postajo Lendava, saj v omreˇzje ni bilo zajetih tujih postaj, povezava do postaje Lendava pa je v viru obstajala le preko Hrvaˇske.
3.1.2 Izdelava omreˇ zja
Vir za ˇcrpanje podatkov je bila slika 3.1, ki se nahaja na spletni strani Slo- venskih ˇzeleznic, pod naslovom ˇZelezniˇsko omreˇzje v Sloveniji [20]. Podatki so bili zajeti julija 2021 in ne zajemajo povezav ter postaj, ki se nahajajo na meji ali izven Slovenije.
Crpanje podatkov je zaradi namena spoznavanja orodja Gephi potekaloˇ roˇcno. Iz vira smo prebrali podatke in v orodju Gephi zanje ustvarili vozliˇsˇca in povezave. Ko smo v orodje vnesli vse podatke, smo graf izvozili v razliˇcnih formatih, ki smo jih nato uporabili za spoznavanje z njimi. Proces ustvar- janja grafa je bil zelo zamuden in monoton, kar nam je dobro predstavilo nesmiselnost roˇcnega ˇcrpanja podatkov.
Slika 3.1: Slikovna shema, vzeta is spletne strani Slovenskih ˇzeleznic [20], po kateri je bil narejen graf Slovenskih ˇzeleznic.
3.2 Omreˇ zje Ljubljanskega potniˇ skega prometa
3.2.1 Opis omreˇ zja
Drugo izdelano prometno omreˇzje je omreˇzje Ljubljanskega potniˇskega pro- meta. Omreˇzje predstavlja shemo linij avtobusov Ljubljanskega potniˇskega prometa znotraj mesta Ljubljana, kjer so zajete linije znotraj Obmoˇcja 1 Mestne obˇcine Ljubljana. Vozliˇsˇca v grafu predstavljajo avtobusne postaje in so tudi poimenovana z imeni postaj. Povezave v grafu povezujejo vozliˇsˇca, ki predstavljajo postaje, med katerimi vozi vsaj en avtobus.
Graf je usmerjen in ima uteˇzene povezave. Usmerjenost povezav doloˇca smer, v katero vozi avtobus po posamezni liniji, uteˇz pa je povpreˇcen ˇcas v minutah, ki ga avtobus potrebuje za pot med postajama. Povpreˇcni ˇcas je bil vzet, ker se ˇcasi med posameznimi linijami malce razlikujejo. Veliko parov vozliˇsˇc je povezanih dvakrat, vsakiˇc v eno smer, saj med postajama,
ki ju predstavljajo, avtobusi vozijo v obe smeri.
V omreˇzje, vizualizacija katerega je vidna na sliki 3.2, je vkljuˇceno 507 avtobusnih postaj, povezanih s 1085 povezavami. Kot priˇcakovano, graf nima osamljenih vozliˇsˇc, saj so vse postaje vkljuˇcene v vsaj eno linijo. Prav tako nobeno vozliˇsˇce nima stopnje ena, saj tudi na vseh konˇcnih postajah avtobusi tako odhajajo kot prihajajo, kar pomeni vsaj dve povezavi. Postaji z najveˇc sosednimi postajami sta postaji Kozolec in Kora bar, ki se nahajata v srediˇsˇcu mesta in sta del postajaliˇsˇca, znanega pod imenom Bavarski Dvor.
Slika 3.2: Graf omreˇzja LPP, vizualiziran z orodjem Gephi v naˇcinu Force Atlas 2.
3.2.2 Izdelava omreˇ zja
Vir za ˇcrpanje podatkov je bila spletna stran Ljubljanskega potniˇskega pro- meta, na kateri se nahajajo datoteke z voznimi redi posameznih linij. Usmer- jenost povezav glede na smer posamezne linije je bilo mogoˇce zajeti, ker imajo vozni redi navedeno ˇcasovno zaporedje obiskanih postaj posamezne linije. Po-
datki so bili zajeti avgusta 2021, ko linija 19B ni bila v obratovanju in tako ni vkljuˇcena v graf.
Kot ˇze omenjeno, je ˇcrpanje podatkov potekalo preko objavljenih voznih redov avtobusnih linij. Iz spleta smo najprej pridobili pdf datoteke z voz- nimi redi. Nato smo izdelali program v jeziku java, ki je zaporedoma odprl datoteke in iz njih prebral postaje posamezne linije v zaporedju.
Ker je to zaporedje predstavljalo tudi zaporedje, v katerem avtobus obiˇsˇce postaje na posamezni liniji, smo iz tega lahko dobili tudi povezave med po- stajami. V lokalnem spominu smo ob branju datotek hranili imena postaj in povezave med njimi.
Ko smo konˇcali z branjem zadnjega voznega reda smo te podatke ˇse za- pisali v datoteko formata Pajek NET.
3.3 Omreˇ zji letalskega prometa
3.3.1 Opis omreˇ zij
Iz podatkov letalskega prometa smo izdelali dve komplementarni omreˇzji.
Omreˇzje potniˇskega in omreˇzje tovornega prometa. Vozliˇsˇca v obeh omreˇzjih predstavljajo drˇzave s katerimi je imela Slovenija v letih 2004-2020 letalski promet, ki je prevaˇzal bodisi potnike ali pa blago, odvisno od omreˇzja.
Oba grafa sta usmerjena, povezave v obeh omreˇzjih pa predstavljajo smer v katero je potekal promet, v Slovenijo ali pa iz Slovenije. Vse povezave so tudi uteˇzene, uteˇzi pa predstavljajo ˇstevilo potnikov v omreˇzju potniˇskega prometa in koliˇcino tovora v tonah v omreˇzju blagovnega prometa. V teh dveh omreˇzjih se tudi pojavijo zanke. V obeh primerih namreˇc obstaja pro- met med razliˇcnimi letaliˇsˇci znotraj drˇzave.
Graf blagovnega prometa ima 63 vozliˇsˇc in 105 povezav. Iz njega je razvidno, da je Slovenija v letih 2004-2020 najveˇc tovora uvozila iz Nemˇcije in sicer kar 36.691 ton. Nemˇciji sledita Avstrija in Belgija. Prav tako je v Nemˇcijo izvozila najveˇc tovora; 14.617 ton. V tej kategoriji Nemˇciji sledita Avstrija in pa Srbija.
Vidimo lahko tudi, da obstaja 15 drˇzav v katere je Slovenija le izvozila blago, uvozila pa niˇc. Prav tako je 6 drˇzav iz katerih je Slovenija le sprejemala tovor. Zanimivo je med njimi Kitajska, iz katere je sprejela kar 390 ton tovora, oddala pa niˇc.
Podobne informacije lahko dobimo tudi iz grafa potniˇskega prometa, ki ima 71 vozliˇsˇc in 133 povezav. Najveˇc potniˇskega prometa je bilo do Nemˇcije, ki ji sledita Zdruˇzeno Kraljestvo in Turˇcija. Iz uteˇzi na povezavah lahko ugotovimo tudi, da je po ˇstevilu potnikov z letali veˇc ljudi priˇslo v drˇzavo, kot jih jo je zapustilo.
Ti dve omreˇzji sta bili izdelani predvsem z namenom prikaza uˇcinkovitosti vizualizacije podatkov, shranjenih v formatu grafa. Iz debelin ˇcrt na slikah 3.3 in 3.4, ki predstavljata oba grafa, je lepo razvidna razliˇcna koliˇcina pro- meta med drˇzavami.
3.3.2 Izdelava omreˇ zij
Podatke za ti dve omreˇzji smo ˇcrpali iz podatkovne baze SiStat Statistiˇcnega urada Slovenije. V zaˇcetku se je zdelo, da bo ta vir velikega ˇstevila grafov, a se je kasneje izkazalo, da je vrsta podatkov neprimerna za gradnjo zanimivih omreˇzij. SiStat omogoˇca izvoz podatkov v obliki tabele, tako da je bilo samo ˇcrpanje podatkov trivialno.
Iz podatkov v pridobljenih tabelah smo grafa nato izdelali s pomoˇcjo programa v jeziku java. Ta je bil spisan tako, da je iz tabel najprej prebral podatke iz razliˇcnih let in jih zdruˇzil v eno ˇstevilko, nato pa vse neniˇcelne ˇstevilke pretvoril v povezave med drˇzavami in jih zapisal v graf.
Namerno smo v vsakem izmed grafov izpustili drˇzave, s katerimi ni bilo nobenega prometa, da smo se izognili osamljenim vozliˇsˇcem. To je tudi razlog za razliˇcni ˇstevili vozliˇsˇc med grafoma.
Slika 3.3: Graf omreˇzja tovornega letalskega prometa, vizualiziran z orodjem Gephi v Fruchterman-Reingold naˇcinu.
Slika 3.4: Graf omreˇzja potniˇskega letalskega prometa, vizualiziran z orodjem Gephi v Fruchterman-Reingold naˇcinu.
3.4 Omreˇ zje zaposlenih na Fakulteti za raˇ cunalniˇ stvo in informatiko
3.4.1 Opis omreˇ zja
Omreˇzje zaposlenih na Fakulteti za raˇcunalniˇstvo in informatiko predstavlja tesnost sodelovanja med zaposlenimi. Podatki so vzeti iz spletne strani fa- kultete in so zaradi skrbi o varstvu osebnih podatkov anonimizirani, tako da vozliˇsˇca nimajo oznak z imeni zaposlenih.
Izdelani graf ima 216 vozliˇsˇc in 1.800 povezav med njimi. Povezave imajo lahko pet razliˇcnih pomenov; povezani osebi sodelujeta pri izvajanju istega predmeta, sta v istem prostoru na fakulteti, sta ˇclana istega laboratorija, sta sodelovala na istem projektu ali pa sta ˇclana istega oddelka, npr. dekanata.
Graf je neusmerjen, povezave v njem pa so uteˇzene. Uteˇzi predstavljajo ˇstevilo skupnih elementov, ki jih imata dve osebi.
Na sliki 3.5 je lepo razvidno, kako so tesneje povezane osebe v istih labo- ratorijih, saj imajo kot taki najverjetneje tudi skupne projekte. Vidi se tudi, da v omreˇzju obstajajo podgrafi zaposlenih, ki niso del uˇcnega kolegija, na primer zaposleni v dekanatu.
Omreˇzje ima tudi ˇstiri osamljena vozliˇsˇca, ki predstavljajo zunanje so- delavce in tajnika fakultete. Najveˇcja stopnja vozliˇsˇca je 61, najveˇcja uteˇz povezave pa 18, kar skoraj zagotovo pomeni, da ti dve osebi tesno sodelujeta, saj je takˇsa uteˇz mogoˇca le z veliko skupnimi projekti.
3.4.2 Izdelava omreˇ zja
Kot ˇze omenjeno je bila vir za ˇcrpanje podatkov spletna stran Fakultete za raˇcunalniˇstvo in informatiko, kjer so navedeni zaposleni in podatki o njih.
Na podlagi teh podatkov smo izdelali omreˇzje. Tu smo se posluˇzili spletnega ˇcrpanja podatkov. Ustvarili smo javascript program 3.1, ki je najprej prebral povezave do strani s podatki posameznih zaposlenih iz seznama zaposlenih in nato s pomoˇcjo knjiˇznice “axios” zaporedoma obiskal vse te strani. Na
Slika 3.5: Graf omreˇzja zaposlenih na FRI, vizualiziran z orodjem Gephi v OpenOrd naˇcinu.
vsaki strani je s pomoˇcjo knjiˇznice “cheerio” poiskal elemente z relevantnimi razredi in iz njih izluˇsˇcil vsebovane podatke ter jih zapisal v datoteko zbranih podatkov kot seznam atributov za to osebo.
Za izdelavo omreˇzja smo se posluˇzili jezika java, kjer smo ustvarili pro- gram, ki je preˇcesal datoteko zbranih podatkov in najprej ustvaril ustrezna vozliˇsˇca za zaposlene, nato pa za vsakega izmed zaposlenih preveril, koliko atributov se ujema z atributi drugih zaposlenih in med vozliˇsˇcema ustvaril povezavo z ustrezno uteˇzjo. Na koncu pa je ustvarjen graf zapisal v datoteko formata Pajek NET.
f o r ( l e t i = 0 ; i < d a t a . l e n g t h ; i ++) { a x i o s ( u r l+d a t a [ i ] )
. t h e n ( r e s p o n s e => {
c o n s t html = r e s p o n s e . d a t a ; c o n s t $ = c h e e r i o . l o a d ( html ) l e t a t t r i b u t e s = [ ] ;
l e t name = $( ’# profName ’ ) . t e x t ( ) . t r i m ( ) ; c o n s o l e . l o g ( name ) ;
l e t t i t l e = $( ’# p r o f T i t l e ’ ) . t e x t ( ) . t r i m ( ) ;
i f ( t i t l e != ” R e t i r e d P r o f e s s o r ” && t i t l e != ” R e s e a r c h e r ”
&& ! t i t l e . i n c l u d e s ( ” F u l l P r o f e s s o r ” ) && t i t l e != ” C o l l a b o r a t o r ”
&& t i t l e != ” A s s i s t a n t ” && t i t l e != ” A s s i s t a n t P r o f e s s o r ”
&& t i t l e != ” L a b o r a t o r y T e c h n i c i a n ” && t i t l e != ” Other members ”
&& t i t l e != ”” && ! t i t l e . i n c l u d e s ( ” A s s o c i a t e P r o f e s s o r ” )
&& t i t l e != ”Young R e s e a r c h e r ” ) { a t t r i b u t e s . push ( t i t l e ) ; }
l e t room = $( ’# m a i l I n f o ’ ) . t e x t ( ) . t r i m ( ) ; i f ( room != ” ” ) {
room = room . s l i c e ( room . i n d e x O f ( ’ R’ ) + 1 , room . end )
room = room . s l i c e ( room . i n d e x O f ( ’ R’ ) , room . i n d e x O f ( ’ R’ ) + 5 ) ; i f ( room != ” ” ) {
a t t r i b u t e s . push ( room ) ; }
}
$( ’ . a b o u t M a i n S e c t i o n L i l i ’ ) . e a c h ( ( i n d e x , e l e m e n t ) => { l e t a t t = $( e l e m e n t ) . f i n d ( ’ a ’ ) . t e x t ( ) . t r i m ( ) ; i f ( a t t . i n c l u d e s ( ” L a b o r a t o r y ” ) ) {
a t t = a t t . s l i c e ( 0 , a t t . l a s t I n d e x O f ( ’ , ’ ) ) ; }
i f ( a t t != ” ” ) {
a t t r i b u t e s . push ( a t t ) ; }
}) ;
c o n s o l e . l o g ( a t t r i b u t e s ) ;
f s . a p p e n d F i l e ( ’ . / f r i d a t a . j s o n ’ , name + ”\n” + JSON . s t r i n g i f y ( a t t r i b u t e s ) + ”\n ” , ( e r r o r ) => {
i f ( e r r o r ) throw e r r o r ; })
})
. c a t c h ( c o n s o l e . e r r o r ) ; }
Slika 3.1: Izsek kode za ˇcrpalnik podatkov pri omreˇzju zaposlenih na FRI
3.5 Omreˇ zje slovenskih startupov
3.5.1 Opis omreˇ zja
Omreˇzje slovenskih startupov, ki je prikazano na sliki 3.6, predstavlja sloven- ska startup podjetja, ki so vˇclanjena v projekt Start:up Slovenia. V projekt je vkljuˇcenih 262 podjetij, zato ima tudi naˇse omreˇzje 262 vozliˇsˇc. Omreˇzje je neusmerjeno in ima 16.816 neuteˇzenih povezav.
Povezave v omreˇzju predstavljajo vˇclanjenost podjetij v isti program pro- jekta, ali pa isto mesto, v katerem se nahaja sedeˇz podjetja. Najprej smo izdelali graf brez moˇznosti povezave istega kraja, a je graf tvoril precej pod- grafov, zato smo se odloˇcili za dodatno moˇzno povezavo.
Programi, v katere so podjetja vkljuˇcena, jim nudijo razliˇcne storitve v obliki finanˇcnih sredstev, seminarjev, svetovanj in drugih oblik podpore.
Vkljuˇcenost v program ‘P2 2019 SPS’ na primer pomeni, da je bilo star- tup podjetje vkljuˇceno v program financiranja P2 Slovenskega podjetniˇskega sklada v letu 2019. Povezave tu niso uteˇzene, saj uteˇzi niso doprinesle veliko dodatnih podatkov.
Omreˇzje je bilo izdelano predvsem z namenom izdelave zanimivega pove- zanega grafa. Tu nam je uspelo le delno, saj ima omreˇzje 4 osamljena vozliˇsˇca, ki predstavljajo startup podjetja, ki niso vkljuˇcena v nobenega izmed pro- gramov in imajo sedeˇz v manjˇsih ali pa bolj odroˇcnih krajih. Omreˇzje je zelo gosto povezano zaradi velike vkljuˇcenosti v vsaj enega od bolj popularnih programov projekta.
Druga najmanjˇsa stopnja vozliˇsˇca, takoj za osamljenimi, ki imajo seveda stopnjo niˇc, je ˇsest, najveˇcja pa kar 236. To vozliˇsˇce pripada startup podjetju Grid Instruments, ki ima sedeˇz v Ljubljani in je vkljuˇceno v veˇc programov, kar tudi nakazuje na pravilnost in smiselnost grafa.
3.5.2 Izdelava omreˇ zja
Vir za ˇcrpanje podatkov je bil pri tem omreˇzju spletna stran projekta Start:up Slovenia, kjer so navedena vsa startup podjetja, vkljuˇcena v program.
Podobno kot pri omreˇzju zaposlenih na FRI se tudi na tej strani nahaja seznam vseh podjetij s povezavami na posamezne strani z opisi in podatki o posameznem podjetju, tako da smo za ˇcrpanje podatkov in izdelave grafa posluˇzili programov iz razdelka 3.4.2, ki smo ju prilagodili potrebam tega omreˇzja.
Javascript ˇcrpalniku smo spremenili iskane elemente na strani, programu za izdelavo grafa pa smo poenostavili funkcije za iskanje povezav, da smo lahko zanemarili uteˇzenost povezav.
Slika 3.6: Graf omreˇzja slovenskih stratupov, vizualiziran z orodjem Gephi v Fruchterman-Reingold naˇcinu.
3.6 Omreˇ zja slovenskih ˇ sportnikov
3.6.1 Opis omreˇ zij
Omreˇzja slovenskih ˇsprtnikov so bila narejena na podlagi podatkov Olimpij- skega komiteja Slovenije. Predstavljajo ˇsportnike, ki so bili vpisani v evi- denco kategoriziranih ˇsportnikov ob ˇcasu zajemanja podatkov, in povezave med njimi.
Izdelali smo tri omreˇzja. Grafi vseh treh izdelanih omreˇzij pa so neusmer- jeni in anonimizirani zaradi varstva osebnih podatkov.
Vsa tri omreˇzja imajo 7.837 vozliˇsˇc, ki predstavljajo ˇsportnike, razlikujejo pa se v naˇcinu tvorjenja povezav in imajo poslediˇcno tudi razliˇcna ˇstevila povezav.
Prvo omreˇzje ima 118.195 povezav, ki predstavljajo ˇclanstvo povezanih ˇsportnikov v istem druˇstvu. Zaradi tega ima kot priˇcakovano graf izjemno veliko ˇstevilo podgrafov.
Drugo omreˇzje ima 172.570 povezav, ki predstavljajo nastop povezanih ˇsportnikov na istem tekmovanju. To omreˇzje je sicer bolje povezano kot prvo, a graf omreˇzja vseeno tvori veliko podgrafov, ki predstavljajo ˇsportnike, ki se ukvarjajo s posameznimi ˇsporti.
Tretje omreˇzje je kombinacija obeh drugih. Ima 263.742 povezav, ki pred- stavljajo nastop na istem tekmovanju ali pa ˇclanstvo v istem druˇstvu v ob- dobju, ko so bili vpisani v evidenco. To omreˇzje je tako veliko bolje povezano kot katerokoli izmed drugih dveh.
Povezave v tem omreˇzju so tudi uteˇzene in sicer na naslednji naˇcin: uteˇz ena pomeni, da povezava predstavlja nastop na istem tekmovanju, pri uteˇzi dva ta predstavlja ˇclanstvo v istem druˇstvu in pri uteˇzi tri oboje.
V omreˇzju nastopa najveˇc povezav, ki imajo uteˇz ena in najmanj takˇsnih z uteˇzjo tri. Graf ima kar 48 osamljenih vozliˇsˇc in precej podomreˇzij, kar je vidno tudi na sliki 3.7, na kateri so prav tako dobro vidne gruˇce ˇsportnikov, ki so tesno povezani, ker so ˇclani istega druˇstva in so nastopali na istih tekmovanjih.
V tem omreˇzju ima najveˇcjo stopnjo vozliˇsˇce s stopnjo 326, kateremu sledi kar 24 vozliˇsˇc s stopnjo 293. Sklepamo lahko, da so to zelo aktivni ˇsportniki, ki so nastopili na veliko tekmovanjih in so najverjetneje tudi ˇclani enega izmed veˇcjih druˇstev.
3.6.2 Izdelava omreˇ zij
Vir za ˇcrpanje podatkov je bila pri tem omreˇzju Excel datoteka evidence ka- tegoriziranih ˇsportnikov, pridobljena iz spletne strani Olimpijskega komiteja Slovenije. Za ˇcrpanje podatkov iz nje smo ustvarili java program, ki je hkrati prebral relevantne podatke in iz njih ustvaril graf.
Za branje datoteke smo se posluˇzili knjiˇznice Apache POI, ki nam je podala vmesnik za manipulacijo tabele, v kateri so se nahajali podatki. Pro- gram je iteriral ˇcez celotno tabelo in v stolpcih, ki so imeli relevantne podatke, prebral vsebino.
Iz prebranih podatkov je loˇceno shranil druˇstva posameznih ˇsportnikov in seznam tekmovanj na katerih so nastopili. Po konˇcanem branju je primerjal druˇstva in tekmovanja med ˇsportniki in ustvaril omreˇzja zanje.
Slika 3.7: Graf omreˇzja slovenskih ˇsportnikov, vizualiziran z orodjem Gephi v OpenOrd naˇcinu.
3.7 Omreˇ zja spletnih strani
3.7.1 Opis omreˇ zij
Izdelali smo tri omreˇzja na podlagi slovenskih spletnih strani. Omreˇzje spletiˇsˇca drˇzavne uprave www.gov.si, omreˇzje spletiˇsˇca Mestne obˇcine Lju- bljana www.ljubljana.si in omreˇzje spletnega portala www.slovenia.si, ki je je glavna nacionalna vstopna toˇcka v lasti Urada Vlade Republike Slovenije za komuniciranje.
Poskusili smo izdelati tudi omreˇzje za spletiˇsˇci Univerze v Ljubljani in
Radiotelevizije Slovenija, a sta se spletiˇsˇci izkazali za preobseˇzni za obdelavo z naˇsimi orodji.
Vsa tri omreˇzja predstavljajo povezanost posameznih spletnih strani v spletiˇsˇcih. Vozliˇsˇca v grafih predstavljajo dostopne spletne strani, vidne uporabnikom, ki brskajo po spletiˇsˇcu, povezave med njimi pa dostopnost ene strani z druge preko hiperpovezav.
Iz glavne spletne strani drˇzavne uprave www.gov.si lahko uporabnik na primer klikne na hiperpovezavo “Drˇzavni organi”, ki odpre spletno stran www.gov.si/drzavni-organi/. Ti dve spletni strani predstavljata v naˇsem grafu vozliˇsˇci, ki sta povezani z usmerjeno povezavo iz prve k drugi.
Grafi so tako usmerjeni in popolnoma povezani, saj smo pri izdelavi po- datkov zaˇceli na eni strani in do vseh drugih priˇsli po neki poti.
Omreˇzje spletiˇsˇca drˇzavne uprave
Omreˇzje spletiˇsˇca drˇzavne uprave ima 3.856 vozliˇsˇc in 87.377 povezav med njimi. Podatki za omreˇzje so bili zajeti 7.8.2021 in tako graf odraˇza stanje strani na ta dan. Kot priˇcakovano imajo najviˇsje stopnje vozliˇsˇca, ki pred- stavljajo spletne strani, ki so dostopne na skoraj vseh straneh iz navigacijske vrstice. Med njimi je tudi domaˇca stran s stopnjo 3.124.
Najveˇc povezav na eni strani je 79, kar je predstavljeno z izhodno sto- pnjo vozliˇsˇca. Omreˇzje ima tudi 216 vozliˇsˇc, ki predstavljajo datoteke na streˇzniku in imajo tako izhodno stopnjo vozliˇsˇca enako niˇc. V primerjavi z drugima dvema omreˇzjema v tej kategoriji je to omreˇzje precej bolj povezano zaradi sorazmerno majhnega ˇstevila takˇsnih vozliˇsˇc. To je razvidno tudi iz vizualizacije, ki je podana na sliki 3.8.
Omreˇzje spletiˇsˇca Mestne obˇcine Ljubljana
Omreˇzje spletiˇsˇca Mestne obˇcine Ljubljana ima 45.346 vozliˇsˇc in 372.446 povezav med njimi. Podatki za omreˇzje so bili zajeti 8.8.2021 in tako graf odraˇza stanje strani na ta dan. Omreˇzje je od omreˇzja spletiˇsˇca drˇzavne uprave precej drugaˇcno, saj ima veˇc kot polovica vozliˇsˇc izhodno stopnjo
Slika 3.8: Graf omreˇzja spletiˇsˇca drˇzavne uprave, vizualiziran z orodjem Ge- phi v Fruchterman-Reingold naˇcinu.
niˇc, kar pomeni, da predstavljajo datoteke na streˇzniku. To je zato, ker stran poleg dostopnih podatkovnih datotek vsebuje veliko ˇstevilo slik, ki so dostopne preko hiperpovezav.
Zanimivo je, da ima slovenska verzija spletiˇsˇca veˇc strani kot angleˇska, kar je razvidno iz dejstva, da ima vozliˇsˇce slovenske domaˇce strani viˇsjo vhodno stopnjo kot vozliˇsˇce angleˇske domaˇce strani. Kot priˇcakovano pa imajo tudi tu najveˇcje stopnje vozliˇsˇca, katerih spletne strani so dostopne preko navigacijske vrstice.
Omreˇzje je bilo za vizualizacijo preveliko, a iz pregleda podatkov lahko sklepamo, da bi bila slika podobna kot za omreˇzje spletiˇsˇca slovenia.si.
Omreˇzje spletiˇsˇca slovenia.si
Omreˇzje spletiˇsˇca drˇzavne uprave ima 5.152 vozliˇsˇc in 112.830 povezav med njimi. Podatki za omreˇzje so bili zajeti 6.8.2021 in tako graf odraˇza stanje strani na ta dan. Vozliˇsˇce z najviˇsjo stopnjo je tudi tu domaˇca stran, ki ima stopnjo 2828.
Zanimivo, da to ne zajema vseh moˇznih povezav na domaˇco stran, spletiˇsˇce namreˇc uporablja 4 razliˇcne hiperpovezave do domaˇce strani, ki tako tvorijo 4 razliˇcna vozliˇsˇca. Vsota njihovih stopenj pa je kar 4.873.
Zopet pa imamo skoraj polovico vozliˇsˇc z izhodno stopnjo niˇc. Prav tako so vozliˇsˇca z najveˇcjimi stopnjami tista, ki predstavljajo strani, dostopne preko navigacijske vrstice. Omreˇzje je vizualizirano na sliki 3.9.
3.7.2 Izdelava omreˇ zij
Pri izdelavi teh treh omreˇzij nismo imeli vira podatkov v obiˇcajnem pomenu besede. Namesto tega so bila viri za ˇcrpanje podatkov spletiˇsˇca sama. Tako smo se posluˇzili enega izmed najbolj pogostih virov ˇcrpanja podatkov; sple- tnega ˇcrpanja. Za to smo morali ustvariti t.i. pajka, ki je izraz za program, ki avtomatsko obiskuje in pregleduje spletne strani.
Na trgu je na voljo veˇc brezplaˇcnih in plaˇcljivih pajkov, ki so precej bolj napredni od naˇse reˇsitve, a v sklopu te naloge smo sami izdelali preprostega pajka 3.2, ki je pregledal spletno stran in iz nje izluˇsˇcil hiperpovezave ter jih dodal na seznam strani, ki so dostopne z nje. Ob tem smo se zopet posluˇzili knjiˇznic “axios” in “cheerio”.
Pajek je prav tako vse najdene strani dodal na ˇcakalno vrsto in po konˇcanem pregledu ene strani obiskal novo stran iz ˇcakalne vrste, na kateri je ponovil postopek pregledovanja. To je izvajal dokler so bile v ˇcakalni vrsti ˇse neobiskane strani. Rezultat tega programa je bila datoteka s seznamom sple-
Slika 3.9: Graf omreˇzja spletiˇsˇca slovenia.si, vizualiziran z orodjem Gephi v Fruchterman-Reingold naˇcinu.
tnih strani spletiˇsˇca, kjer je imela vsaka stran pripet seznam hiperpovezav na njej.
Nato smo izdelali ˇse java program, ki je prebral izdelano datoteko, dodal vse strani v omreˇzje kot vozliˇsˇca in pregledal sezname posameznih strani ter zanje ustvaril povezave. Spletnim naslovom strani je nato poˇcistil formatira- nje in celotno omreˇzje zapisal v datoteko grafa.
a s y n c f u n c t i o n mapSite ( u r l ) { c o n s o l e . l o g ( u r l ) ;
l e t a t t r i b u t e s = [ ] ; a w a i t a x i o s ( u r l )
. t h e n ( r e s p o n s e => {
c o n s t html = r e s p o n s e . d a t a ; c o n s t $ = c h e e r i o . l o a d ( html )
$( ’ a ’ ) . e a c h ( ( i n d e x , e l e m e n t ) => { l e t l i n k = $( e l e m e n t ) . a t t r ( ’ h r e f ’ ) ; i f ( l i n k != n u l l ) {
l i n k = l i n k . t r i m ( ) ;
i f ( l i n k . s t a r t s W i t h ( ”\/ ” ) ) {
i f ( ! c o n t a i n s L i n k ( a t t r i b u t e s , l i n k ) ) { a t t r i b u t e s . push ( l i n k ) ;
}
i f ( ! c o n t a i n s L i n k ( l i n k s , l i n k ) ) { l i n k s . push ( l i n k ) ;
} } }
// c o n s o l e . l o g ($( e l e m e n t ) . a t t r ( ’ h r e f ’ ) . t r i m ( ) ) ; }) ;
f s . a p p e n d F i l e ( ’ . / f r i−uni−l j . j s o n ’ , u r l + ”\n”
+ JSON . s t r i n g i f y ( a t t r i b u t e s ) + ”\n ” , ( e r r o r ) => { i f ( e r r o r ) throw e r r o r ;
}) })
. c a t c h ( e r r o r => {
c o n s o l e . l o g ( e r r o r . r e s p o n s e ) ; }) ;
}
Slika 3.2: Funkcija izdelanega pajka, ki je pregledovala stran za vsebovane hiperpovezave.
3.8 Geografska omreˇ zja
3.8.1 Opis omreˇ zij
Geografska omreˇzja smo izdelali s podatki, ki jih ponuja projekt OpenStre- etMap [15]. Vsa omreˇzja te vrste so bila izdelana na isti naˇcin in se koncep- tualno razlikujejo samo v infrastrukturah, ki jih predstavljajo.
V teh omreˇzjih vozliˇsˇca predstavljajo obstojeˇce objekte v Sloveniji (v primeru omreˇzja izposoje koles pa v Ljubljani), povezana pa so, ˇce so ti objekti med seboj po zraˇcni razdalji oddaljeni za manj kot doloˇceno ˇstevilo kilometrov. Najprej smo ˇzeleli takˇsna omreˇzja izdelati glede na razdaljo po cestah, a so imeli vsi brezplaˇcni aplikacijski vmesniki, ki lahko raˇcunajo matrike oddaljenosti, prevelike omejitve za naˇse potrebe.
Izdelana geografska omreˇzja lahko loˇcimo na sedem skupin, glede na vrsto objekta, ki jih predstavljajo vozliˇsˇca v grafu. Te skupine nato vsebujejo od enega do tri omreˇzja, ki se med seboj razlikujejo glede na kriterije, upora- bljene pri ustvarjanju povezav. V nekaterih omreˇzjih smo vozliˇsˇca povezali le v primeru, da so bili objekti med seboj oddaljeni manj kot kilometer, drugje smo kriterij sprostili na 5 kilometrov in pa tudi na 10 kilometrov.
Kot priˇcakovano so omreˇzja z bolj sproˇsˇcenimi kriteriji bolje povezana, kljub temu pa imajo vsa omreˇzja tudi podomreˇzja in osamljena vozliˇsˇca.
Osnovne znaˇcilnosti omreˇzij so zbrane v tabeli 3.1. Primer omreˇzja pa lahko vidimo na sliki 3.10, ki predstavlja vizualizacijo najveˇcjega izmed izdelanih geografskih omreˇzij.
Objekti omreˇzja Kriterij povezav
St.ˇ vozliˇsˇc
St. po-ˇ vezav
Povpreˇcna stopnja vozliˇsˇca
Bolniˇsnice 1 km 115 152 2,643
Bolniˇsnice 5 km 115 486 8,452
Bolniˇsnice 10 km 115 788 13,704
Svetiˇsˇca 5 km 2.202 9.787 8,889
Svetiˇsˇca 10 km 2.202 32.054 29,114
Gasilski domovi 5 km 701 1.429 4,077
Gasilski domovi 10 km 701 5.197 14,827
Izposojevalnice koles 1 km 69 142 4,116
Policjske postaje 5 km 113 104 1,841
Policjske postaje 10 km 113 176 3,115
Poˇstne poslovalnice 5 km 371 585 3,154
Poˇstne poslovalnice 10 km 371 1603 8,642
Ambulante 5 km 311 1.903 12,238
Ambulante 10 km 311 2.907 18,695
Tabela 3.1: Tabela osnovnih znaˇcilnosti izdelanih geografskih omreˇzij
Slika 3.10: Graf omreˇzja svetiˇsˇc pri kriteriju 10 km, vizualiziran z orodjem Gephi v Yifan Hu naˇcinu.
3.8.2 Izdelava omreˇ zij
Crpanje podatkov za izdelavo geografskih omreˇˇ zij je potekalo z uporabo ˇcrpalnika Overpass turbo [19], preko katerega smo lahko komunicirali z apli- kacijskim vmesnikom Overpass, ki je izvajal poizvedbe nad podatki Open- StreetMap.
Najprej smo za vsak izbran objekt napisali poizvedbo, ki jo je Overpass turbo nato izvedel in nam vrnil podatke v formatu JSON. Primer takˇsne poizvedbe je podan na sliki 3.3. Za branje teh datotek in gradnjo grafa smo zopet izdelali java program, ki je prebral podatke in iz njih ustvaril seznam vozliˇsˇc s pripadajoˇcimi koordinatami.
Zaradi naˇcina pridobivanja podatkov so imele datoteke podvojene vnose;
objekt je namreˇc v OpenStreetMap lahko zapisan kot entiteta tipa “node”,
“way”, ali pa “relation” in precej pogosto je, da je en objekt shranjen na veˇc naˇcinov. Tako je program s pregledom koordinat vozliˇsˇc lahko odstranil tista, katerih koordinate so bile skoraj enake. Nato je nad vsemi pari vo- zliˇsˇc izraˇcunal zraˇcno razdaljo po formuli haversine in vozliˇsˇca povezal, ˇce je rezultat izraˇcuna ustrezal zadanemu kriteriju.
[ o u t : j s o n ] [ t i m e o u t : 2 5 ] ;
{{g e o c o d e A r e a : S l o v e n i a}}−>. s e a r c h A r e a ; (
node [ ” a m e n i t y ”=” p l a c e o f w o r s h i p ” ] ( a r e a . s e a r c h A r e a ) ; way [ ” a m e n i t y ”=” p l a c e o f w o r s h i p ” ] ( a r e a . s e a r c h A r e a ) ;
r e l a t i o n [ ” a m e n i t y ”=” p l a c e o f w o r s h i p ” ] ( a r e a . s e a r c h A r e a ) ; ) ;
o u t c e n t e r body ;
>;
o u t s k e l q t ;
Slika 3.3: Overpass turbo poizvedba, ki vrne seznam vseh cerkva in drugih svetiˇsˇc v Sloveniji.
3.9 Cestna omreˇ zja
3.9.1 Opis omreˇ zij
V sklopu cestnih omreˇzij smo izdelali 67 grafov, vsak izmed katerih predsta- vlja eno takˇsno omreˇzje za doloˇceno slovensko mesto. Pri izdelavi omreˇzij smo poskusili izdelati omreˇzja za vsa slovenska mesta, a smo morali izpustiti dve mesti, ker v projektu OpenStreetMaps nista imeli definiranih meja.
V teh omreˇzjih predstavljajo vozliˇsˇca cestna kriˇziˇsˇca in konci slepih ulic, povezave pa ceste, ki povezujejo kriˇziˇsˇca. Grafi omreˇzij so neusmerjeni, po- vezave in vozliˇsˇca pa imajo veˇc atributov, ki zaradi nedostopnosti informacij v viru niso prisotni pri vseh omreˇzjih.
Vozliˇsˇca imajo opcijsko pripete atribute za koordinate, stopnjo, posebno vrsto kriˇziˇsˇca in referenˇcno ˇstevilko iz vira. Povezave imajo moˇzne atribute za koordinate, ˇsirino, dolˇzino, ime, ˇstevilo pasov, omejitev hitrosti, morebitne storitve; na primer cestno parkiranje, vrsto dovoljenega prometa. Poleg tega imajo tudi atribute, ki doloˇcujejo, ˇce je dovoljen le enosmerni promet, ˇce predstavlja most, ˇce predstavlja tunel ali pa ˇce predstavlja kroˇziˇsˇce. Prav tako imajo moˇzna atributa ‘id’ in referenˇcne ˇstevilke iz vira.
Ta omreˇzja bi bila lahko posebej zanimiva za potrebe urbanistike. Vi- zualizacija enega izmed omreˇzij se nahaja na sliki 3.11, osnovne znaˇcilnosti omreˇzij pa so podane v tabelah 3.2, 3.3 in 3.4.
Slika 3.11: Graf cestnega omreˇzja mesta Domˇzale, vizualiziran z orodjem Gephi v OpenOrd naˇcinu.
Mesto ˇSt.
vozliˇsˇc
ˇSt.
povezav
Povpreˇcna stopnja vozliˇsˇca
Ajdovˇsˇcina 4.771 11.446 2,399
Bled 1.969 4.835 2,456
Bovec 2.385 5.975 2,505
Breˇzice 6.868 15.820 2,303
Celje 4.748 11.018 2,321
Cerknica 2.971 7.695 2,59
Crnomeljˇ 4.439 10.424 2,348
Domˇzale 3.452 8.593 2,489
Dravograd 3.031 6.732 2,221
Gornja Radgona 1.650 3.733 2,262
Grosuplje 3.832 9.287 2,424
Hrastnik 1.105 2.468 2,233
Idrija 2.328 5.476 2,352
Ilirska Bistrica 2.688 6.597 2,454
Izola 3.211 7.395 2,303
Jesenice 1.661 3.955 2,381
Kamnik 4.130 10.074 2,439
Koˇcevje 2.789 6.753 2,421
Koper 8.810 21.454 2,435
Kostanjevica na Krki 510 1.168 2,29
Kranj 5.951 14.996 2,520
Krˇsko 6.906 15.750 2,281
Laˇsko 3.104 6.930 2,233
Tabela 3.2: Tabela osnovnih znaˇcilnosti izdelanih cestnih omreˇzij Ajdovˇsˇcina - Laˇsko
Mesto ˇSt.
vozliˇsˇc
ˇSt.
povezav
Povpreˇcna stopnja vozliˇsˇca
Lenart 1.329 2.931 2,205
Lendava 2.062 4.770 2,313
Litija 3.021 6.872 2,275
Ljubljana 31.944 80.676 2,526
Ljutomer 2.255 5.039 2,235
Logatec 1.889 4.629 2,451
Maribor 14.273 36.532 2,560
Medvode 3.332 7.961 2,389
Mengeˇs 834 2.056 2,465
Metlika 2.630 6.222 2,366
Meˇzica 734 1.652 2,251
Murska Sobota 2.636 6.225 2,456
Nova Gorica 5.597 13.595 2,429
Novo Mesto 5.510 13.238 2,403
Ormoˇz 3.795 8.517 2,244
Piran 3.969 9.323 2,349
Postojna 6.651 16.161 2,43
Prevalje 1.315 3.011 2,29
Ptuj 2.404 5.874 2,443
Radeˇce 973 2.176 2,236
Radovljica 2.358 6.073 2,575
Ravne na Koroˇskem 1.808 4.292 2,374
Tabela 3.3: Tabela osnovnih znaˇcilnosti izdelanih cestnih omreˇzij Lenart - Ravne na Koroˇskem
Mesto St.ˇ vozliˇsˇc
St.ˇ povezav
Povpreˇcna stopnja vozliˇsˇca
Ribnica 1.915 4.739 2,475
Rogaˇska Slatina 2.742 6.141 2,24
Ruˇse 3.633 8.893 2,448
Sevnica 4.927 11.055 2,244
Seˇzana 4.422 10.960 2,479
Slovenj Gradec 5.070 11.479 2,264
Slovenska Bistrica 8.795 19.910 2,264
Slovenske Konjice 2.034 4.946 2,432
Sentjurˇ 4.427 9.935 2,244
Skofja Lokaˇ 3.833 9.335 2,435
Soˇstanjˇ 2.039 4.516 2,215
Tolmin 3.078 7.464 2,425
Trbovlje 1.375 3.194 2,323
Trebnje 3.361 7.721 2,297
Trˇziˇc 2.238 5.374 2,401
Velenje 1.704 4.075 2,391
Vrhnika 3.107 7.251 2,334
Zagorje ob Savi 2.431 5696 2,343
Zreˇce 2.901 6.507 2,243
Zalecˇ 2.278 5.148 2,26
Zeleznikiˇ 2.187 5.242 2,397
Ziriˇ 621 1.475 2,375
Tabela 3.4: Tabela osnovnih znaˇcilnosti izdelanih cestnih omreˇzij Ribnica - Ziriˇ
3.9.2 Izdelava omreˇ zij
Crpanje podatkov za ta omreˇˇ zja je potekalo z uporabo python paketa OSMnx [3], ki je za vir ˇcrpanja uporabljal podatke, podane s strani projekta Open- StreetMap. Preden smo lahko zaˇceli ˇcrpati, pa je bilo potrebno ugotoviti kako dostopati do relevantnih podatkov.
Doloˇcanje ustreznega okvira znotraj katerega naj nam OpenStreetMap poda podatke je namreˇc precej zapleteno, ˇce ˇzelimo podatke, ki niso zajeti v pravokotniku, ampak znotraj bolj zapletenega obmoˇcja, na primer obˇcine.
Zato smo se za ta namen posluˇzili spletnega orodja OSM-Boundaries, ki je dostopen na naslovu https://osm-boundaries.com/ in omogoˇca brskanje po ˇze obstojeˇcih okvirjih, ki jih uporablja OpenStreetMap. S pomoˇcjo tega orodja smo ugotovili, da OpenStreetMap ˇze vsebuje okvirje za veˇcja slovenska mesta in smo se zaradi tega odloˇcili za izdelavo mestnih omreˇzij.
Na sliki 3.12 je vidna meja, ki v projektu OpenStreetMap oznaˇcuje mesto Ljubljana. Podatke, ki se nahajajo znotraj te meje smo uporabili za izdelavo cestnega omreˇzja mesta Ljubljana.
Za ˇcrpanje podatkov in izdelavo grafov smo v okolju Conda ustvarili pre- prost program v programskem jeziku python, kjer smo se posluˇzili funkcij znotraj osmnx.graph modula, ki ga ponuja OSMnx. Grafe smo zaradi koliˇcine dodatnih informacij shranili v GraphML formatu.
Slika 3.12: Obmoˇcje, znotraj katerega smo zajeli podatke za izdelavo cestnega omreˇzja Ljubljane, prikazano na strani projekta OpenStreetMap.
3.10 Jezikovna omreˇ zja
3.10.1 Opis omreˇ zij
Izdelana jezikovna omreˇzja predstavljajo omreˇzja slovenskih besed, vir kate- rih je bil Inˇstitut za slovenski jezik Frana Ramovˇsa. Besede so so med seboj povezane glede na njihovo Levenshteinovo razdaljo.
Levenshteinova razdalja je metrika, ki meri razliko med dvema zapored- jema znakov. V naˇsem primeru meri razliko med dvema besedama, kjer ta predstavlja najmanjˇse moˇzno ˇstevilo dodanih, izbrisanih ali pa spremenjenih ˇcrk, ki ga potrebujemo, da eno besedo spremenimo v drugo.
Za primer lahko vzamemo besedi “jeˇz” in “mreˇza”. ˇCe besedi “jeˇz” naj- prej ˇcrko ‘j’ spremenimo v ‘m’, dobimo “meˇz”. Nato na drugo mesto dodamo
