Jak sprawdzić statystycznie, czy moja sieć (wykres) jest siecią „małego świata”, czy nie?

Sieć małego świata jest rodzajem wykresu matematycznego, na którym większość węzłów nie sąsiaduje ze sobą, ale do większości węzłów można dotrzeć od siebie niewielką liczbą przeskoków lub kroków. W szczególności sieć małego świata jest zdefiniowana jako sieć, w której typowa odległość L między dwoma losowo wybranymi węzłami (liczba wymaganych kroków) rośnie proporcjonalnie do logarytmu liczby węzłów N w sieci, to znaczy

$$L \approx \log(N)$$

Ten związek między L i N jest „regułą kciuka”. W swoich badaniach szukam bardziej profesjonalnego określenia wykresów z małego świata. Jak mogę sprawdzić, czy mój wykres jest wykresem z małego świata, czy nie?

Eksperyment małą świat składa się kilka eksperymentów prowadzonych przez Stanley Milgram i innych badaczy analizujących średnią długość drogi dla sieci społecznych ludzi w Stanach Zjednoczonych. Badania były przełomowe, ponieważ sugerowały, że społeczeństwo ludzkie jest siecią typu małego świata, charakteryzującą się krótkimi ścieżkami. Eksperymenty często kojarzone są ze zwrotem „sześć stopni separacji”, chociaż Milgram sam nie używał tego terminu.

Z góry dziękuję.

TL; DR:

Nie możesz

Co zazwyczaj się robi?

Obecny „aktualny stan techniki” w określaniu, czy sieć jest małym światem, stosuje następujące podejście:

1. Oblicz średnią najkrótszą długość ścieżki  i współczynnik skupienia  Twojej sieci.$L$$C$

2. Wygenerować odpowiedni zespół sieci null modelowych, takich jak Erdős-Renyi grafów losowych lub Maslov-Sneppen grafów losowych .

3. Oblicz średnią średnią najkrótszą długość ścieżki tego zestawu sieci o zerowym modelu; obliczyć analogicznie.$L_\text{r}$$C_\text{r}$

4. Oblicz znormalizowaną najkrótszą ścieżkę . i .$λ := L/L_\text{r}$$γ := C/C_\text{r}$

5. Jeśli i spełniają określone kryteria (np. i ), nazwij sieć siecią małego świata.$λ$$γ$$λ≈1$$γ>1$

Chodzi o to, że:

• Sieci małych światów powinny mieć pewną strukturę przestrzenną, co odzwierciedla wysoki współczynnik grupowania. Natomiast losowe sieci nie mają takiej struktury i mają niski współczynnik grupowania.

• Sieci małych światów są wydajne w komunikacji i podobne, a zatem mają małą długość najkrótszej ścieżki, porównywalną do sieci losowych. Natomiast sieci czysto przestrzenne mają wysoką najkrótszą długość ścieżki.

Gdzie są problemy

• Nie mówi to nic o tym, jak średnia najkrótsza ścieżka skaluje się z rozmiarem sieci. W rzeczywistości w przypadku prawdziwych sieci nie można zastosować całej cytowanej definicji, ponieważ nie istnieje coś takiego jak ta sama sieć z inną liczbą węzłów.

• Załóżmy, że przyjmujemy inną definicję małego świata, która nie jest bezpośrednio oparta na wartościach i , np .:$λ$$γ$

  Sieć małego świata to sieć przestrzenna z dodanymi połączeniami dalekiego zasięgu.

  W dalszym ciągu nie jesteśmy w stanie wywrzeć solidnego wpływu na to, czy taka definicja jest spełniona tylko przy użyciu i (lub w rzeczywistości innych miar sieciowych). Interpretacja wielu badań zakłada, że ​​wszystkie sieci są realizacją modelu Watts – Strogatz z pewnym prawdopodobieństwem ponownego podłączenia , co nie jest wcale uzasadnione: znamy wiele innych modeli sieci, których realizacje są całkowicie odmienne od modelu Watts – Strogatz.$λ$$γ$

• Powyższa metoda nie jest odporna na błędy pomiarowe. Małe błędy przy ustanawianiu sieci z pomiarów wystarczą, aby np. Sieć wyglądała jak sieć małego świata, patrz np. Bialonski i in., Chaos (2010) i Papo i in., Front. Szum. Neurosci. (2016) . W rzeczywistości nie znam żadnego badania, które twierdzi, że jakaś sieć empiryczna nie jest siecią małego świata.

Sidenote: Co byś zyskał?

Nie znam żadnego przydatnego wglądu, jaki można uzyskać z jakiejś sieci będącej małym światem. Twierdzenie, że pewien typ sieci jest dobrze opisany przez pewien model sieci (np. Model Watts-Strogatz), może być przydatne w badaniach modelowania, ale to znacznie więcej niż tylko twierdzenie o małej światowości.

^{Pełna nota prawna: Jedna z powyższych prac pochodzi z mojego bezpośredniego środowiska akademickiego.}

Indeks Small-Worldness można obliczyć w „R” za pomocą funkcji smallworldness w pakiecie qgraph .

Jest to oparte na: Humphries, MD, i Gurney, K. (2008). Sieć „ mały świat”: metoda ilościowa do określenia kanonicznej równoważności sieci . PLoS One, 3 (4), e0002051

Z gazety:

„Sieć jest teraz uważana za„ mały świat ”, jeśli S> 1 - twierdzenie, które można przetestować statystycznie.”