IV124 Komplexní sítě Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 26. dubna 2018 Uvod náhodná sit binomická distr. ER model mame neco podobného pro bezskalovou sit? 2 of 16 Generovaní sítí s daným obecnější přístup: • na základě dané pk vygenerujeme sít • umožňuje vytvořit surogátní data k reálne síti • neříká nic o původu struktury samotné sítě Tři hlavní varianty: • konfigurační model • randomizace zachovávající stupeň • model se skrytým parametrem 3 of 16 Konfigurační model Postup: • zadána sekvence stupňů uzlů • hrany vygenerovány náhodně: dvojice pahýlků Vlastnosti • pravděpodobnost hrany mezi uzly / a j: 2\e\-i = upřednostňuje propojení uzlů s vysokým stupněm • vede ke vzniku smyček a multihran 4 of 16 Randomizace zachovávající stupeň Postup: • na vstupu je již existující síť • iterativně vybíráme náhodnou dvojici hran, které prohodíme • {(iJl(k,l)}^{(iJl(kj)} Vlastnosti: • zachovává velikost a hustotu sítě, • vlastnosti závislé na jiných parametrech se ztratí 5 of 16 Model se skrytým parametrem Postup: • začneme s izolovanými uzly • každému uzlu přiřadíme hodnotu parametru r\\ z distribuce p{r\) • hranu (/,_/') přidáme s pravděpodobností • např. pro bezškálovou síť: r\\ = c/ia, i = 1,..., N o výsledkem síť s « k~(1+ä> Vlastnosti: • nevytváří multihrany a smyčky • flexibilní vůči požadavku na výsledné Růstové modely Motivace • zajímají nás principy stojící za bezškálovým charakterem sítí sdíleným napříč velmi rozdílnými systémy Pozorování: • reálné sítě často vznikají postupným vývojem (připojováním uzlů) • citačnísíť, WWW, ... 7 of 16 Upřednostněné připojení Intuice: • nově příchozí jsou s větší pravděpodobností představeni „populárním" uzlům s vysokým k\ • „rich get richer" Obecný postup • iterativně přidáváme uzel s daným počtem hran • pravděpodobnost navázání na existující uzel j závisí na k; 8 of 16 Model Barabási-Albert Postup • každý nový uzel přichází s m hranami • pravděpodobnost připojení k uzlu / je dána n(/í;) = Ä Výsledná distribuce: p(k) « 2m2k~3 9 of 16 Netlogo demo 10 of 16 Nelineární upřednostněné připojení Obecně U(k) ~ k a sublineární (a < 1) • nestačí na vznik hubů: náhodná síť lineární (a ~ 1) • bezškálová síť superlineární (a > 1) • tendence „bohatnutí bohatých" dominuje • vítěz bere vše: topologie hvězda 11 of 16 Sublinear Linear Superlinear \ 1 Y \ a = 1 3 a=2 k k 0.5 1.5 a . , Stretched Hub-and-spoke Vk Exponential _ . Power law . exponential topology Int (Int)1/(1 "Q) -t1^"1' ~t Network Ran dorn No preferential Random Scale-free nl) _ ^Barabasi: Network Science Book 12 of 16 _ Model Bianconi-Barabási Motivace: • BA model zvýhodňuje dříve příchozí • v reálných sítích tomu tak není: Friendster -Myspace - Facebook - ? • „schopné" uzly mohou předběhnout stávající dominující huby - do modelu přidáme parameter zdatnost (fitness) 13 of 16 Model Bianconi-Barabási Postup • v každém kroku přidáme uzel s m hranami, a zdatností tj z dané distribuce p(rf) • pravděpodobnost připojení nově příchozího k uzlu / je dána jako: nf= Viki 14 of 16 Model Bianconi-Barabási Vlastnosti: • i malý rozdíl ve zdatnosti uzlu vede k velkým rozdílům ve stupni (limitně) • pokud je zdatnost tj identická pro všechny uzly, model se redukuje na BA • pro uniformní p{rf) dostaneme bezškálovou sít • čas příchodu uzlu není hlavním určujícím prvkem pro výsledný stupeň 15 of 16 NetworkX demo 16 of 16