IV124 Komplexní sítě
Eva Výtvarová, Jan Fousek, Eva Hladká
Fakulta informatiky, Masarykova univerzita
10. dubna 2019
Milgramův experiment
Zadání:
• 300 osob z různých míst v USA
• cílem dopravit přes osobní kontakty dopis cílovému člověku v Bostonu
Výsledek:
• 64 úspěšných řetězů
• v průměru 6.2 kroků: 6 stupňů odloučení
1Milgram, S. (1967). The small world problem. Psychology today,
Milgramův experiment: proč 6?
náhodné sociální sítě:
• předpokládá se 500-1500 kontaktů na osobu2
• pro náhodnou síť tedy na tři kroky ~ 5003 = 125-106 osob
přátelé přátel
• tranzitivní povaha sociálních vazeb
• kvantifikujeme pomocí klastrovacího koeficientu.
f£ool & Kochen (1978)
Klastry a délka cesty: modely
Žádané vlastnosti:
• malý diametr (průměrná délka cesty): /« ln(/V)
• vysoký klastrovací koeficient: C > Crand
model	klastry	malý diametr
Erdós Rényi	ne	ano
Barabási-Albert	ne	ano
grid	ano	ne
■	ano	ano
4 of 17
Watts-Strogatz model3
Postup:
• začneme s n uzly spojenými s k nejbližšími sousedy (mesh)
• pro každou hranu, s pravděpodobností p změníme náhodně cílový uzel
Pro určité hodnoty p získáme jak vysoké C, tak nízké /
3Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of 's^ajl-worlďnetworks. Nature, 393(6684), 440-442.
Watts-Strogatz model
o
-* en
"D
O
CO
■
o
O
V
o
NO
t"1
Clustering, Path Length
o     o     o o
O       NJ <J) CO
CD
CD TJ
O O"
o;
O
o t
O
o
O
I
o o o
0°
o
o
o
o
o
o
o
o
#0
en
Watts-Strogatz: ukázka
Model lesních požárů6
Motivace:
• Watts-Strogatz model nevytváří bezškálovou síť
• náhodné přepojování se těžko interpretuje Postup
• v každém kroku přidáme uzel u
• náhodně vybereme a „zapálíme" přípojný bod
• oheň se iterativně šíří s pravděpodobností p, po příchozích hranách r-krát méně
• k u připojíme zhořelé
9 j^eskovec et. al (2005)
Model lesních požárů - vlastnosti
• forma upřednostněného připojení: mocninný zákon
• tzv. komunitou řízené připojení: klastrování
• pouze dva parametry
0.2     0.4     0.6     0.8 0.2     0.4     0.6 0.8
Forward buring probability Forward buring probability
Densification exponent Diameter 7
Malé světy vs. efektivita8
Intuice:
• u fyzických sítí (dopravní, neuronová, ...) proti sobě působí snaha o maximální konektivitu a cena vybudování spojení
• hodnotící funkce E = XL + (1 - A) l/l/
• L je char. délka cesty, W je celková cena spojení (pro jednu hranu závisí na vzdálenosti mezi uzly), A udává preferenci L vs W
l^athias & Gopal (2000)
Malé světy vs. efektivita
Výsledek:
• pro extrémní hodnoty A dostaneme náhodnou síť a mřížku
• pro střední hodnoty malé světy s huby
12 of 17
Milgramův experiment - navigace
1** chains pronreea from the alerting Position (Omaha) to the let0»* «•* (Boston) with each remove. Diagram thovri the number of miles from the tttQet area, with the dlalance of each remove averaged over completed ■M uncompleted chain*.
^-------------
00$ ML
67
Pozorování:
• dopisy se s každým krokem přibližují k cíli
Milgramův experiment dnes
Srovnej:
• Szule, J., Kondor, D., Dobos, L, Csabai, I., & Vattay, G. (2014). Lost in the City: Revisiting Milgram's Experiment in the Age of Social Networks. PloS one, 9(11), e111973.
15of 17
Kleinbergův model
Motivace
• využít znalost geografické polohy cíle a ostatních uzlů
Postup
• uzly rozloženy na mřížce
• přidány náhodné hrany:
p(w, v) = d{u, v)~r
Weinberg, J. (2000)
Kleinbergův model: ukázka