Simulating Molecular Motion

Trzy modele generatywne, trzy różne światy

Nie wszystkie grafy wyglądające na splątane są takie same. Generator losowych grafów to przepis: mały zestaw zasad, który, zastosowany do n węzłów, produkuje sieć o statystycznie przewidywalnej strukturze. Trzy klasyczne modele – Erdős-Rényi, Wattsa-Strogatza i Barabási-Alberta – każdy został zbudowany w celu wyjaśnienia różnych obserwacji dotyczących rzeczywistych sieci, a porównywanie ich obok siebie przy tej samej liczbie węzłów to najszybszy sposób na zrozumienie, dlaczego topologia sieci nie jest jedną rzeczą.

Erdős-Rényi: czysty przypadek i największy składnik

Model G(n, p), wprowadzony przez Erdősa i Rényi w 1959 roku, jest najprostszym możliwym grafem losowym: wybierz n węzłów i dla każdego z n(n-1)/2 możliwych krawędzi, rzuć niezależną monetę z prawdopodobieństwem p i dodaj ją, jeśli wypadnie orzeł. Nic w nim nie jest zaprojektowane – żaden węzeł nie jest specjalny, żadna krawędź nie jest bardziej lub mniej prawdopodobna niż inna.

Dla każdej pary (i, j) z i != j: jeśli random() Jego najbardziej znaną właściwością jest przejście fazowe: gdy p przekracza próg krytyczny 1/n, graf nagle przechodzi z morza małych, odizolowanych fragmentów na jeden duży składnik, który zawiera dodatni ułamek wszystkich węzłów, a wielkość tego dużego komponentu skacze dyskontynuistycznie – nie stopniowo – dokładnie w tym progu. Poniżej progu największy złączony kawałek ma tylko O(log n) węzłów; powyżej jeden komponent pochłania prawie wszystko. Ten pojedynczy wynik, pochodzący z czysto kombinatorycznego modelu zabawkowego, jest powodem, dla którego teoria perkolacji i argumenty dotyczące progów epidemii tak często redukują się do tego samego obliczenia p ~ 1/n. Kompromis polega na tym, że G(n,p) to słaby model rzeczywistych sieci społecznych lub technologicznych: jego rozkład stopniowy jest bardzo ciasny binominalny (każdy ma w przybliżeniu tyle samo połączeń) i jego współczynnik gęstości krawędzi wynosi dokładnie p, oba znacznie niższe niż to, co pokazują rzeczywiste sieci.

for each pair (i, j) with i != j:
  if random() < p:  add edge(i, j)

expected degree of each node  ≈  p * (n - 1)
expected total edges          ≈  p * n(n-1) / 2

Watts-Strogatz: jak pierścień staje się małym światem

Model Wattsa i Strogatza z 1998 roku zaczyna się od skrajnego przypadku – regularny pierścień, w którym każdy węzeł jest połączony z k najbliższymi sąsiadami po obu stronach, co charakteryzuje się wysoką gęstością połączeń (sąsiedzi sąsiedzi również bywają sąsiadem) oraz dużym średnim promieniem. Następnie każda krawędź jest losowo przekierowywana na cel o równomiernym rozkładzie z małą prawdopodobieństwem β:

początkowo: pierścień, każdy węzeł połączony z k najbliższymi sąsiadami (wysoka gęstość połączeń, długie ścieżki) dla każdej krawędzi: z prawdopodobieństwem beta: przekieruj ją do losowego celu o równomiernym rozkładzie beta = 0 → oryginalny regularny pierścień (wysoka gęstość połączeń, długie ścieżki) beta = 1 → zasadniczo graf Erdos-Reniego o randomowym rozkładzie (niska gęstość połączeń, krótkie ścieżki) beta ≈ 0.01 – 0.1 → „sweet spot” małego świata Zauważalny wynik empiryczny to jak wąska jest ta przejście: nawet niewielki procent przekierowanych krawędzi – kilka procent – wystarczy, aby skrócić średnią długość ścieżki z O(n) do O(log n), a współczynnik gęstości połączeń ledwo spada z wysokiej wartości początkowej. Kilka losowych, długodystansowych połączeń działa jako mosty przez cały sieć, to intuicyjny mechanizm stojący za znanym odkryciem „sześć stopnie oddalenia” – większość znajomych się ze sobą zna (wysoka lokalna gęstość połączeń), ale kilka osób z różnych kręgów społecznych ma połączenia i te rzadkie, długie skoki sprawiają, że cały świat jest dostępny w kilku krokach.

start:  ring lattice, each node connected to k nearest neighbours (high clustering, long paths)
for each edge:
  with probability beta:  rewire it to a uniformly random new endpoint

beta = 0     → the original regular ring (high clustering, long paths)
beta = 1     → essentially an Erdos-Renyi random graph (low clustering, short paths)
beta ~ 0.01-0.1 → the "small-world" sweet spot

