IV124 Komplexní sítě
Jan Fousek, Eva Hladká
Fakulta informatiky, Masarykova univerzita
28. dubna 2015
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í
Milgram, 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.
3 Jgool & Kochen (1978)
Klastry a délka cesty: modely
Zadané vlastnosti:
• malý diametr (průměrná délka cesty): / ~ ln(A/)
• vysoký klastrovací koeficient: C ^> Crancj
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 model
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. 1, & Strogatz, S. H. (1998). Collective dynamics of 'sm^ll-worlďnetworks. Nature, 393(6684), 440-442.
Watts-Strogatz model
Watts-Strogatz model
10
10 10 10
Rewiring Probability (p)
10
0
http://bit.Iy/1D2WBIL
7 Jgporns 0. (2011)_
Watts-Strogatz: ukázka
8 of 17
Model lesních požárů
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 Forward buring probability
Densification exponent
■i 0.8 co
0.2 0.4 0.6 0.8 Forward buring probability
Diameter
7
^skovec et. al (2005)
10 of
Malé světy vs. efektivita
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) W
• 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
Mathias & Gopal (2000)
Malé světy vs. efektivita
Výsledek:
• pro extrémní hodnoty A dostaneme náhodnou síť a
v'v I
mrizku
• pro střední hodnoty malé světy s huby
12 of 17
Milgramův experiment - navigace
"The chain* pi-ogreee trom the alerting P«wltlon (Omaha) to the target area (Bwton) with each remove. Diagram *hov»i ihe number of mllee from the taroet area, with the dlalanee of each remove avaraead over completed and 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), elll973.
15 of 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(u, v) = d(u, v)~r
"Kleinberg, J. (2000)
Kleinbergův model: ukázka
17 of 17