Sześć stopni oddzielenia: Sieć świata małych światów…

Q: Stanley Milgram na prawdę udowodnił sześć stopni oddzielenia?

Nieco mniej. Swoje badanie z 1967 roku, w którym śledzono łańcuchy listów przekazywanych przez osobiste znajome do osoby docelowej, pokazało, że ukończone łańcuchy średnio liczyły około pięć do sześciu pośrednich osób — ale większość łańcuchów nigdy nie dotarła do celu, więc słynny liczba opisuje powodujące sukces łańcuchy, a nie udowodnione właściwości całego grafu społecznego. Później, wiele większych badań, w tym analiza z 2011 roku grafu przyjaźni na Facebooku, wykazały podobnie krótkie średnie odległości, co daje rzeczywistą wsparcie dla idei.

Q: Jak sieć może mieć zarówno krótkie ścieżki, jak i tight-knit cluster'y?

Ta kombinacja jest dokładnie tym, co sprawia, że sieć jest małym światem, a nie tylko losową. W większości sieci pozostaje lokalna grupa — twoi znajomi tendencjami znają się nawzajem — podczas gdy niewielka liczba długich łańcuchów przekierowanych działa jako skróty między inaczej odległymi grupami, zrównywając średnią długość ścieżki znacznie bardziej niż spadają współczynnik lokalnej grupy.

Q: Dlaczego średnia długość ścieżki spada tak szybko nawet przy niskiej prawdopodobieństwie przekierowania?

Bo pojedynczy długi skrót może zmniejszyć odległość między dwiema odległymi grupami z dziesiątek hopów do tylko dwóch lub trzech, a ten efekt kompensuje się — kilka losowych długich krawędzi tworzy sieć skrótów między skrotami. Watts i Strogatz pokazali, że średnia długość ścieżki prawie zanika już po wprowadzeniu jakiegokolwiek przekierowania, podczas gdy współczynnik lokalnej grupy niemal się nie zmienia, dopóki prawdopodobieństwo przekierowania nie stanie się znacznie wyższe.

Pismo, nieznajomy i sześć kroków

W 1967 roku psycholog Stanley Milgram przeprowadził eksperyment legendarny w dziedzinie nauki o sieciach: podał grupom wolontariuszy z Nowego Jorku i Kansasu listy adresowane do brokera akcji w Bostonie, z instrukcjami, aby je przekazać tylko osobom, które znają się osobiście i które mogą być bliższe socjologicznie do docelowej osoby. Nici łączące się w skończonego punktu średnio liczyły około pięciu do sześciu pośredników — źródło frazy „sześć stopni oddzielenia”. Najczęściej nici nigdy nie docierały do docelowej osoby, więc ta liczba jest właściwie cechą pomyślanych ścieżek, a nie objętą doraźnym dowodem faktem o całym grafie społecznym, ale intuicja, którą zaszyła — że nasze osobiste sieci, choć lokalnie skupione, są wypełnione wystarczającą liczbą łączy dalekostronnej, aby uczynić cały świat nieoczekiwanie bliskim — okazała się prawdziwa. Trzy dekady minęły przed tym, zanim ktoś stworzył model wyjaśniający dlaczego.

Konstrukcja Watts-Strogatz

Duncan Watts i Steven Strogatz zaproponowali ten model w 1998 roku. Zaczynając od siatki torusa: n węzłów ułożonych w okręgu, każdy połączony z swoimi k najbliższymi sąsiadami na obu stronach. Ta regularna struktura ma dokładnie takie same właściwości lokalne jak sieci prawdziwych znajomości — sąsiedzi twoich sąsiadów często są również twoimi sąsiadami, co daje wysoki współczynnik skupienia (C). Jednak jest to bardzo słabe podejście do całościowej struktury sieci, ponieważ przebycie od jednego końca torusa do drugiego wymaga liczby skoków proporcjonalnej do n, co rośnie liniowo z rozmiarem sieci.

start: siatka torusa, n węzłów, każdy łączący się ze swoimi k najbliższymi sąsiadami → wysoki współczynnik skupienia C(0), długie średnie długości ścieżek L(0) ~ n dla każdego krawędzi z prawdopodobieństwem p: przeprowadź nową krawędź do losowo wybranego węzła p = 0 → regularna siatka (wysoki C, długie L) p = 1 → graf losowy (niski C, krótkie L) 0 < p < 1 (małe) → ŚMIECIOWY ŚWIAŁD: C pozostaje wysoki, L szybko krycia Konstrukcja przeprowadza niezależne przepinanie każdej krawędzi do losowo wybranego węzła z pewnym małym prawdopodobieństwem p. Dla p = 0 otrzymujemy pierwotną, wolną i skupioną siatkę; dla p = 1 otrzymujemy graf losowy Erdős-Rényiego typu, z krótkimi ścieżkami ale prawie bez skupienia. Zaskakujące jest to, co pokazały Watts i Strogatz: nawet bardzo małe p — przepinanie tylko kilku procent krawędzi — jest wystarczające do szybkiego spadku średniej długości ścieżki niemal do wartości grafu losowego, podczas gdy współczynnik skupienia barely spada od wartości siatki. Istnieje szeroki zakres p, w którym sieć ma jednocześnie obie właściwości: lokalnie skupiona jak siatkę, globalnie tak samo dostępna jak graf losowy.

