Úvod Vlastnosti sítí Modely Procesy Závěr Modelování komplexních sítí Radek Pelánek Úvod Vlastnosti sítí Modely Procesy Závěr Úvodní poznámky Souvislosti další typ aplikace modelování a simulace nemodelujeme konkrétní systém, ale obecný jev, vlastnost společnou mnoha systémům (srovnej fyzikální zákony) ilustrace obecných principů komplexních systémů (např. mocninný zákon) Úvod Vlastnosti sítí Modely Procesy Závěr Úvodní poznámky Komplexní sítě komplexní síť (např. sociální sítě, regulační sítě exprese genů, Internet) = rozsáhlý graf společné vlastnosti – např. vzdálenosti, stupně vrcholů abstraktní modely (vesměs výpočetní) Úvod Vlastnosti sítí Modely Procesy Závěr Úvodní poznámky Historické poznámky do 90. let: modelem náhodné grafy druhá polovina 90. let: dostatek sítí v elektronické podobě, možnost jejich počítačové analýzy konec 90. let: první modely komplexních sítí knihy: Linked (V pavučině sítí), A-L Barabási, 2002 Small Worlds, Six degrees, D Watts, 2003 Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Internet uzly: servery, hrany: dráty Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Firmy uzly: firmy, hrany: obchodují spolu, sdílejí šéfy, ... Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Firmy http://j-node.blogspot.cz/2011/10/network-of-global-corporate-control.html Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Sociální sítě uzly: lidé, hrany: známost Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Síť sexuálních vztahů uzly: lidé, hrany: sexuální styk Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Spolupráce organizátorů volnočasových akcí Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Vědecká spolupráce uzly: vědci, hrany: spoluautorství (viz též Erd˝os number) Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Buněčná biologie uzly: proteiny, (příp. další látky), hrany: reagují spolu Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Potravní řetězce uzly: zvířata, hrany: pokud jedno žere druhé Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Úvod Vlastnosti sítí Modely Procesy Závěr Příklady Příklady komplexních sítí – přehled oblast uzly hrany Web stránky odkazy internet servery dráty elektrické sítě transformátory dráty telefonní hovory telefony volání vědecká spolupráce vědci spoluautorství síť herců herci hráli v jednom filmu síť sexuálních kontaktů lidé sex citační sítě vědecké články citace potravní řetězce druhy zvířat vztah lovec-kořist metabolismus chemické látky reakce neuronové sítě neurony synaptické spojení lingvistika slova konotace, synonyma Úvod Vlastnosti sítí Modely Procesy Závěr Pojmy teorie grafů Grafy graf G = (V , E) V je množina uzlů (vrcholů) E je množina hran orientované hrany: E ⊆ V × V neorientované hrany: E ⊆ V 2 Úvod Vlastnosti sítí Modely Procesy Závěr Pojmy teorie grafů Grafy: základní pojmy cesty, vzdálenosti stupeň vrcholu dv = počet hran z vrcholu v vycházejících (u orientovaných grafů rozlišujeme výstupní stupeň a vstupní stupeň) distribuce stupňů P(k) – pravděpodobnost, že náhodně vybraný uzel má stupeň k Úvod Vlastnosti sítí Modely Procesy Závěr Pojmy teorie grafů Typické vlastnosti komplexních sítí malé vzdálenosti (vlastnost malého světa, small world fenomenon) shlukování (clustering) bezškálovitost (scale-free) „motivy Úvod Vlastnosti sítí Modely Procesy Závěr Malý svět Malý svět „malý svět ∼ potkáte cizího člověka a po chvíli zjistíte, že máte společné známé průměrné nejkratší vzdálenosti mezi uzly v komplexních sítích jsou „malé Úvod Vlastnosti sítí Modely Procesy Závěr Malý svět Milgramův experiment Stanley Milgram, 1967 60 balíčků, z Kansasu do Massachusetts balíčky povoleno posílat jen známým osobám (známost na úrovni křestního jména ∼ tykání) identifikace adresáta: jméno, zaměstnání, přibližné místo bydliště cíl: co nejrychleji k adresátovi Úvod Vlastnosti sítí Modely Procesy Závěr Malý svět Šest stupňů odloučení balíčky, které došly, přišly průměrně na šest kroků experiment měl poměrně dost vad, ale i tak se výsledek zprofanoval (a teprve později potvrdil) „šest stupňů odloučení pozn. též divadelní hra, film viz též Erd˝os number, Bacon number Úvod Vlastnosti sítí Modely Procesy Závěr Shlukování Shlukování lidé mají tendenci tvořit shluky znám Pepu a Frantu ⇒ je pravděpodobné, že Pepa zná Frantu nejen sociální sítě Úvod Vlastnosti sítí Modely Procesy Závěr Shlukování Shlukování formálněji uzel v má kv sousedů ev = počet vzájemně propojených sousedů koeficient shlukování: Cv = ev kv 2 = 2ev kv (kv − 1) Úvod Vlastnosti sítí Modely Procesy Závěr Shlukování Koeficient shlukování: příklad Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Distribuce stupňů Existuje typická hodnota, kolem které se stupeň uzlů pohybuje („škála grafu )? náhodné grafy ⇒ ano komplexní sítě ⇒ ne Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Poisson a mocninný zákon: příklad A.-L. Barabási: V pavučině sítí Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů „Typické uzly Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Distribuce stupňů formálněji Poissonova distribuce (pro velké λ ∼ normální distribuce) P(n) = λn e−λ /n! Mocninný zákon P(n) ∼ n−γ Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Poissonova distribuce, mocninný zákon 0 0,02 0,04 0,06 0,08 0,10 0,12 0,14 0,16 0,18 0,20 0,22 2 4 6 8 10 12 14 16 18 20 Poissonova distribuce mocninný zákon Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Poissonova distribuce, mocninný zákon Poissonova distribuce mocninný zákon Wikipedia Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Příklady mocninného zákona rozdělení bohatství (Paretův princip) velikost meteoritů, záplav, požárů, zemětřesení, ... frekvence použití písmen, slov v jazyce; noty v hudebních skladbách jména v populaci velikost měst management: zákon 80-20 (produkce – zaměstnanci, rozhodnutí – čas porady) Mocninný zákon často souvisí s přítomností pozitivních zpětných vazeb. Dokážete je pojmenovat? Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Příklad: Hamlet The, 1101; And, 898; To, 726; Of, 657; I, 561; You, 544; My, 508; A, 498; In, 414; It, 414; That, 389; Is, 334; Not, 315; This, 296; His, 292; But, 265; With, 257; For, 247; Your, 242; Me, 235; As, 228; Be, 226; Lord, 218; He, 216; What, 203; So, 197; Him, 189; Have, 179; Will, 169; Do, 150; No, 143; We, 140; Are, 131; On, 125; O, 121; Our, 119; By, 116; Shall, 114; If, 113; Or, 112; All, 110; Good, 109; Come, 104; Thou, 103; Now, 97; From, 95; More, 95; They, 95; Let, 94; How, 88; Thy, 87; Her, 86; At, 84; Was, 83; Most, 82; Like, 80; Would, 80; Hamlet, 78; Well, 78; There, 76; Know, 74; Sir, 74; Them, 74; May, 71; Tis, 71; Go, 70; Us, 69; King, 67; Love, 66; Did, 65; Very, 64; Speak, 63; Which, 63; Hath, 62; Then, 62; Why, 62; Must, 61; Thee, 59; Give, 58; Should, 58; An, 57; Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Mocninný zákon v komplexních sítích komplexní sítě: pár hodně propojených uzlů, většina uzlů má malé propojení webové stránky citační sítě sociální sítě bezškálovitost (scale-free) – neexistuje typická hodnota (škála) Úvod Vlastnosti sítí Modely Procesy Závěr Distribuce stupňů Vlastnosti sítí – výzkum Úvod Vlastnosti sítí Modely Procesy Závěr Další vlastnosti Assortativity korelace r mezi stupni vrcholů M.E.J. Newman. Assortative mixing in networks Úvod Vlastnosti sítí Modely Procesy Závěr Další vlastnosti Motivy podgrafy vyskytující se daleko častěji než v náhodném grafu různé motivy pro různé typy sítí většina komplexních sítí má nějaké motivy Úvod Vlastnosti sítí Modely Procesy Závěr Další vlastnosti Úvod Vlastnosti sítí Modely Procesy Závěr Další vlastnosti Váhy hran hrany různě důležité váhy hran: internet: množství přenesených dat mezi počítači sociální sítě: četnost sociálních kontaktů proteiny: frekvence reakcí váhy hran mají také distribuci podle mocninného zákona Úvod Vlastnosti sítí Modely Procesy Závěr Další vlastnosti Význam slabých hran silné hrany tvoří shluky slabé hrany propojují tyto shluky význam např. při shánění práce Úvod Vlastnosti sítí Modely Procesy Závěr Další vlastnosti Analýza sociálních sítí social network analysis studováno dlouho – donedávna však data pouze v malém (dotazníky) nyní data ve velkém (mobily, e-maily, Facebook, ...) analýzy: metriky centrality, detekce shluků komerční využití: mobilní operátoři a nabídky zákazníkům doporučující algoritmy Úvod Vlastnosti sítí Modely Procesy Závěr Další vlastnosti Míry centrality Kdo je klíčovou osobou ve skupině? Co jsou centrální uzly v grafu? degree centrality ∼ stupeň vrcholu closeness centrality ∼ jak moc uprostřed, průměrná vzdálenost k ostatním vrcholům betweeness centrality ∼ jak moc propojuje ostatní, kolik nejkratších cest vede přes vrchol hubs and authorities a další . . . Úvod Vlastnosti sítí Modely Procesy Závěr Modely komplexních sítí komplexní sítě mají typické vlastnosti dokážeme tyto vlastnosti modelovat na abstraktní úrovni? Úvod Vlastnosti sítí Modely Procesy Závěr Úrovně abstrakce sociální skupina web interakce proteinů konkrétní systém model konkrétního systému obecný model sítě bezškálovité sítě uzly: lidé hrany: známosti uzly: stránky hrany: odkazy uzly: proteiny hrany: reakce Úvod Vlastnosti sítí Modely Procesy Závěr Modely komplexních sítí náhodné grafy (Erd˝os-Renyi model) grafy malého světa (small-world graphs, Watts-Strogatz model) bezškálovité sítě (scale-free networks, Barabási-Albert model) modely jednoduché, umožňují simulaci i částečné analytické řešení Úvod Vlastnosti sítí Modely Procesy Závěr Náhodné grafy Náhodné grafy Erd˝os-Renyi model: množina vrcholů V , počet hran m z množiny potenciálních hran V 2 vybereme náhodně m hran Alternativní definice (zhruba ekvivalentní): množina vrcholů V , pravděpodobnost p pro každou dvojici vrcholů vložíme hranu s pravděpodobností p Úvod Vlastnosti sítí Modely Procesy Závěr Náhodné grafy Zajímavé výsledky „téměř všechny grafy mají vlastnost Q = pravděpodobnost se blíží k 1 (v limitě pro n → ∞) pro hodně vlastností fázový přechod: grafy s pravděpodobností hran p ⇒ téměř všechny mají danou vlastnost nebo ji nemají (např. souvislost) skokový přechod NetLogo: Networks / Giant Component: náhodný graf, velikost největší komponenty Úvod Vlastnosti sítí Modely Procesy Závěr Náhodné grafy Vlastnosti průměrná délka cesty: ∼ log n distribuce stupňů: Poissonova distribuce shlukování: průměrný shlukovací koeficient C ∼ p ∼ m n , výrazně méně než u reálných komplexních sítí vlastnosti reálných sítí: splňují malý svět, nesplňují ostatní Úvod Vlastnosti sítí Modely Procesy Závěr Grafy malého světa Grafy malého světa (Small-world graphs, Watts-Strogatz model) 1 pravidelná inicializace: N vrcholů, uspořádáme do kruhu, každý spojíme s K sousedy (K/2 na každé straně) 2 náhodné předrátování: ∀ hrany – s pravděpodobností p nahradíme náhodnou hranou Úvod Vlastnosti sítí Modely Procesy Závěr Grafy malého světa NetLogo: Networks / Small Worlds Úvod Vlastnosti sítí Modely Procesy Závěr Grafy malého světa Vlastnosti průměrná délka cesty ∼ log N (pro vhodné p, přesná charakteristika složitá) shlukování: pro p = 0 máme C = 3(K−2) 4(K−1) , pro větší p trochu menší, ale stále dosti velké (reálné) distribuce stupňů ∼ Poissonova distribuce (přesná charakterizace složitá), jiná než u reálných komplexních sítí Úvod Vlastnosti sítí Modely Procesy Závěr Grafy malého světa Mezi řádem a náhodou Úvod Vlastnosti sítí Modely Procesy Závěr Bezškálovité sítě Bezškálovité sítě (scale-free networks, Barabási-Albert model) 1 začít s malým množstvím vrcholů a hran 2 postupně přidávat vrcholy, nově přidaný vrchol je spojen k hranami 3 upřednostněné připojení (preferential attachment): pravděpodobnost, že bude vrchol vybrán je úměrná jeho aktuálnímu stupni Π(ki ) = ki Σkj NetLogo: Networks / Preferential Attachment Úvod Vlastnosti sítí Modely Procesy Závěr Bezškálovité sítě Vlastnosti průměrná délka cesty: ∼ log N distribuce stupňů: mocninný zákon (pro základní model s fixním γ = 3) shlukování: větší než u náhodných grafů, ale klesá s velikostí grafu (na rozdíl od Watts-Strogatz modelu), je menší než pro reálné sítě Úvod Vlastnosti sítí Modely Procesy Závěr Bezškálovité sítě Úvod Vlastnosti sítí Modely Procesy Závěr Bezškálovité sítě Poznámky proti předchozím dvěma modelům je zde důraz na vznik (růst) sítí – žádaná struktura vzniká jako vedlejší produkt upřednostněné připojení = pozitivní zpětná vazba důležitý postupný růst i upřednostněné připojení Úvod Vlastnosti sítí Modely Procesy Závěr Bezškálovité sítě Další modely rostoucích sítí nelineární Π(k) (upřednostněné připojení) počáteční atraktivnost stárnutí, způsobilost (fitness) rušení, přesměrování hran Úvod Vlastnosti sítí Modely Procesy Závěr Bezškálovité sítě Deterministický model bezškálovité sítě I Úvod Vlastnosti sítí Modely Procesy Závěr Bezškálovité sítě Deterministický model bezškálovité sítě II Úvod Vlastnosti sítí Modely Procesy Závěr K čemu to je? komplexní sítě mají zajímavé vlastnosti máme modely, které tyto vlastnosti (do určité míry) reprodukují Úvod Vlastnosti sítí Modely Procesy Závěr K čemu to je? komplexní sítě mají zajímavé vlastnosti máme modely, které tyto vlastnosti (do určité míry) reprodukují no a co? můžeme to nějak využít? Úvod Vlastnosti sítí Modely Procesy Závěr Procesy na sítích chyby, útoky, stabilita šíření epidemií, informací hledání v sítích spolupráce analýzu procesů provádíme zejména pomocí simulace Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Chyby, útoky, robustnost sítí robustnost sítě: jak se změní vlastnosti sítě (souvislost, průměrná vzdálenost) při odstranění určitých uzlů chyby = náhodně odstraněné uzly útoky = cíleně odstraněné uzly, většinou ty s největším stupněm Jaký vliv na robustnost má topologie sítě? Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Role klíčových uzlů Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Odolnost proti chybám a útokům Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Robustnost a topologie Bezškálovité sítě (oproti náhodným): vyšší odolnost proti chybám náchylnější proti útokům – „Achilova pata komplexních sítí Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Příklady Bezškálovité sítě s uvedenými vlastnostmi (odolnost proti chybám, náchylnost k útokům): komunikační sítě (Internet, www) ekonomické sítě (a např. teroristický útok na NY) proteiny – funkčnost vysoce propojených proteinů je životně důležitá Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Analýza nad daty: letecká doprava Eyjafjallajokull and 9/11: The Impact of Large-Scale Disasters on Worldwide Mobility http://rocs.northwestern.edu/projects/ resilience/eyjafjallajokull.html Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Letecká doprava – závěry studie velký dopad uzavření evropských letišť – spojnice regionů zranitelnost okrajových částí význam spojnic „mimo jádro sítě Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Dynamické efekty změna v síti může vyvolávat další změny např. elektrická energie v elektrické síti, energie v potravních řetězcích tok ovlivňuje funkčnost sítě jaká je robustnost sítě? jak souvisí s topologií sítě? Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Dynamické efekty narušení sítě může vést k neočekávaným důsledkům (vlivem zpětných vazeb) elektřina: výpadek celé sítě vlivem kumulace zátěže potravní řetězce: vyhubení predátora vedoucí k poklesu kořisti Úvod Vlastnosti sítí Modely Procesy Závěr Robustnost sítí Robustnost: příklady studovaných otázek Jaký je vliv stability/robustnosti a složitosti sítě? Jaký vliv na stabilitu ekosystému má složitost potravního řetězce (a potažmo biodiverzita)? Proč jsou potravní řetězce krátké? různé výsledky pro sítě modelované náhodně a sítě modelované realističtěji Úvod Vlastnosti sítí Modely Procesy Závěr Epidemie Šíření epidemií šíření počítačových virů po Internetu HIV po sexuální síti šíření náboženství, informací v sociální síti šíření nových technologií (na základě sociální sítě) (již jsme viděli: přednáška systémové modelování, cvičení, SIR, SIS, SIRS) Úvod Vlastnosti sítí Modely Procesy Závěr Epidemie Imunizace léky antiviry cenzura, inkvizice reklama Úvod Vlastnosti sítí Modely Procesy Závěr Epidemie Epidemie v homogenním prostředí V „homogenním prostředí (de facto náhodný graf): kritická hranice infekčnost menší ⇒ epidemie se nešíří infekčnost větší ⇒ epidemie se výrazně šíří uniformní imunizace Úvod Vlastnosti sítí Modely Procesy Závěr Epidemie Epidemie v bezškálovitých sítích neexistuje kritická hranice nemoc s velmi malou infekčností se může rozšířit – díky uzlům s vysokým stupněm uniformní imunizace je poměrně neúčinná cílená imunizace zasahující hlavně uzly s vysokým stupněm však může být velmi účinná Praktické poučení: např. pro boj s AIDS Úvod Vlastnosti sítí Modely Procesy Závěr Epidemie Epidemie v bezškálovitých sítích Úvod Vlastnosti sítí Modely Procesy Závěr Hledání v grafu Hledání v grafu vlastnost „malého světa – mezi většinou uzlů existují krátké cesty Jak tyto cesty najít? Milnerův experiment: nejen, že existuje krátký řetězec známostí účastníci experimentu jej byli schopni najít bez znalosti celého grafu, tj. jen za použití lokálních informací (srovnej ABM) Úvod Vlastnosti sítí Modely Procesy Závěr Hledání v grafu Kleinbergův model graf je založen na dvourozměrné mřížce, uzly spojeny se sousedy náhodně přidány dlouhé vazby informace o poloze v této mřížce je využívána pro navigaci směrem k cíli Úvod Vlastnosti sítí Modely Procesy Závěr Hledání v grafu Úvod Vlastnosti sítí Modely Procesy Závěr Hledání v grafu Hledání s využitím náhodné procházky velký a neznámý graf ⇒ náhodná procházka náhodná procházka (random walk) = vždy vybírá další uzel pro navštívení čistě náhodně bezškálovité grafy: cíleně preferujeme uzly s vyšším stupněm výsledky simulace: lepší pokrytí než čistá náhodná procházka aplikace: Gnutella (peer-to-peer filesharing system) Úvod Vlastnosti sítí Modely Procesy Závěr Hledání v grafu Úvod Vlastnosti sítí Modely Procesy Závěr Hledání v grafu Úvod Vlastnosti sítí Modely Procesy Závěr Další procesy Dynamika spolupráce v síti dilema vězně - dříve studováno v homogenním prostředí (každý s každým nebo pravidelná mřížka) jaký je vliv topologie sítě na vývoj spolupráce? pozorování: shlukování podporuje rozvoj spolupráce na grafech malého světa se spolupráci daří lépe než na náhodných grafech Úvod Vlastnosti sítí Modely Procesy Závěr Další procesy Další procesy na sítích buněčné automaty na sítích synchronizace formování názorů iterované hry Úvod Vlastnosti sítí Modely Procesy Závěr Shrnutí příklady komplexních sítí společné vlastnosti: krátké cesty, shlukování, bezškálovitost abstraktní modely: náhodné grafy, malý svět, bezškálovité sítě procesy na sítích: útoky, výpadky, epidemie, šíření informací, spolupráce, hledání chování modelů studováno pomocí simulace