Sieci o Skalowaniu: Jak 'Bogaci Zyskują Bogactwo' Buduje Centra Internetu

Bogaci stają się jeszcze bogatsi: zasada działania centrów

Większość sztucznych i naturalnych sieci nie jest budowana poprzez losowe łączenie węzłów. Internetowa infrastruktura, sieci cytowań, map interakcji białkowych oraz grafy obserwatorów w mediach społecznościowych wszystkie charakteryzują się skośnym ułożeniem: niewielka liczba potężnie połączonych centrów i długi ogon węzłów z prawie zerowymi połączeniami. Albert-Laszlo Barabasi i Reka Albert modelowali to w 1999 roku dzięki jednej, pozornie prostej zasadzie wzrostu: preferencyjne przyłączenie — każdy nowy węzeł przybywający do sieci jest bardziej prawdopodobne, że połączy się z węzłem, który już ma wiele połączeń.

P(połączyć się z węzłem i) = k_i / ∑_{j} k_j gdzie: k_i = bieżący stopień (liczba połączeń) węzła i ∑_{j} k_j = suma stopni wszystkich istniejących węzłów. Zacznij od małej sieci ziarna. Dodawaj jeden węzeł na raz, każdy przynoszący m nowych krawędzi i podłączając te krawędzie do istniejącego węzła z prawdopodobieństwem proporcjonalnym do jego bieżącego stopnia. Węzeł, który przypadkowo zdobędzie kilka dodatkowych połączeń wcześnie — czysty przypadek lub bycie pierwszym, który istnieje — staje się nieco bardziej atrakcyjny dla następnego przybyłego, co sprawia, że jest jeszcze bardziej atrakcyjny dla kolejnego po nim. Małe wczesne przewagi kumulują się i tworzą ogromne, wzmacniające się centra.

P(connect to node i)  =  k_i / Σ_j k_j

k_i    = current degree (number of connections) of node i
Σ_j k_j = sum of degrees over all existing nodes

Władza praw potęg

Uruchom ten proces przez długi czas i ułamek węzłów o stopniu k zbiega się do prawa mocy: P(k) ≈ k⁻^γ, gdzie model Barabási-Alberego generuje wykładnik dokładnie γ = 3 niezależnie od m. Rozkład stopni o prawie mocy nie ma charakterystycznej skali – nie ma typowego rozmiaru węzła tak jak krzywa Gaussa ma typową wartość – co właśnie powoduje, że te sieci nazywane są wolne od skali. Wykres log-log P(k) w stosunku do k jest diagnostyczny: graf Erdos-Renyi o podwójnym wzorcu pokazuje zakrzywioną, kształt dzwonu linię na tych osiach, podczas gdy sieć wolna od skali wykazuje prostą linię.

P(k)  ∝  k^(-3)      ← Barabasi-Albert degree distribution

random graph:    most nodes near the average degree, exponential tail
scale-free graph: most nodes have few links, a few hubs have enormous ones

Dlaczego węzły centralne czynią sieci zarówno wydajnymi, jak i kruchymi

Struktura skali-wolna charakteryzuje się ostrym podwójnym brzegi. Ponieważ niewielu węzłów centralnych łączy ogromne obszary sieci, średnia odległość między dowolnymi dwoma węzłami pozostaje zaskakująco krótka, nawet gdy sieć rośnie – właściwość małego świata, która sprawia, że ​​hipoteza sześciu stopni oddalenia jest możliwa w sieciach miliardów węzłów. Losowe usuwanie węzłów prawie nie wpływa na to: prawie każdy węzeł ma niską stopień, więc losowy awaria jest bardzo mało prawdopodobny, aby uderzyć w węzeł centralny i sieć pozostaje połączona. Jednak celowa atakująca węzły o najwyższym stopniu jest katastrofalna – wyeliminowanie kilku największych węzłów może podzielić całą sieć na odizolowane wyspy. Ten wzorzec odporności na uszkodzenia, ale kruchości pojawia się w infrastrukturze rzeczywistej: Internet toleruje ogromną liczbę losowych awarii routerów, ale jest podatny na ataki na swoje główne punkty wymiany.

Nie każdy sieć jest skalejny

Preferencyjne przyłączenie to mechanizm, a nie uniwersalna zasada – wiele rzeczywistych sieci (sieci drogowe, sieci energetyczne, niektóre sieci społeczne mierzone ostrożnie) wykazuje rozkłady stopni o charakterze wykładniczym lub innym, a twierdzenie o wszechobecności struktury skalejnej jest od 2018 roku aktywnie dyskutowane w wyniku wpływowej analizy statystycznej przez Broido i Clauset, która wykazała, że mocne prawa występują znacznie rzadziej w rzeczywistych sieciach niż wcześniejsze, mniej precyzyjne analizy. Preferencyjne przyłączenie jednak niezawodnie wyjaśnia, dlaczego tworzą się węzły centralne tam, gdzie działają wzrost i kumulatywna przewaga – nowe strony internetowe linkujące do już popularnych, nowe cytowania faworyzujące już cytowane artykuły, nowe konta obserwatorów przyciągające się do już popularnych kont.

Frequently asked questions

Wypróbuj na żywo

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