IZBRANI PRISPEVKI 051 2QOA
0n ■ «v» ■■ * i v««
Dinamični prikaz casovmn omrežij
Darko Brvar1. Andrej Mrvar in Vladimir SaLagelj3 Univerza v Ljubljani
Univerzitetni podiplomski študijski program statistika1
Fakulteta za družbene vede3 Fakulteta za matematiko in fiziko3
darko.brvar®siol.net, andrej.mrvar®fdv.uni-lj si, vladimir.batagelj@fmf.uniTj.si
Povzetek
Časovna omrežja lahko prikažemo statično ali dinamično. Pri statičnem prikazu omrežje prikažemo s sliko ali zaporedjem slik. pri dinamičnem pa gre za zvezno prehajanje med časovnimi rezinami omrežja, kjer sledi prednjih slik omrežja postopno izginjajo. Statične prikaze časovnih omrežij lahko izdelamo s programskim paketom Pajek. V članku bomo predstavili program PajekToSvgAnim, ki temelji na slikovnem |eziku SVG m programskem jeziku Python in ki je programski dodatek programskemu paketu Pajek za dinamični prikaz časovnih omrežij. Prikazali bomo delovanje programa PajekToSvgAnim na nekaterih znanih primerih časovnih omrežij.
Abstract
DYNAMIC VISUALIZATION OF TEMPORAL NETWORKS
Temporal networks can be visualized statically or dynamically. While static visualization presents networks with pictures, dynamic visualization shows continuous passes of networks between time points with traces of previous network pictures. Static visualization can be produced using program package Pajek. We will present program PajekToSvgAnim. based on graphical languege SVG and programming language Python, as addition to program package Pajek for dynamic visualization of temporal networks. Program PajekToSvgAnim will be demonstrated on some well-known examples of temporal networks.
1 Časovna omrežja
1.1 Definicija grafa in omrežja
Graf G je definiran kot par G = (V, /,), kjer je V množica točk in / množica povezav. Povezave so lahko usmerjene ali neusmerjene. Predpostavljamo, da je bralec seznanjen z osnovami teorije grafov (na primer 112|).
Graf postane omrežje, če vsebuje dodatne podatke o točkah in/ali povezavah. Omrežje N lahko torej definiramo kot četverico množic N=(V, L, Fv, /', ), kjer je V množica točk, L množica povezav, Fv množica lastnosti točk in Ft množica lastnosti povezav.
Množica lastnosti točk Fv je množica funkcij f: V ->X, kjer množica X lahko predstavlja množico oznak
točk, razbitje točk ali množico Številskih lastnosti točk. Na sliki lahko številsko lastnost prikažemo kot velikost točke ali njeno koordinato, imensko lastnost pa kot barvo, obliko lika ali kot oznako točke.
Množica lastnosti točk F, pa je množica funkcij g: L -> Y, kjer je Y množica Številski h lastnosti povezav. Na sliki jih prikažemo /. izpisom vrednosti, debelino črte ali sivino.
Primer: Na sliki l.la je prikazan graf z množico točk (a, b, c, d, e), množico usmerjenih povezav [(a, b), (a, c), {b, c), (d, e)) in množico neusmerjenih povezav [(b: d),(c: d)}. Na sliki t.lb pa je prikazan isti graf z imensko lastnostjo točk (razbitjem), predstavljeno z dvema barvama ter s številsko lastnostjo povezav,
Stika 11 a Primer grafa
Slika 1 1b Graf i dodatnimi lastnostmi
2006 - Številka 3 - lelnik XIV
ueontBN* INFORMATIKA 147
Darka Brvar, Andrej Mrvar, Vladimir Satagelj Dinamični prikaz časovnih omreiij
predstavljeno z različnimi debelinami (barve niso razvidne zaradi črnobelega tiska, zato se Članek nahaja tudi na spletni strani |2|).
1.2 Definicija časovnega omrežja
Časovno omrežje je omrežje, v katerem se prisotnost posameznih točk in povezav pa tudi njihove lastnosti spreminjajo skozi čas. Zato ga laiiko definiramo na naslednji način:
Časovno omrežje N, definiramo kot peterico množic iV(-{V, L, Fv, Fl, T), kjer je V množica točk, /. množica povezav, Fy množica lastnosti točk, F, množica lastnosti povezav in 7* množica linearno urejenih časovnih trenutkov.
Točke in povezave, ki pripadajo časovnemu omrežju, niso nujno prisotne v vseh časovnih trenutkih. Pri tem velja logična omejitev, da je povezava prisotna v določenem časovnem trenutku, če sta v tem trenutku prisotni tudi obe njeni krajišči.
1.3 Časovna socialna omrežja
Pri analizi časovnih socialnih omrežij se zanimanje vrti okrog razumevanja, kako se omrežje razvija in spreminja skozi čas, in okrog iskanja načinov za razvoj modelov socialnih procesov, ki bi pomagali pojasniti opažene strukture (Doreian el al. ¡ii|). Jedro zanimanja je torej dinamika medosebnih odnosov, ki je pomembna za razumevanje socialnega omrežja. Pri tem se pojavi problem, da se te dinamike ne da na zadovoljiv način prikazati s statičnim prikazom (Bear-man, Everett [4]). Rešitev je dinamični prikaz časovnih omrežij, ki raziskovalcem odpira vrata na naslednjih področjih:
• pri odkrivanju značilnosti razvoja omrežja,
■ pri spremljanju razvoja izbranih delov omrežja (tirov),
• pri odkrivanju izstopajočih delov omrežja.
2 Slikovni jezik SUG
Jezik SVG (Ferraiolo et al. \7\) je označevalni jezik za opis vektorskih slik, s katerim je mogoče izdelati spletne strani, ki vključujejo slike z visoko ločljivostjo. Ima Številne dobre lastnosti:
• slike v SVG so vektorske (brez izgube ločljivosti pri transformacijah),
. datoteke .SVG imajo manjšo velikost, kar pomeni hitrejše nalaganje, in lahko jih pregledujemo kar s spletnim brskalnikom, v katerega prej namestimo prosto dostopen dodatek za pregledovanje.
• v spletnem brskalniku deluje tudi iskanje nizov/ besedil v sliki SVG,
* osnova jezika SVG je označevalni sestav XM1„ ki ima danes že vodilno vlogo pri izmenjavi najrazličnejših podatkov na spletu in tudi drugje.
2.1 Zgradba opisa SVG
Opis SVG lahko definiramo kol samostojno datoteko ali kot vgrajeno datoteko v spletni strani. Spodnji primer predstavlja samostojno datoteko .SVG:
<3OOCTVPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"
"http://www.w3.0rg/Graphics/SVG/l,1/DTD/ svgll.dtd">
.
Prva vrstica vsebuje najavo XML glede na to, da je jezik XML osnova jezika SVG. Druga in tretja vrstica vsebujeta povezavo z opisom 'slovnice' jezika SVG (angl. Document Type Definition ali krajše DTD), ki mora biti tako kot najava XML sestavni del vsake datoteke .SVG.
Četrta in peta vrstit a vsebujeta značko SVG, ki označuje, da gre za opis SVG. Značka SVG ima naslednje lastnosti:
• xlmns:
obvezna lastnost, ki določa imenski prostor jezika SVG,
• height in width:
določata velikost okna SVG na zaslonu,
• x in y:
določata položaj okna SVG na zaslonu (jezik SVG ima privzeti koordinatni sistem postavljen tako, da je koordinatno izhodišče v zgornjem levem vogalu zaslona).
Opis SVC lahko vključimo v spletno stran tudi z datoteke:
.
Iz primera lahko vidimo, da ima značka animate naslednje lastnosti:
• attributeName:
ime lastnosti nadrejenega objekta, ki se ji spremeni vrednost; . from in to:
stara in nova vrednost te lastnosti;
• begi n:
začetek dinamičnega prikaza spremembe vrednosti lastnosti;
• dur:
trajanje animacije; . f i 11:
izbira, ki vpliva na to, ali nadrejeni objekt po koncu dinamičnega prikaza ohrani novo vrednost lastnosti (freeze) ali jo zamenja s staro vrednostjo (remove).
S
Slika 2 1 Dve točki in povezava med njima na lačelku in na koncu dinamičnega prikaza
3 Program PajekToSugAnim
Program PajekToSvgAnim (Brvar (51) je programski dodatek programskemu paketu Pajek (Batagelj, Mrvar [3], [8], 11()|) za pripravo dinamičnih opisov v SVG razvoja časovnih omrežij. Iz vhodne Pajkove projektne datoteke .PAJ izdela datoteke .SVG, .SVG.GZ in .HTML {datoteka .SVG.GZ je stisnjena oblika GZIP datoteke .SVG, ki omogoča hitrejše nalaganje in hitrejši prikaz objektov SVG).
Program je napisan v programskem jeziku Python {Van Rossum 1111). Python je tolmačenj interaktivni objektni programski jezik in tako kot programski jezik Java omogoča izdelavo modulov, razredov, izjem
?006 - Številka 3 - Iptnik XIV
u p o p t h n i INFORMATIKA 14?
Darko Brvai, Andrej Mrvar. Vladimir Batagelj Dinamični prikar časovnih omrežij
in dinamičnih podatkovnih tipov. Omogoča tudi izdelavo samostojno izvedljivih prevedenih programov.
Na začetku vhodne Pajkove datoteke se nahajajo podatki o celotnem omrežju, torej o vseh točkah in povezavah skupaj z njihovimi lastnostmi. Sledijo podatki o omrežjih v posameznih časovnih rezinah. Za ta omrežja so podani samo podatki o listih točkah in povezavah, ki so v rezini dejansko prisotne.
Na koncu vhodne datoteke se nahaja še točkovno razbitje, pri katerem za vsako točko navedemo, ali je v prikazu njena oznaka vidna ali ne (vrednost I: oznaka je vidna, vrednost (t: oznaka ni vidna).
Lastnosti točk in povezav v posameznih omrežjih so standardne lastnosti, ki so določene že v programskem orodju Pajek. Tako lahko točki določimo naslednje lastnosti:
■ oznako,
• kooordinati x in y (in /,),
• vrednost,
• obliko,
• razteg v smeri x,
• razteg v smeri v,
• barvo,
. interval(e) prisotnosti (npr. 11-3, 7, 12-15|}.
Povezavi pa lahko določimo naslednje lastnosti:
• začetno kraj išče (obvezen podatek),
■ končno krajišče (obvezen podatek),
■ vrednost,
• debelino (če ni podana, se privzame kar vrednost povezave),
• barvo,
■ interval(e) prisotnosti.
Program PajekToSvgAnim upošteva naslednje posebnosti časovnih omrežij:
• zvezno spreminjanje koordinat točk,
■ izginjanje točk in povezav in pojavljanje novih točk ili povezav glede na to, alt je določena točka oziroma povezava prisotna v določenem Časovnem trenutku, > spreminjanje velikosti točk in debelin povezav brez izgube ločljivosti,
• prikaz večkratnih omrežij na istih točkah.
V program je vgrajenih več izbir, ki se lahko določajo v slikovnem uporabniškem vmesniku {slika 3.1). Poleg osnovnih izbir vhodne Pajkove datoteke in imena ter poti izhodne datoteke .SVG omogoča še naslednje izbire:
- dolžino trajanja dinamičnega prikaza prehoda omrežja iz ene rezine v drugo (Slide tirne), . dolžino trajanja statičnega prikaza rezine pred dinamičnim prikazom prehoda v naslednjo rezino (Pause time),
• številski seznam dinamičnih prehodov med rezinami, ki naj se prikažejo (Animated slides).
Primer: Animated slides: 1,5-10, I2-*.
V tem primeru si prikazi omrežja sledijo v naslednjem vrstnem redu:
• dinamični prikaz prehoda od prve do d ruge rezine, . statični prikazi od druge do pete rezine,
• dinamični prikazi prehodov med peto do enajsto rezino (poleg vmesnih statičnih prikazov),
• statična prikaza enajste in dvanajste rezine,
• dinamični prikazi prehodov med dvanajsto in zadnjo rezino (poleg vmesnih statičnih prikazov);
Pajek -> Svg Animation Generator
File Svg Info
uda
Source c./pajektosvganim/linden.paj
Output: |c;/pajektosvganim/linden. svej
Slide time (in seconds) ji Animated slides:
Pause tune (in seconds): fl |i-*
Browse
Btowse
(for example: 1,5-10,12-*)
Real vertex si2e: * On Off Svg window size: 1784 x | S48 px ▼ (dots density: 96 DPI) Vertex label font size: fl2 !? Multiple relations checked on Html window toad
Line opacity:
1.0
Stâtvs: Source file checked.
Slika 3 1 Izbira vhodne Pajkove datotek« v programu PajekToSugflnim
150 uposiu*« INFORMATIKA 2006 - številka 3 - letnik XJV
Darko Brvar, Andrej Mrvar, Vladimir Batagelj Dinamični prikar časovnih omrežij
« možnost izbire med dvema velikostirna oblik točk: dejansko velikostjo, ki je podana v vhodni datoteki, in enotno velikostjo (Real Vertex Size On/Off),
• velikost pisave oznak točk (Vertex label font size), ■ velikost okna SVG (Svg window size),
• možnost izbire označitve relacij v spletnem sestavku z vgrajeno sliko SVG (ob vsaki naložitvi sestavka) v primeru večkratnega omrežja (Multiple relations checked on Html window load),
• ne prosojnost povezav (Line opacity).
Program najbolj preprosto uporabimo tako, da kar poženemo izdelavo datotek .SVG, .SVG.GZ in .HTMI. z ukazom Svg Generate. Ce je izdelava datotek uspešna, se prikaže ustrezno sporočilo. Dinamični prikaz si ogledamo tako, da odpremo izdelano datoteko .HTML, ki poleg okna SVG vsebuje še izbiro prikaza oznak točk in izbiro prikaza relacij v primeru večkratnega omrežja. Datoteka .HTML je povezana s stisnjeno datoteko .SVG GZ zaradi hitrejšega prenosa izdelanih objektov v oknu SVG.
V nadaljevanju si oglejmo nekaj primerov, v katerih lahko uporabimo eno ali več od zgoraj naštetih izbir.
1. Če si želimo bolj podrobno ogledati dinamične prikaze prehodov med rezinami, potem povečamo dolžino trajanja dinamičnega prikaza prehoda omrežja iz ene rezine v drugo. Privzeta dolžina trajanja je 1 sekunda.
2. Če nas zanimajo statični prikazi posameznih rezin, potem povečamo dolžino trajanja statičnega prikaza rezin. Privzeta dolžina trajanja je 1 sekunda.
3. Če ima omrežje veliko rezin, se večkrat osredotočimo le na nekaj dinamičnih prikazov prehodov med i/branimi rezinami in ne na vse prehode. V tem primeru si lahko pomagamo z možnostjo določitve številskega seznama dinamičnih prikazov prehodov, ki naj se prikažejo. Privzeti seznam je 1-"", kar pomeni dinamični prikaz vseh prehodov.
4. Možnost izbire med dejansko velikostjo točk, ki je podana v vhodni datoteki, in enotno velikostjo za vse točke je možnost, ki jo poznamo iz programskega paketa Pajek. Uporabimo jo, ko nas dejanske velikosti točk ne zanimajo ali pa ko so točke prevelike za prikaz.
5. Možnost izbire velikosti pisave oznak točk je klasična možnost, ki jo tudi poznamo iz programskega paketa Pajek. Privzeta velikost pisave je 12.
6. Če želimo dinamični prikaz vključiti v svojo spletno stran, si lahko pomagamo z možnostjo določitve vel i kt >s ti okna SVG. Prt tem lahko izbiramo med enotami cm, ineh, px. Privzeta velikost okna je velikost celotnega zaslona.
7. Če imamo opravka z večkratnim omrežjem z velikim številom relacij, se lahko /godi, da bit dinamični prikaz nepregleden. V tem primeru si pomagamo z možnostjo izbire označitve relacij v spletnem sestavku z vgrajeno sliko SVG, s katero lahko sami določimo, katero relacijo želimo prikazati. Po privzetem se prikažejo vse relacije.
8. Če omrežje vsebuje večkratne povezave, se lahko zgodi, da določene povezave na prikazu ne bodo vidne, ker bodo prekrite z drugo povezavo, ki povezuje isti točki. V programskem paketu Pajek je to rešeno z uporabo ukaza Net -> Transform SortLines —► LineValues -> Descending, ki uredi povezave po vrednosti padajoče, v programu Pajek-ToSvgAnim pa lahko določimo stopnjo ne prosojnosti povezav. Pri tem si lahko pomagamo z naslednjo lestvico:
1 - povezave so popolnoma ne prosojne, 0.75 povezave so delno prosojne, 0.5 - povezave so srednje prosojne, 0.25 - povezave so zelo prosojne,
t) povezave so popolnoma prosojne, torej nevidne.
Seveda lahko izberemo katerokoli vrednost od Odo 1, ne samo vrednosti iz lestvice. Privzeta vrednost je L
4 Primer uporabe programa PajekToSvgAnim
Na sliki 4.1 je narisan prikaz omrežja zgodb nadaljevanke Lindenstrasse (Mutzel [9], Batagelj |1]) z nepremičnimi točkami, izdelan s programom PajekToSvgAnim, za prvo rezino (prva zgodba) in malo zatem, ko se že rahlo opazi jo točke in povezave, ki so prisotne šele v drugi rezini (druga zgodba). Delno prosojne na novo prihajajoče točke in povezave (npr. točka z oznako v209 in povezava od Le točke do točke z oznako Dr. Ludwig Dressler) postajajo tem bolj vidne, čim bolj se bliža druga rezina. Več takih spletnih prikazov (v barvah) je dosegljivih na spletni strani (Batagelj [2|).
5 Sklep
Zaradi povečanega zanimanja za raziskovanje časovnih omrežij in zaradi dejstva, da prikaz omogoča boljši
20UA številko 3-tetnik XIV
UHoftte», INFORMATIKA 151
Darlto Brvar, Andrti Mrvar. Vladimir Balagdj Dinamični prikaz časovnih omrežij
Klaus Beim er
l_Beimar Schilfer
\ f iv19S
Bonny Qeimer
Marion Bei mer Vasily Sarikakis
^t.lnftrhi Rfsnn
Else Kiing LudwiC. DiWslOr kEgo\Kling
P Berta Griese
v205
220
^Joschi Bennarsch
^Gabi Zenker gob Skawowski CjeiiB Kronmayr
J> v222
¿-^Sigi Kronmayr ' Philo Bennarsch
LEGENDA __partnerska rotacija
_____družinska relacija
....................poslovna relacija
____prijateljska relacija
„ .. _ . relacija mod osebami, ki se no maraio
Slika 4 1 Prikai prve rezine omrežja Lindenstrasse z nepremičnimi točkami, izdelan s programom PajefcToSugAnim, in med prehodom
vpogled v značilnosti omrežij tako pri začetnem raziskovanju omrežij kot tudi pri predstavitvi rezultatov raziskav, se je v zadnjem času pojavila potreba po dinamičnem prikazu omrežij.
V ta namen je bil izdelan PajekToSvgAnim kot programski dodatek programskemu paketu Pajek /a dinamični prikaz časovnih omrežij.
S pomočjo programa PajekToSvgAnim lahko izdelamo zvezne prehode časovnih omrežij med časovnimi rezinami. Pri posameznem prehodu omrežja iz ene rezine v drugo se vidijo sledi prejšnjih slik omrežja, torej sledi tistih točk in povezav omrežja, ki v naslednji rezini niso več prisotne. To nam omogoča, da lahko bolj natančno sledimo spremembam omrežja skozi
152 ui-orab** informatika 2006 • Številka 3 - tetnik XIV
Darko Brvar. Andrej Mrvar, Vladimir Batagelj: Dinamični prtkai časovnih «mreiij
čas kot doslej/ ko smo imeli na voljo le statične slike omrežja.
Program PajekToSvgAnim ima za različne potrebe uporabnikov vgrajenih kar nekaj izbir, ki se lahko določajo v slikovnem uporabniškem vmesniku. Če si želimo npr. bolj podrobno ogledali dinamične prikaze prehodov med rezinami, povečamo dolžino trajanja dinamičnega prikaza prehoda omrežja iz enega rezine v drugo. Če želimo dinamični prikaz vključiti v svojo spletno stran, si lahko pomagamo z možnostjo določitve velikosti okna SVG. Če pa imamo opravka / večkratnim omrežjem z velikim številom relacij, uporabimo možnost izbire označitve relacij v spletnem sestavku z vgrajeno sliko SVG, s katero lahko sami določimo, katere relacije želimo prikazati.
6 Uirt in literatura
[1] BATAGEU. Vladimir: Pajek Datasets.
[URL: http ://Vlado. fm f. u n i - Ij. si/pu b/n et works/d ata/l.
[2] BATAGEU. Vladimir: Pajek to SI/G Anim.
[URL: http://vlado.fmf.uni-li.5i/oub/networKs/paieK/ sygAnirri/].
[3] BATAGEU, Vladimir, MRVAR, Andrej: PAJEK 1.02. Program for Large Network Analysis.
[/1] BEARMAN, R, EVERETT, K.: The Structure of Social Protest. Social Networks 15, 1993, str. 171.
[5] BRVAR, Darko: Dinamični prikaz časovnih omrežij. Magistrsko delo. Ljubljana, 2005.
[6] DOREIAN, R, KAPUSCINSKI, R„ KRACKHARDT, D., SZCZYPULA, J,: A Brief History of Balance Through Time. Journal of Mathematical Sociology 21(1-2), 1996, str. 113.
[7] FERRAIOLO, J., JUN, F„ JACKSON, D.: Scalable Vector Graphics (SVG) 1.1 Specification. W3C Recommendation.
[URL: htto://www. w3 .o rg/TR/2003/R EC - SVG 11-2QQ30114/1
[8] MRVAR, Andrej: Analiza in prikaz velikih omrežij. Doktorska disertacija. Ljubljana, 1999.
¡9] MUTZEL, R: GD99 contes!.* Lindenstrasse network, 1999.
[URL: htto://kam.mff .cunI.c?/conferencea/GD99/contast/ graphs/A.htmll
[10] de NOOY, Wouter, MRVAR, Andrej, BATAGEU, Vladimir: Exploratory Social Network Analysis with Pajek. New York: Cambridge University Press, 200b
[11] VAN ROSSUM, G.: Python. [URL:
[12] WILSON, Robin. J., WATKINS, John J,: Uvod v teorijo grafov. Sigma, št. 63, DMFA Slovenije, Ljubljana, 1997.
Mag Darko Brvar je univerzitetni diplomirani inženir matematike. Konec leta 2005 |e zaključil podiplomski Študij statistike, smer družboslovna statistika Ukvarja se z dinamičnim prikazom časovnih omrežij. Ternu magistrskega dela je predstavil Si rži strokovni |avnosti na Dnevih slovenske informatike aprila 2006.
m
Doc. dr. Andrej Mrvar je zaposlen na Fakulteti za družbene vede kjer predava predmete s področia informatike in analize podatkov. Ukvarja se predvsem s teorijo grafov, algoritmi na grafih io omrežjih in analizo podatkov. Je soavtor programa za analizo in prikaz velikih omrežij Pajek. Letos |B pri založbi Cambridge University Press izšla monografija W de Nooy, A. Mrvar. V Bsiagelj: Exploratory Social Network Analysis with Pajek.
■
□r Vladimir Batagelj je zaposlen kot redni profesor na Fakulteti za matematiko in fiziko, kjer predava predmete s področja diskretne in računalniške matematike Ukvaria se predvsem s teorijo grafov, algoritmi na grafih in omrežjih, kombinatoričnn optimizacijo, analizo podatkov in uporabo informacijske tehnologije v izobraževanju. Je član več domaČih in mednarodnih strokovnih združenj, Sam ali kot soavtor je napisal več visokošolskih in srednješolskih učbenikov, priročnikov in poljudnih del. Številne znanstvene, strokovne in poljudne članke. Je soavtor programe za analizo io prikaz velikih omrežij Pajek
2006 - številka 3 - felnik XIV
UPtiBiB«* INFORMATIKA 153