Quantum Superposition

Model G(n,p)

Graf losowy G(n,p) zgodnie z twierdzeniem Erdős–Rényi przyjmuje n oznaczonych wierzchołków i dla każdego z możliwych C(n,2) = n(n−1)/2 krawędzi niezależnie zawiera go z prawdopodobieństwem p. Edgar Gilbert wprowadził dokładnie tę formułę w 1959 roku, w tym samym roku Paul Erdős i Alfréd Rényi opublikowali pokrewny model G(n,M), który zamiast tego ustalał dokładnie M krawędzi wybranych losowo z uwzględnieniem. Oba modele są asymptotycznie równoważne, gdy M ≈ p·C(n,2), a graf G(n,p) jest tym, co większość ludzi rozumie dzisiaj przez „graf ER” ze względu na niezależność między krawędziami, która znacznie upraszcza matematykę.

Rozkład stopni: Poissona, a nie prawospowodowy

Każe wierzchołek ma n−1 potencjalnych sąsiadów, każdy uwzględniony niezależnie z prawdopodobieństwem p, więc stopień wierzchołka jest Binominalny(n−1, p). Wraz ze wzrostem n przy zachowanym np = λ, to konwerguje do rozkładu Poissona:

E[stopień(v)] = (n-1)·p ≈ np = λ P(stopień(v) = k) → e^(-λ)·λ^k / k! (Poissonski, n → ∞) Ostroga ogona Poissona zanika wykładniczo — wierzchołki znacznie powyżej średniego stopnia są niezwykle rzadkie. Ten jeden fakt jest podstawą najsłynniejszej ograniczenia modelu, omówionej poniżej.

E[deg(v)] = (n-1)·p ≈ np = λ
P(deg(v) = k) → e^(-λ)·λ^k / k!   (Poisson, n → ∞)

Przejście fazowe na dużą komponentę

Wraz ze wzrostem średniej stopnia λ = np powyżej 1, największa połączona komponenta przechodzi przejście fazowe w sposób szczerzny, podobnie jak zamarzanie wody:

λ < 1 (podkrytyczny): największa komponenta O(log n) — rozrzucone fragmenty λ = 1 (krytyczny): największa komponenta Θ(n^(2/3)) λ > 1 (nadkrytyczny): pojawia się duża komponenta o rozmiarze f(λ)·n, gdzie f(λ) = 1 - e^(-λ·f(λ)) Obszar wokół λ = 1 jest niezwykle wąski — minimalna zmiana w p powoduje zmianę grafu z "bez dużej komponenty" na "jedną komponentę pochłaniającą dodatkową część wszystkich wierzchołków". Oddzielny, jeszcze bardziej wyraźny próg reguluje pełne połączenie: przy p = ln(n)/n odizolowane wierzchołki zanikają i cały graf staje się połączony z wysokim prawdopodobieństwem.

λ < 1 (subcritical): largest component O(log n) — scattered fragments
λ = 1 (critical):     largest component Θ(n^(2/3))
λ > 1 (supercritical): a giant component of size f(λ)·n emerges,
                       where f(λ) = 1 - e^(-λ·f(λ))

Dlaczego model sam w sobie jest niewystarczający

Grafy ER rzeczywiście odtwarzają właściwość "małego świata" – długości ścieżek rosnące jedynie jako ln(n)/ln(np), odpowiadające zasadzie "sześć stopnie separacji". Jednakże, prawdziwe sieci społeczne i biologiczne wykazują znacznie więcej klastrów niż graf ER o tej samej gęstości, a konsekwentnie wykazują rozkłady stopni mocy z niewielką liczbą ekstremalnie wysokodegradowych węzłów – wzorzec, który model o ogonie Poissona z ER po prostu nie potrafi wygenerować. Obserwacja ta, podkreślona przez Barabási i Alberta w 1999 roku, skłoniła do tworzenia modeli preferencyjnego przyłączenia, gdzie nowe węzły preferencyjnie łączą się z już popularnymi. Grafy ER pozostają podstawowym punktem odniesienia, ponieważ pokazują, jak wygląda struktura w całkowskim braku takich mechanizmów – standardowy model zerowy, na którym porównywane są klastry i rozkład stopni każdej rzeczywistej sieci.

Często zadawane pytania

Wypróbuj na żywo

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