start:  ring lattice, n nodes, each linked to its k nearest neighbours
        → high clustering C(0), long average path length L(0) ~ n

for each edge, with probability p:
  rewire one endpoint to a uniformly random node

p = 0    → regular lattice   (high C, long L)
p = 1    → random graph      (low C,  short L)
0 < p < 1 (small)  → SMALL WORLD: C stays high, L collapses fast

demo na żywo · powiązana symulacja● LIVE

Dlaczego kilka skrótu wykonuje tyle pracy

Intuicja zaasymetrycznego upadku polega na tym, że grupowanie jest właściwością lokalną — zależy tylko od tego, czy Twoi bezpośrednie sąsiadzi znają się nawzajem — więc kilka losowo przewiązanych krawędzi rozłożonych po całym sieciu wpływa tylko na niewielką część lokalnych sąsiedztw i prawie nie zmniejsza średniej wartości. W przeciwieństwie do tego, długość ścieżki jest właściwością globalną, a pojedyncza długorzyska krawędź może skrócić dystans między dwiema inaczej odległymi regionami sieci z dziesiątek hopów do dwóch lub trzech. Ponieważ te długorzyskie skróty są również ze sobą połączone, ich efekt kompensuje się szybko: mała liczba losowych długich krawędzi szybko tworzy siatkę skrótów między skrótami, a średnia długość ścieżki w całym sieciu nie zależy od n, ale od log n.

Gdzie pokazuje się właściwość małego świata

W pracy Wattsa i Strogatza model testowano na sieci neuronowej nici C. elegans, siatkach energetycznym Stanów Zjednoczonych oraz sieci współpracy aktorów filmowych — wszystkie trzy pokazały charakterystyczne dla małego świata połączenie krótkich ścieżek z wysokim stopniem skupienia. Ten sam strukturalny wzór można znaleźć w grafach społecznościowych mediów społecznych (globalna sieć Facebooka okazała się w 2011 roku mieć średni stopień separacji około 3,5), a jego konsekwencje praktyczne są bezpośrednie dla epidemiologii: ponieważ choroba może podróżować po sieci tak szybko, jak to umożliwia najkrótsze ścieżki, nawet mała liczba długodystansowych połączeń społecznych lub podróży może przekształcić wybuch lokalny i geograficznie ograniczony w globalny, który dotrze do całej populacji szybko.

Często zadawane pytania

Stanley Milgram na prawdę udowodnił sześć stopni oddzielenia?

Nieco mniej. Swoje badanie z 1967 roku, w którym śledzono łańcuchy listów przekazywanych przez osobiste znajome do osoby docelowej, pokazało, że ukończone łańcuchy średnio liczyły około pięć do sześciu pośrednich osób — ale większość łańcuchów nigdy nie dotarła do celu, więc słynny liczba opisuje powodujące sukces łańcuchy, a nie udowodnione właściwości całego grafu społecznego. Później, wiele większych badań, w tym analiza z 2011 roku grafu przyjaźni na Facebooku, wykazały podobnie krótkie średnie odległości, co daje rzeczywistą wsparcie dla idei.

Jak sieć może mieć zarówno krótkie ścieżki, jak i tight-knit cluster'y?

Ta kombinacja jest dokładnie tym, co sprawia, że sieć jest małym światem, a nie tylko losową. W większości sieci pozostaje lokalna grupa — twoi znajomi tendencjami znają się nawzajem — podczas gdy niewielka liczba długich łańcuchów przekierowanych działa jako skróty między inaczej odległymi grupami, zrównywając średnią długość ścieżki znacznie bardziej niż spadają współczynnik lokalnej grupy.

Dlaczego średnia długość ścieżki spada tak szybko nawet przy niskiej prawdopodobieństwie przekierowania?

Bo pojedynczy długi skrót może zmniejszyć odległość między dwiema odległymi grupami z dziesiątek hopów do tylko dwóch lub trzech, a ten efekt kompensuje się — kilka losowych długich krawędzi tworzy sieć skrótów między skrotami. Watts i Strogatz pokazali, że średnia długość ścieżki prawie zanika już po wprowadzeniu jakiegokolwiek przekierowania, podczas gdy współczynnik lokalnej grupy niemal się nie zmienia, dopóki prawdopodobieństwo przekierowania nie stanie się znacznie wyższe.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Six Degrees of Separation — Small-World Networks i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Six Degrees of Separation — Small-World Networks

Sześć stopni oddzielenia: Sieć świata małych światów Watts-Strogatz