IV124 Komplexní sítě
Jan Fousek, Eva Hladká
Fakulta informatiky, Masarykova univerzita
19. dubna 2018
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ý"
2 of 18
Huby a distribuce stupně uzlů
náhodná síť vs. síť s huby
			■		uooo
			L		s;
			É		
					
		■	1		4O0
					
		m i.........	llll ľ,,.		
-5-4-3-2-10123^ 0 300 x.-Z ĚO0        800        UOOO       120O 1400
3 of 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
13 10] 13 103
4 of 18
Povědomá distribuce
10
10
r i —p i i iiiii|—i ■ i li i ■ i p—i i i iiiii^ * i
0 1 4
10 10" 10
word frequency
10
10
10"
10
10"
■   ■ i i Ml I-1   ■ i   ii 'i-1   ■■ iii
—i i i piip^
citations
10" 1
10"
I ......1 10
10"
(c)
10
i i iiiiij—i i ipiiij—p-rnrp^—i i iniij—i i ipiiij"
10" I"
web hits
100-
(e)
books sold
10       10"      10 10 telephone calls received
1041
ioN
10"
(0
T
1
2    3    4    5    6 7 earthquake magnitude
5 JMewman. M. E. (2005) DOI:10.1080/00107510500052444
Povědomá distribuce
6 of 18
Povědomá distribuce
10'
10°
103
1,0*
CD
|io3 >
i—
CD CS
Q)
5
10'
10'
10u
10
-1
-1—1—I I I I 11
Pygmy shrew ,
West European hedgehog Algerian hedgehog
Rat % Fisherman bat Tenrec
Risso's dolphin Human Bottlenose dolphin -
Horse Harbor porpoise Chimpanzee -' Sea lion
Olive baboon w / Cow Capuchin monkey       .     ... * Vervet monkey Lar gibbon
Redcolobus     \ Pig Redtail monkey^Macaque monkey Howler monkey v. ^ S/j«?/>
Squirrel monkey Cat      /. WooWy morcfcey
White sifaka   ^9*     ^ fox White-fronted lemur^m/*^ Aye-aye Owl monkey -    - •
Tufted-ear marmoset, Rabbit^
Woolly lemur Red-tailed sportive lemur Pygmy marmoset Flyingfox
Indri Mara Marmoset
Everett's tupaia
Large Madagascar hedgehog.
Mouse -Water shrew South African giant shrew ^ '■ Small Madagascar hedgehog
Dwarfbushbaby Tarsier Tree shrew Lesser mouse lemur
Long—eared desert hedgehog
Streaked tenrec Asian house shrew
Common shrew
European white-toothed shrew
Elephant Pilot whale
log10 W= (1.23 + 0.01) logi0 G - (1.47 ± 0.04)
r= 0.998
i. i.j.i i
10u
10'
10
10J
10*
10=
10°
10'
7 of 18
Gray Matter Volume G ( mm )
Od zobrazení ke vzorci
Na log-log osách máme přímku:
log(p(x)) = c-7log(x)
Po umocnění:
p(x) = cx~7
Tzv. mocninný zákon (mocninné pravidlo, power-law)
8 of 18
Mocninné pravidlo: variance
Druhý moment (variance) obecně není omezený
čím větší máme vzorek (síť), tím větší bude maximální
hodnota.
	~k	o
E. Coli metab.	5.58	20.79
WWW	4.60	30.27
kvasinky prot.	2.9	4.88
9 of 18
Log-log zobrazení
Problém:
• s rostoucím stupněm klesá počet vzorků, roste šum
10L
irr-
10 ■
10l
10'
10:
o^ poznámka: vždy používat logaritmus o základu 10.
Log-log zobrazení
Řešení:
• logaritmické třídy
10° -==
10 J L0J
io-!
L0J 10 a
13 10] 13 103
11 of 18
Log-log zobrazení
Rešen ŕ
• komplementární kumulativní distribuce
• p>(x) = x1-^
io° 10] lír 103
12 of 18
Vlastnosti bezškálových sítí
Velikost sítě vs velikost hubů
o 1
• lze odvodit , ze km3x ~ kmmN^ 1
• tedy km3x 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?
arabasi: Network Science, chapter 4
13 of T8
Třídy bezškálových sítí
Anomální režim 7 < 2
• stupeň nej většího hubu roste rychleji než velikost sítě
-1
• 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 hubu klesá příliš rychle
• těžce rozeznatelná od náhodné sítě
konkrétně z předchozí rovnice: N ^>
'mm
Tedy pokud požadujeme rozpětí alespoň 3 řádů, tak pro 7 = 5, kmjn = 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 a pod. v oblíbeném statistickém softwa re
17 of 18
Praktická ukázka
18 of 18