Model blokowy stochastyczny — probabilistyczne wykrywanie społeczności w sieciach
- Rok
- 1983
- Typ
- Probabilistic generative graph model
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Model blokowy stochastyczny (SBM), wprowadzony przez Hollanda, Laskeya i Leinhardta (1983), jest probabilistycznym modelem generatywnym dla grafów, który przypisuje węzły do ukrytych bloków i parametrycznie szacuje prawdopodobieństwa połączeń między blokami.
Jest to fundamentalne podejście do wykrywania społeczności, identyfikacji struktur rdzeń-peryferia i odkrywania hierarchicznych struktur w analizie sieci.
Intuicja stojąca za metodą
Wyobraźmy sobie sieć społeczną, w której ludzie grupują się w klastry — współpracownicy, rodzina, drużyny sportowe — a połączenia wewnątrz grupy są bardziej prawdopodobne niż połączenia między grupami. Model blokowy stochastyczny formalizuje tę intuicję: zakłada, że każdy węzeł ma ukrytą etykietę grupy, a prawdopodobieństwo krawędzi między dowolnymi dwoma węzłami zależy wyłącznie od tego, do których grup należą te dwa węzły. Dopasowanie modelu oznacza znalezienie ukrytych etykiet, które najlepiej wyjaśniają zaobserwowany wzorzec krawędzi. Wynikiem jest ugruntowany statystycznie, oparty na zasadach podział sieci na bloki, bez konieczności zakładania, że grupy są gęstymi kliki — model uwzględnia struktury rdzeń-peryferia, a nawet wzorce dysasortatywne, w których połączenia międzyblokowe przewyższają połączenia wewnątrzblokowe.
Historia
Model blokowy stochastyczny został wprowadzony przez Hollanda, Laskeya i Leinhardta w ich artykule z 1983 roku w czasopiśmie Social Networks jako probabilistyczne uogólnienie wcześniejszych prac nad modelowaniem blokowym w analizie sieci społecznych. Przez dwie dekady pozostawał głównie narzędziem teoretycznym; zyskał praktyczne znaczenie wraz z rozwojem skalowalnych algorytmów wnioskowania — wariantowego EM i MCMC — w latach 2010. Model DCSBM został wprowadzony przez Karrera i Newmana (2011) w celu rozwiązania problemu heterogeniczności stopni. Przegląd Lee i Wilkinsona z 2019 roku w Applied Network Science skonsolidował rodzinę rozszerzeń, obejmując modele z zaimplementowaną partycją, SBM z mieszanymi przynależnościami i warianty hierarchiczne. Obecnie SBM i jego potomkowie są referencyjnym probabilistycznym frameworkiem do wykrywania społeczności i klastrowania grafów.
Kiedy stosować
Użyj modelu blokowego stochastycznego, gdy masz sieć z co najmniej 50 węzłami i chcesz odkryć ukrytą strukturę grupową, nie zakładając, że grupy muszą być gęstymi klikami. Nadaje się do grafów skierowanych lub nieskierowanych, ważonych lub nieważonych, i pasuje zarówno do zadań eksploracyjnych, jak i klasyfikacyjnych. Wariant DCSBM jest preferowany, gdy stopnie węzłów znacznie się różnią. Jeśli graf ma mniej niż 20 węzłów, struktury społeczności nie można wiarygodnie oszacować i należy zamiast tego użyć prostszych metryk opisowych.
Ograniczenia i uwagi
- Wymaga co najmniej około 50 węzłów do wiarygodnego oszacowania bloków; bardzo małe grafy dają niestabilne rozwiązania.
- Wnioskowanie jest kosztowne obliczeniowo dla dużych grafów: wymagane jest wariantowe EM lub MCMC, a zbieżność nie jest gwarantowana.
- Założenie jednorodności w podstawowym SBM między parami bloków załamuje się, gdy wskaźniki połączeń wewnątrzblokowych się różnią — DCSBM łagodzi, ale nie eliminuje tego problemu.
- Wybór bloków za pomocą BIC lub czynnika Bayesa może nadal niedostatecznie lub nadmiernie segmentować, jeśli graf ma słabo rozdzielone społeczności.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Ugruntowany probabilistyczny framework, który pozwala na wybór modelu za pomocą BIC lub czynnika Bayesa, unikając arbitralnych wyborów parametrów.
- Uwzględnia szeroki zakres wzorców strukturalnych — społeczności, rdzeń-peryferia, dwudzielne i hierarchiczne — wykraczające poza założenie gęstej kliki w metodach algorytmicznych.
- Wariant z poprawką na stopień obsługuje grafy z heterogenicznymi rozkładami stopni i hubami bez zniekształcania przypisań bloków.
- Dostarcza prawdopodobieństwa przynależności a posteriori, umożliwiając miękkie lub niepewne przypisania węzłów zamiast twardych podziałów.
Zastosowania
- Wykrywanie społeczności badawczych w sieciach cytowań i współpracy w naukach społecznych i przyrodniczych.
- Identyfikacja modułów funkcjonalnych w sieciach biologicznych, takich jak grafy interakcji białko-białko i współekspresji genów.
- Odkrywanie segmentów klientów lub pierścieni oszustw w sieciach transakcyjnych i finansowych.
- Charakteryzacja struktury rdzeń-peryferia w sieciach handlu międzyorganizacyjnego lub międzykrajowego.
- Benchmarking i ocena innych algorytmów wykrywania społeczności przy użyciu syntetycznych grafów wygenerowanych przez SBM jako prawdy podstawowej.
Jak to działa
Jak to działa
Analityk określa kandydujący zakres liczby bloków K i wybiera wariant: podstawowy SBM zakłada jednorodny rozkład stopni wewnątrzbloku, podczas gdy SBM z poprawką na stopień (DCSBM) dodaje parametry stopnia na poziomie węzła, aby obsłużyć huby i heterogeniczne sekwencje stopni. Wybór wariantu jest informowany przez rozkład stopni zaobserwowanego grafu.
Biorąc pod uwagę macierz sąsiedztwa, model szacuje przynależność do bloków i macierz prawdopodobieństw połączeń K×K za pomocą algorytmu wnioskowania. Dla małych i średnich grafów możliwe jest dokładne maksymalizowanie; dla dużych grafów stosuje się wariantowe oczekiwanie-maksymalizację (wariancyjne EM) lub próbkowanie łańcuchowe Markowa (MCMC), aby uczynić wnioskowanie wykonalnym.
Liczba bloków K nie jest znana z góry i musi być wybrana na podstawie danych. Preferowane kryteria wyboru to Bayesowski Kryterium Informacyjne (BIC) i czynnik Bayesa, które oba penalizują złożoność modelu i wybierają K, które najlepiej równoważy dopasowanie z parsymonią. Zasada minimalnej długości opisu (MDL) leży u podstaw implementacji w graph-tool.
Po ustaleniu optymalnego K i przypisania bloków, macierz połączeń bloków jest analizowana w celu scharakteryzowania struktury: bloki asortatywne odpowiadają społecznościom, bloki dysasortatywne wzorcom przypominającym grafy dwudzielne, a profile mieszane układom rdzeń-peryferia. Przynależności węzłów są raportowane z prawdopodobieństwami a posteriori, jeśli algorytm wnioskowania je dostarcza.
Częste pułapki
- Ustalenie K arbitralnie zamiast wybierania go za pomocą BIC lub czynnika Bayesa prowadzi do nierzetelnych podziałów — zawsze używaj ugruntowanego kryterium wyboru modelu.
- Zastosowanie podstawowego SBM do grafu z heterogeniczną sekwencją stopni (huby, rozkład stopni typu prawo potęgowe) zawyża szacunki liczby bloków; zamiast tego użyj DCSBM.
- Traktowanie przynależności do bloku jako pewnej, gdy a posteriori jest rozproszone, przecenia pewność siebie — raportuj niepewność, gdy jest dostępna.
- Mylenie wyników SBM z rzeczywistymi społecznościami: model znajduje statystycznie wiarygodne struktury ukryte, niekoniecznie grupy o znaczeniu socjologicznym. Waliduj w oparciu o wiedzę dziedzinową.
- Uruchamianie SBM na mniej niż 20 węzłach daje zdegenerowane rozwiązania — dla małych grafów użyj metryk opisowych sieci lub prostego wykrywania społeczności.
Najczęściej zadawane pytania
Czym model blokowy stochastyczny różni się od wykrywania społeczności opartego na modularności?
Maksymalizacja modularności (np. Louvain, Leiden) optymalizuje heurystyczny cel, który niejawnie zakłada społeczności asortatywne, o w przybliżeniu równej wielkości, i ma znany limit rozdzielczości, który uniemożliwia wykrycie małych społeczności. SBM jest probabilistycznym modelem generatywnym z jawnymi założeniami; liczba bloków jest wybierana przez wybór modelu (BIC lub czynnik Bayesa), a nie przez optymalizację heurystyczną, i może wykrywać struktury dysasortatywne i rdzeń-peryferia, które metody oparte na modularności pomijają.
Kiedy powinienem użyć DCSBM zamiast podstawowego SBM?
Użyj DCSBM, gdy rozkład stopni węzłów jest heterogeniczny — na przykład, gdy niewielka liczba hubów odpowiada za dużą część krawędzi, lub gdy sekwencja stopni podąża za przybliżonym prawem potęgowym. Podstawowy SBM traktuje wszystkie węzły w bloku jako wymienne, co powoduje, że huby są wciągane do własnych fałszywych bloków. DCSBM dodaje człon poprawki na stopień, który oddziela pozycję strukturalną od stopnia, prowadząc do bardziej interpretowalnych przypisań bloków w takich grafach.
Jak wybrać liczbę bloków K?
Dopasuj modele dla zakresu wartości K i wybierz ten, który minimalizuje BIC lub maksymalizuje czynnik Bayesa (lub równoważnie minimalizuje długość opisu). Nie wybieraj K na podstawie wizualnej inspekcji grafu lub oczekiwań a priori. Większość implementacji (graph-tool, blockmodels w R) automatyzuje to wyszukiwanie. Zaleca się również analizę wrażliwości — sprawdzanie, czy jakościowa struktura bloków zmienia się, gdy K jest zmieniane o jeden.
Jaka jest minimalna wielkość sieci, aby SBM był wiarygodny?
Rejestr określa minimum 50 węzłów dla wiarygodnego wnioskowania. Przy mniej niż 20 węzłach model nie jest w stanie zidentyfikować znaczącej struktury społeczności i dopasuje szum — zamiast tego użyj opisowych statystyk sieci lub prostego wykrywania społeczności. W przedziale od 20 do 50 węzłów wyniki należy traktować jako eksploracyjne i interpretować z ostrożnością.
Pokrewne metody
Źródła
Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.
Otwórz odnośnik DOISkopiowano.Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.
Otwórz odnośnik DOISkopiowano.