🕸️ Generator topologii sieci — grafy losowe i małe światy

W modelu Erdősa-Rényiego G(n,p), każda z N(N−1)/2 możliwych krawędzi między N węzłami jest włączana niezależnie z prawdopodobieństwem p. Wynikowy rozkład stopni jest dwumianowy, dobrze przybliżany rozkładem Poissona dla dużych N — większość węzłów ma stopień bliski średniej, żaden nie wyróżnia się jako strukturalnie specjalny węzeł centralny. To naturalny matematyczny punkt odniesienia, z którym porównuje się bardziej realistyczne modele sieci.

Watts i Strogatz (1998) zaczynają od sieci pierścieniowej, gdzie każdy węzeł łączy się ze swoimi k najbliższymi sąsiadami — silnie klastrowana, ale wolna w przemierzaniu struktura — a następnie przełączają każdą krawędź na losowy cel z prawdopodobieństwem β. Nawet małe β wprowadza kilka dalekozasięgowych 'skrótów', które zapadają średnią długość najkrótszej ścieżki w kierunku małej wartości typowej dla grafu losowego, podczas gdy współczynnik klastrowania ledwo spada z wysokiej wartości pierścienia. Ta kombinacja — wysokie klastrowanie plus krótkie ścieżki — to prawdziwy, mierzalny efekt małego świata.

Model Barabásiego-Albert (1999) rozrasta graf węzeł po węźle: każdy nowy węzeł tworzy m połączeń, a prawdopodobieństwo połączenia z istniejącym węzłem jest proporcjonalne do bieżącego stopnia tego węzła — 'bogaci się bogacą'. Węzły, które przypadkiem zyskują kilka dodatkowych wczesnych połączeń, stają się nieproporcjonalnie bardziej skłonne do zyskiwania przyszłych, produkując niewielką liczbę węzłów o bardzo wysokim stopniu obok wielu węzłów o niskim stopniu, zamiast wąskiego rozrzutu stopni widocznego w grafach Erdősa-Rényiego.

'Sześć stopni oddalenia' to popularna nazwa empirycznej obserwacji — sięgającej eksperymentów małego świata Stanleya Milgrama z lat 60. i później potwierdzonej w skali internetu — że większość par ludzi w ogromnej sieci społecznej jest połączona zaskakująco krótkim łańcuchem znajomości. To dokładnie to, co model Wattsa-Strogatza odtwarza matematycznie: sieć może być ogromna i wciąż mieć malutką średnią długość najkrótszej ścieżki, gdy istnieje kilka dalekozasięgowych skrótów.

Rozkład potęgowy stopni oznacza, że ułamek węzłów o stopniu k spada mniej więcej jak k⁻ᵞ zamiast klastrować się wokół średniej — więc podczas gdy większość węzłów ma bardzo mało połączeń, niewielka, ale nieznikoma liczba ma ich bardzo dużo, bez naturalnej 'typowej' skali (stąd 'bezskalowy'). Na histogramie tej symulacji objawia się jako długi, cienki ogon rozciągający się ku statystyce maksymalnego stopnia dla grafów Barabásiego-Albert.

Zmierzona topologia AS internetu, graf hiperłączy sieci web i większość sieci społecznych wykazują zarówno wysokie klastrowanie, jak i krótkie średnie długości ścieżek wraz z ciężko-ogoniastymi, często potęgowymi rozkładami stopni — właściwości, których graf Erdősa-Rényiego z tą samą liczbą węzłów i krawędzi zasadniczo nie może wyprodukować, ponieważ niezależność wymywa zarówno klastrowanie, jak i strukturę centralną.

To dobrze udokumentowany, opublikowany wynik nauki o sieciach (Albert, Jeong i Barabási, 2000): ponieważ większość węzłów w sieci bezskalowej ma niski stopień, usuwanie węzłów losowo w przeważającej mierze trafia węzły o niskim stopniu i ledwo nadszarpuje ogólną łączność. Ale usunięcie garstki węzłów centralnych o wysokim stopniu fragmentuje sieć znacznie szybciej niż usuwanie losowych węzłów.

Lokalny współczynnik klastrowania węzła to ułamek par wśród jego sąsiadów, które są same bezpośrednio połączone — dosłownie, w ilu trójkątach uczestniczy w stosunku do tego, ile jest możliwych. Ta symulacja oblicza to dokładnie dla każdego węzła i uśrednia po wszystkich węzłach, by uzyskać współczynnik klastrowania całej sieci pokazany w panelu statystyk.