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

10

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.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ę.

Übel Yildmar
źródło
2
Nie wiem, jaki jest cel twojego papara ani twojego pochodzenia. Czy masz rzeczywisty wykres, który chcesz przetestować? Możesz podjąć podstawowe miary opisowe swojego wykresu, wystarczyłaby każda biblioteka wykresów (np. Networkx w pythonie lub igraph w R). Wystarczy sprawdzić, czy sieć jest podłączona, jaka jest średnica, średnia najkrótsza ścieżka itp. Jeśli generujesz wykres lub twój kontekst jest inny, powiedziałbym, że potrzebuję więcej informacji, aby odpowiedzieć na twoje pytanie.
lrnzcig,
2
Aby ocenić obecność tego logarytmicznego związku, myślę, że potrzebujesz szeregu wartości. Na przykład sekwencja migawek wykresu ewoluuje w czasie. Lub zbiór różnych wykresów odpowiadających podobnym (porównywalnym) systemom (np. Sieci komputerowe kilku firm różnej wielkości).
Vincent Labatut

Odpowiedzi:

7

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.do

  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.rdor

  4. Oblicz znormalizowaną najkrótszą ścieżkę . i .λ: =L./L.rγ: =do/dor

  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.

Wrzlprmft
źródło
Czy znasz także jakieś artykuły, w których wymieniona jest metodologia wymieniona w tej odpowiedzi? Tworzenie zespołu sieci, obliczanie jego średniej itp.
Ostatnie słowo
@TheLastWord: Czy znasz też jakieś artykuły , w których wymieniona jest metodologia wymieniona w tej odpowiedzi? - Artykuł Bialońskiego i in. Podsumowuje to podejście i powinien zawierać odpowiednie odniesienia. Zobacz także mój artykuł .
Wrzlprmft