Barabási-Albert: wzrost plus preferencyjne przyłączenie daje nam węzły centralne

Żaden z poprzednich dwóch modeli nie generuje węzłów centralnych, takich jak występują w rzeczywistych sieciach, takich jak sieć WWW, grafy cytowań lub trasy lotnicze – niewielu węzłów z ogromną liczbą połączeń w porównaniu z resztą. Model Barabási-Albert (1999) generuje je z dwóch prostych mechanizmów połączonych: sieć rośnie krok po kroku, dodając nowy węzeł (nie zaczyna się od ustalonej liczby n i nie podłącza go ponownie), a każdy nowy węzeł preferencyjnie przyłącza się do istniejących węzłów w proporcji do ich aktualnej liczby połączeń – „bogaci stają się bogatsi”, formalnie nazywane preferencyjne przyłączenie:

zacznij od małej grafu ziarna o m0 węzłach dla każdego nowego węzła (n - m0 razy): dodaj m nowych krawędzi z tego nowego węzła do m ISTNIEJĄCYCH węzłów, wybierając każdy istniejący cel z prawdopodobieństwem proporcjonalnym do jego aktualnego stopnia: P(połączyć się z węzłem i) = stopień(i) / suma wszystkich stopni // węzeł, który już ma wiele krawędzi, jest proporcjonalnie bardziej prawdopodobny // aby zostać wybranym jako cel kolejnej nowej krawędzi Rozkład stopni otrzymany w ten sposób ma prawo potęgowe, P(stopień = k) ∝ k^(-γ) z γ zwykle około 3 dla podstawowego modelu – co oznacza, że nie ma charakterystycznego „średniego” stopnia węzła, jak to jest przypadku grafu Erdős-Rényi; zamiast tego kilka węzłów centralnych ma ogromny stopień, a większość zdecydowanie ma bardzo mało połączeń, struktura w skali wolnej, ponieważ ten sam kształt występuje niezależnie od zakresu stopni, do którego zoomujesz. To zaskakująco dobrze pasuje do rzeczywistego rozkładu stopnia wejścia sieci WWW, sieci interakcji białkowych i map tras lotniczych, a to wiąże się z dobrze znanym praktycznym konsekwencją: sieci w skali wolnej są niezwykle odporne na losowe awarie węzłów (usuń losowy węzeł, prawie na pewno jest to węzeł o niskim stopniu i sieć prawie go nie zauważa) ale niezwykle kruche wobec ukierunkowanego ataku na węzły centralne (usun kilka najwyżej stopnia węzłów i duży komponent może szybko ulec fragmentacji).

start with a small seed graph of m0 nodes
for each new node (n - m0 times):
  add m new edges from the new node to m EXISTING nodes,
  choosing each existing target with probability proportional to its current degree:

  P(connect to node i)  =  degree(i) / sum of all degrees

  // a node that already has many edges is proportionally more likely
  // to be picked as the target of yet another new edge

Pomiar tego, co wygenerowałeś

Trzy statystyki podsumowań pozwalają na ilościowe odróżnienie tych struktur od siebie po wygenerowaniu wykresu i są dokładnie tym, co symulacja na tej stronie oblicza na bieżąco po ustabilizowaniu się układu.

clustering coefficient  = fraction of a node's neighbour-pairs that are
                          themselves connected, averaged over all nodes
                          (ER: low & uniform  |  WS: high  |  BA: moderate)

average path length     = mean shortest-path distance between all node pairs
                          (ER: short, ~log n  |  WS: short after rewiring
                           |  BA: very short, hubs act as universal shortcuts)

degree distribution     = histogram of how many nodes have each degree
                          (ER: binomial/Poisson, tight bell curve
                           |  WS: still fairly tight
                           |  BA: power law, heavy-tailed with hubs)

Układ: symulacja fizyczna własnego układu

Tworzenie jakichkolwiek z tych wykresów w sposób czytelny dla człowieka stanowi problem oddzielny od ich generowania, rozwiązany poprzez traktowanie samego układu jako systemu fizycznego opartego na sile – każda para węzłów odpycha się jak identyczne ładunki (co powoduje rozdzielenie niezwiązanych węzłów), każdy element graficzny ciągnie swoje dwa końce razem jak sprężyna (co utrzymuje połączone węzły blisko siebie), a cały system jest integrowany w czasie do przodu – z tłumionym ruchem – aż ustabilizuje się w lokalnym minimum energii. Ten proces stabilizacji to właśnie powód, dla którego wykres oparte na sile wizualnie „relaksuje” się w klastry i węzły oddzielające się od obszarów rzadkich: fizyka wykonuje tę samą pracę, jaką robi ludzkie oko podczas rozplatania diagramu, tylko automatycznie.

Często zadawane pytania

Wypróbuj na żywo

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