IV124 Komplexní sítě Eva Výtvarová, Eva Hladká Fakulta informatiky, Masarykova univerzita 2. května 2017 Temporální sítě Motivace • reálné sítě sestávají z kontaktů, které se v čase proměňují • statická síť nezachycuje informaci o posloupnosti a vzdálenosti v čase komunikační sítě, face-to-face interakce, neurální sítě, ekologické sítě a interakce mezi druhy, ... 2of 19 Temporální sítě - motivace1 © © © © ®-® © ©t1i ®-©t2 ©^© © 0 © ©-© © ©M © © © © © © © ©tl: © (i t2: i © ©-© ©"Ota © © © ©-© . ©-® ® ® t5 i t6 © © © © ©t7 !© ©-© i © ©t8 b) T = 240 min, a) Ař = 60 min, b) At = 30 min Q ,1 Nicosia V., 2013 3 of 19 J_ • struktura sítě = řečiště • dynamická síť = změny řečiště (síť přátel) • temporální síť = říční tok (síť setkávání a komunikace) .iSaramáki, 2014 Sítě temporální, časově proměnné [0,7] = = <^2, • • • , G/tf}j Gm - snapshot (řez, snímek) sítě Zpravidla ekvidistantní řezy fm+1 = tm + Aí, AT? = 1, . . . , M. ít! ÍO ^ plně popsán • maticemi sousedností A(tm) • výčtem událostí (událost e = (/,/, ř, Jí) mezi uzly /,/, počátek kontaktu 0 < t < Ta jeho trvání St) 5of 19 Temporální měřítko časové okno velikosti At • At = T... statická síť • At -^0 ... nekonečná sekvence okamžitých sítí • doporučené: maximální možné časové rozlišení ? víceškálové systémy využití poznatků zpracování signálů, teorie informace, analýz časových řad, granularity modelu, segmentace časových řad, ... 6of 19 Temporální měřítko - příklad3 35 min 10 min 5 min 4 / / 1 / / --* \ J > J 1 min ' etc. 3J§ender-deMoll S., 2006, Sulo Caceres R., 2013 Hodnocení topologie - souvislost • temporálně silně souvislá komponenta uzlu /': v orientovaném grafu uzel / temporálně dosažitelný z ostatních uzlů komponenty v čase [0, T], všechny uzly komponenty dosažitelné z / • temporálně slabě souvislá komponenta uzlu /': / temporálně dosažitelný z ostatních uzlů komponenty a naopak; v příslušné neorientované temporální síti 8of 19 Metriky - temporální cesty I Vij = {e//c(ři), ew(fe),..., exj{tL) \ U < t2 < ■ ■ ■ < tL} • topologická / temporální délka cesty = počet kontaktů / čas mezi / a j • temporální vzdálenost (latence) d-,j = temporální délka nejkratší temporální cesty • temporální diametr sítě D = max,jd,j • NE reciprocita, NE tranzitivita, časová závislost 9of 19 Metriky - temporální cesty II A B B D D D T=0 T=l 1=2 ► Time T=3 4 uzel často temporálně nedosažitelný z jiného, tj. d j j = oo, proto temporální (globálni) efektivita S = N^_^ J2íj k in^ngJ..20Q9 _ Metriky - shlukovací koeficient schopnost událostí perzistovat napříč snímky Cj(tm, Wi) topologický překryv okolí uzlu lokální shlukovací koeficient globální shlukovací koeficient Metriky - centralita5 . mezilehlost: Cf = E/^Eto;2^ Užitečné vzít v úvahu interval, během kterého informace čeká v uzlu před posláním dál • blízkost: C,c = ^4 • broadcast, receive centralita: ne vše se šíří po nejkratších cestách; odhalení šiřitelů a hlavních příjemců informace ^icosia V, 2013, Holme & Saramäki, 2013 Statickä vs. temporälnf centralita ENRON6 150, 122, 053, 107, 127 075, 147, 013. 048, 067 ID Name Hole Notes 9 Stephanie Pamis (Unknown) 13 Marie Heard Legal Senior Legal Specialist 17 Mike Grigsby Manager 48 Tan a Jones Executive 53 John Lavorato Trader 54 Greg Whalley President Former Head of Trading 67 Sara Shackleton Vice President Enron Wholesale Services 73 Jeff Dasovich Trader 75 Gerald Neniec Director of Trading 107 Louise Kitchen Trader Head of Online Trading 122 Sally Beck Managing Director 127 Kenneth Lay Chairman & CEO 139 Mary Hain Director 147 Carol Clair Trader 150 Liz Taylor Secretary Assistant to Greg Whalley 150, 122, 053, 127, 049 107, 053, 048, 113, 139 13 Of Jjing J., 2010 Metriky - komunitní struktura • přeskupení soudržných skupin • formování nových skupin • fragmentace existujících • maximalizace optimalizační funkce, parametry prostorového a temporálního rozlišení ^Řassett D.,2013_ Výbušnost (burstiness) bursty waiting time to next event long I i Poisson B t time waiting time to next event short temporální nehomogenita události se v čase shlukují B =