Co to znaczy, że wszystkie krawędzie sieci / wykresu w świecie rzeczywistym są statystycznie równie prawdopodobne, że zdarzy się to przez przypadek?

11

Korzystałem z metody ekstrakcji sieci szkieletowej opisanej w tym artykule: http://www.pnas.org/content/106/16/6483.abstract

Zasadniczo autorzy proponują metodę opartą na statystykach, która daje prawdopodobieństwo dla każdej krawędzi na wykresie, że krawędź mogła wystąpić przypadkowo. Używam typowej granicy istotności statystycznej wynoszącej 0,05.

Zastosowałem tę metodę do kilku rzeczywistych sieci, a co ciekawe, niektóre sieci nie mają tak znaczących krawędzi. Próbuję zrozumieć, co to oznacza dla sieci. Jedynym innym razem, gdy zastosowałem tę metodę do sieci i nie było żadnych znaczących krawędzi, było to, gdy zastosowałem metodę do losowych sieci, które wygenerowałem, i jest to dokładnie to, czego byśmy oczekiwali.

Jako przykład sieci z prawdziwego świata, być może widziałeś ostatnią wizualizację sieci, która pojawiła się w The Economist, pokazując polaryzację Senatu USA w ciągu ostatnich 25 lat: http://www.economist.com/news/united-states/21591190 -zjednoczone-stany-ameba . Zastosowałem metodę ekstrakcji sieci szkieletowej do tych sieci i żadne krawędzie nie były tak znaczące. Chociaż surowe krawędzie najwyraźniej wykazują preferencyjne przywiązanie i skupianie, czy jest to przypadek? Czy sieć senacka sieci wyborczej jest zasadniczo losowa?

Randy Olson
źródło

Odpowiedzi:

6

Hipoteza zerowa związana z metodami szkieletowymi brzmi:

[] Znormalizowane wagi odpowiadające połączeniom pewnego węzła stopnia k są wytwarzane przez losowe przypisanie z rozkładu równomiernego.

Jeśli nie ma żadnych „znaczących” krawędzi, hipoteza zerowa obowiązuje dla całego wykresu, tj. Wagi krawędzi wynikają z węzłowych skłonności do wysyłania i odbierania więzi.

W zależności od analizowanych relacji metoda szkieletowa może być nieodpowiednia. Ta metoda działa najlepiej w przypadku sieci, które są koncepcyjnie ważonymi sieciami jednomodowymi. Sieci dwumodowe mogą być wyświetlane jako ważona sieć jednomodowa, ale często nie ma to sensu.

Opierając się na twoim przykładzie w Economist, nie ma sensu analizować głosowania w Senacie jako sieci jednomodowej ważonej liczbą współdzielonych głosów. Głosowanie w Senacie to podpisany, dwumodowy związek. Senatorowie (i) mają związek z aktami prawnymi (j) i wstrzymują się od głosu (0) lub głosują za (+1) lub przeciw (-1) przepisom. Przekształcenie sieci w ważoną sieć jednomodową opartą na umowie, a następnie wykonanie na niej analizy szkieletowej stanowiłoby poważne ograniczenie danych. Niektóre akty prawne są bardziej podzielne politycznie, a niektóre mają więcej głosów niż inne - metody szkieletowe nie uchwycą tych mechanizmów.

Zamiast metod szkieletowych warto rozważyć testy Warunkowego Uniform Graph (CUG). Ideą tych testów jest ustalenie, czy pewne właściwości na poziomie grafu (np. Grupowanie, średnia długość ścieżki, centralizacja, homofilia) wynikają z przypadku. Proces przebiega następująco:

  1. Weź pomiar f z obserwowanego wykresu
  2. Wygeneruj losowy wykres, który kontroluje określone właściwości obserwowanego wykresu (np. Rozmiar, liczba krawędzi, rozkład stopni itp.)
  3. Weź pomiar f z losowego wykresu
  4. Powtórz kroki 2 i 3 wiele razy (np. 1000), aby uzyskać rozkład zerowy
  5. Porównaj zaobserwowany pomiar z rozkładem zerowym

W przypadku sieci dwumodowych sensowne byłoby utworzenie losowego wykresu poprzez permutację obserwowanego wykresu (zarówno tnet, jak i statnet w R mają procedury umożliwiające permutację sieci dwumodowych). Jeżeli pomiar f wymaga sieci jednomodowej, proces randomizacji należy wykonać w sieci dwumodowej przed wyświetleniem jej jako sieci jednomodowej.

BenjaminLind
źródło
4

W cytowanym artykule autorzy uważają, że w złożonej sieci „węzły [reprezentują] elementy [modelowanego] systemu, a ważone krawędzie identyfikują obecność interakcji i jej względną siłę” (moje podkreślenie) .

W badanej sieci, jeśli dobrze rozumiem artykuł o ekonomistach, istnieje związek między 2 senatorami, jeśli głosowali podobnie co najmniej 100 razy. Tak więc linki nie modelują interakcji, ale podobieństwa (między zachowaniami wyborczymi senatorów). Z mojego doświadczenia wynika, że ​​sieci podobieństwa nie wykazują takiego samego rozkładu stopnia jak sieci interakcji, w tym sensie, że nie są tak heterogeniczne. Ponadto parametr progowy używany podczas wyodrębniania sieci (tutaj: 100) czasami ma silny wpływ na rozkład stopni.

Co więcej, nie mogłem znaleźć wzmianki o żadnych wagach w artykule Economist. Jednak obecność wag wydaje się być ważnym punktem w metodzie opisanej w pracy Ángeles Serrano i in . cytujesz w swoim pytaniu.

Na podstawie tych dwóch obserwacji wydaje się możliwe, że metoda nie działa dokładnie na tych danych, ponieważ nie została zaprojektowana do przetwarzania sieci tego typu. Może możesz sprawdzić rozkład stopni: czy jest on wyśrodkowany na wartości charakterystycznej, czy heterogeniczny? A co z wagami, czy są jakieś?

Vincent Labatut
źródło
Sam odtworzyłem dane ze źródłowej strony internetowej, więc podałem wagi i nie zastosowałem arbitralnego progu odcięcia. Dlatego uważam, że dane, na które zastosowałem metodę szkieletową, nie powinny mieć wpływu na te problemy. Dobry pomysł na sprawdzenie rozkładu stopni - muszę rzucić okiem!
Randy Olson