IV124 Komplexní sítě Eva Výtvarová, Jan Fousek, Eva Hladká Fakulta informatiky, Masarykova univerzita 27. března 2019 Huby a bezškálové sítě Minule jsme se věnovali hubům: • huby: uzly s překvapivě velkým stupněm • dnes se systematicky podíváme na to, co to znamená „překvapivý" 2of 18 Huby a distribuce stupně uzlů náhodná síť vs. síť s huby 7'j 50 uo ■| L uooo BOO 400 300 -5-4-3-2-10 2 3 300 4JC ĚOO BQO UOOO 120O L400 3of 18 Log-log zobrazení distribuce Na běžném histogramu toho moc nevidíme, log-log zobrazení je mnohem zajímavější 10° 10 J L0J 10 J 13 10L 13 103 4 Of 18 Povědomá distribuce1 word frequency citations web hits Newman, M. E. (2005) DOM 0.1080/00107510500052444 Povědomá distribuce 6of 18 Povědomá distribuce 7 of 18 10' 10° 10J 03 |io3 > i— O) co 10' 10' 10° 10" -i—i—i—i 11111 -i—i i i i 111-1-1—i—i i i i 11-1-1—i—i i i 111 Risso's dolphin Human Bottlenose dolphin, Horse Harbor porpoise Chimpanzee - ' Sea lion Olive baboon ^ s. / Cow Pig ;J> Macaque monkey ' Sheep Woolly monkey Pygmy shrew - West European hedgehog Algerian hedgehog Rat Fisherman bat Tenrec Capuchin monkey . ... Vervet monkey Lar gibbon Red colobus Redtail monkey^^ Howler monkey Squirrel monkey Cat White sifaka ^9* " pox White-fronted lemur Aye-aye Owl monkey \ ^ • y indri Slowloris^j' Mara Tufted-ear marmoset-v f ^ Marmoset Rabbit — . Woolly lemur Red-tailed sportive lemur Everett stupaia^ / \ Pygmy marmoset Large Madagascar hedgehog „ Mouse -Water shrew South African giant shrew ^ '- Small Madagascar hedgehog » Ftyingfox Dwarf bushbaby Tarsier Tree shrew Lesser mouse lemur Long-eared desert hedgehog Streaked tenrec Asian house shrew Common shrew European white—toothed shrew Elephant Pilot whale log W= (1.23 ± 0.01) logi0 G - (1.47 ± 0.04) r= 0.998 10u 10' 10' 10° 1 čím větší máme vzorek (síť), tím větší bude maximální hodnota. k E. Coli metab. WWW 5.58 20.79 4.60 30.27 2.9 4.88 kvasinky p rot. 9of 18 Log-log zobrazení2 Problém: • s rostoucím stupněm klesá počet vzorků, roste šum 13 13 13 13 13 10' 13 13' 10 poznámka: vždy používat logaritmus o základu 10. Log-log zobrazení 11 of 18 Log-log zobrazení Řešení • komplementární kumulativní distribuce LO ■ 13 10] 1C: 103 12 of 18 Vlastnosti bezškálových sítí Velikost sítě vs velikost hubů • lze odvodit3, Že Kmax ~ kmjnN > 1 • tedy kmax je polynomiálně závislá na N Velké množství systémů se zdá být v režimu 2 < 7 < 3. Má to nějaký důvod? °jBarabasi: Network Science, chapter 4 Třídy bezškálových sítí Anomální režim 7 < 2 • stupeň největšího hubu roste rychleji než velikost sítě • protože exponent je větší než jedna • jinými slovy, taková síť není bez smyček asymptoticky možná 14 of 18 Třídy bezškálových sítí Bezškálový režim 2 < 7 < 3 • první moment distribuce (průměr) je konečný, ostatní momenty divergují (rozptyl, šikmost, ...) • nejzajímavější vlastnosti: o specifické chování dynamických procesů (difúze) o robustní proti náhodnému výpadku, zranitelná na cílený útok (narozdíl od náhodné sítě) o ■ ■ ■ 15 of 18 Třídy bezškálových sítí Režim náhodné sítě 7 > 3 • pravděpodobnost velkých hubů klesá příliš rychle • těžce rozeznatelná od náhodné sítě 7-1 konkrétně z předchozí rovnice: N > Tedy pokud požadujeme rozpětí alespoň 3 rádu, tak pro 7 = 5, kmin = 1 a kmax = 102 potřebujeme síť o velikosti N > 108. 16 of 18 Empirické hledání exponentu Motivace: • kromě předchozí klasifikace důležité pro nulové modely např. pro studium dynamických procesů Postup: • vycházíme z log-log transformace, fitujeme přímku • použijeme log. intervaly, případně kumulativní distribuci pro odstranění šumu • aplikujeme metodu nejmenších čtverců, max. věrohodnost apod. v oblíbeném statistickém 17 software_ Praktická ukázka 18 of 18