Wykrywanie społeczności — klasteryzacja grafów w sieciach
- Autor metody
- Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
- Rok
- 2002–2019 (algorithm family)
- Typ
- Graph-partitioning / clustering algorithm family
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Wykrywanie społeczności to rodzina algorytmów podziału grafu, które odkrywają gęsto połączone podgrupy — społeczności — w obrębie sieci.
Po raz pierwszy sformalizowana za pomocą miary modularności przez Girvana i Newmana (2002), dziedzina szybko się rozwijała dzięki metodzie Louvain (Blondel et al., 2008), udoskonaleniu Leiden (Traag et al., 2019) oraz podejścia Infomap opartego na teorii informacji. Wszystkie warianty odpowiadają na to samo pytanie: które węzły grupują się ściślej między sobą niż z resztą sieci?
Intuicja stojąca za metodą
Wyobraźmy sobie dużą sieć społeczną, w której niektórzy ludzie rozmawiają głównie ze swoim najbliższym kręgiem, a jedynie okazjonalnie kontaktują się z kimś spoza niego. Wykrywanie społeczności automatycznie znajduje te kręgi, bez konieczności ich wcześniejszego etykietowania. Algorytm reorganizuje węzły w grupy tak, aby połączenia wewnętrzne były gęste, a połączenia międzygrupowe rzadkie — maksymalizując wskaźnik jakości zwany modularnością (lub, w Infomap, minimalizując długość opisu losowego przejścia przez sieć). Wynikiem jest podział: każdy węzeł należy dokładnie do jednej społeczności, a sieć można zwizualizować jako zbiór spójnych klastrów.
Historia
Badanie struktury społeczności w sieciach zostało postawione na podłożu ilościowym przez Girvana i Newmana (2002), którzy wprowadzili koncepcję centralności pośredniej jako narzędzia do hierarchicznego podziału sieci. Newman i Girvan (2004) następnie sformalizowali miarę modularności Q, która stała się standardowym kryterium jakości. Blondel et al. (2008) opublikowali metodę Louvain — dwufazową optymalizację zachłanną, która uczyniła wysokiej jakości wykrywanie społeczności praktycznym dla sieci z milionami węzłów. Traag, Waltman i van Eck (2019) zidentyfikowali wadę strukturalną w Louvain — że może ona prowadzić do wewnętrznie rozłącznych społeczności — i opracowali algorytm Leiden, aby ją naprawić, gwarantując dobrze połączone podziały. Równolegle Rosvall i Bergstrom (2008) opracowali Infomap, który przekształca wykrywanie społeczności w problem kompresji: znajdź podział, który minimalizuje długość opisu losowego przejścia po sieci.
Kiedy stosować
Wykrywanie społeczności jest odpowiednie, gdy dysponujemy siecią (co najmniej ~20 węzłów) i chcemy odkryć ukrytą strukturę grupową bez wstępnego określania grup. Nadaje się do celów eksploracyjnych, opisowych i klasyfikacyjnych na danych binarnych lub ciągłych wag krawędzi, w tym danych sieciowych przekrojowych i podłużnych. Nie wymaga atrybutów węzłów ani rozkładów normalnych. Metoda jest szczególnie przydatna, gdy liczba społeczności jest nieznana. Jeśli sieć jest zbyt mała (poniżej 20 węzłów), preferowane są opisowe statystyki sieci. Wyniki są wrażliwe na definicje wag krawędzi i gęstość sieci, dlatego te wybory zasługują na staranne przemyślenie.
Ograniczenia i uwagi
- Optymalizacja modularności jest podatna na lokalne optima; wyniki mogą się różnić w zależności od uruchomienia i powinny być raportowane jako najlepsze z wielu uruchomień.
- Limit rozdzielczości oznacza, że bardzo małe społeczności w dużych sieciach mogą zostać połączone, maskując drobnoziarnistą strukturę.
- Wyniki są wrażliwe na sposób definiowania wag krawędzi; różne schematy wagowania mogą dawać znacząco różne podziały.
- Złożoność Girvan-Newman wynosi O(m²n) i jest niepraktyczna dla dużych sieci; Louvain lub Leiden powinny być preferowane ze względu na skalę.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Nie wymaga określania liczby społeczności z góry — rozmiar podziału jest określany automatycznie przez dane.
- Skalowalność do dużych sieci: Louvain i Leiden działają w czasie bliskim liniowemu, co czyni je praktycznymi dla sieci z milionami węzłów.
- Leiden gwarantuje dobrze połączone, wewnętrznie spójne społeczności, korygując wadę rozłącznych społeczności w Louvain.
- Możliwość zastosowania zarówno do sieci nieważonych, jak i ważonych, bez założeń dotyczących rozkładu danych.
Zastosowania
- Identyfikacja klastrów badawczych w sieciach cytowań i współautorstwa w celu mapowania dziedzin nauki.
- Wykrywanie modułów funkcjonalnych w sieciach interakcji białko-białko w biologii.
- Znajdowanie społeczności użytkowników w mediach społecznościowych i sieciach komunikacyjnych w celu analizy zachowań.
- Segmentacja sieci klientów w biznesie i marketingu w celu ujawnienia spójnych grup klientów.
- Odkrywanie bloków strukturalnych w sieciach infrastruktury, transportu lub łańcucha dostaw.
Jak to działa
Jak to działa
Wejściem jest graf, którego węzły reprezentują byty (ludzie, strony internetowe, białka, cytowania), a krawędzie reprezentują relacje między nimi. Krawędzie mogą być skierowane lub nieskierowane i mogą mieć wagi. Struktura sąsiedztwa — które węzły są połączone i jak silnie — jest jedynym wymaganym przez algorytmy wejściem. Nie są wymagane żadne etykiety węzłów, klasy ani zewnętrzne atrybuty, chociaż można ich użyć do późniejszej walidacji wyników.
Każdy algorytm rozpoczyna się od początkowego przypisania węzłów do społeczności. W Louvain i Leiden każdy węzeł zaczyna jako własna, jednoelementowa społeczność. Girvan-Newman zaczyna z pełną siecią i iteracyjnie usuwa krawędź o najwyższej centralności pośredniej, stopniowo ujawniając strukturę społeczności. Infomap zaczyna od opisu sieci za pomocą losowego przejścia i koduje go przy użyciu dwupoziomowej mapy w celu minimalizacji długości kodu.
Główna faza poszukuje podziału, który maksymalizuje modularność Q (Louvain, Leiden) lub minimalizuje długość kodu mapy (Infomap). Louvain zachłannie przenosi pojedyncze węzły między społecznościami w celu poprawy Q, następnie agreguje społeczności w super-węzły i powtarza — proces dwufazowy, który dobrze się skaluje, ale może prowadzić do rozłącznych społeczności. Leiden udoskonala Louvain, gwarantując, że każda społeczność jest wewnętrznie połączona, używając lokalnego kroku przenoszenia i udoskonalania przed agregacją. Girvan-Newman usuwa krawędzie iteracyjnie i zapisuje dendrogram podziałów; wybierany jest podział maksymalizujący Q przy dowolnym cięciu dendrogramu. Liczba społeczności wyłania się z samego algorytmu; nie trzeba jej określać z góry.
Jakość końcowego podziału jest podsumowana przez wynik modularności Q, który waha się od −0,5 do 1. Wartości powyżej ~0,3–0,5 są generalnie uważane za wskazujące na znaczącą strukturę społeczności. Ponieważ optymalizacja modularności może utknąć w lokalnych optimach, standardową praktyką jest wielokrotne uruchamianie algorytmu i wybieranie najlepszego wyniku. Podział jest również badany wizualnie i krzyżowo walidowany z dostępnymi atrybutami węzłów lub etykietami prawdy absolutnej, aby potwierdzić jego znaczenie merytoryczne.
Częste pułapki
- Uruchamianie algorytmu raz i traktowanie pojedynczego wyniku jako prawdy absolutnej — zawsze uruchamiaj wielokrotnie i raportuj najlepszą modularność lub używaj metod zespołowych.
- Ignorowanie limitu rozdzielczości: w dużych, rzadkich sieciach małe, ale rzeczywiste społeczności mogą zostać wchłonięte przez większe bez ostrzeżenia.
- Stosowanie algorytmów opartych na modularności do sieci z mniej niż 20 węzłami — struktury społeczności nie można wiarygodnie zidentyfikować w tej skali.
- Mylenie wysokiego wyniku modularności z potwierdzoną strukturą społeczności w świecie rzeczywistym; modularność jest miarą jakości podziału, a nie testem wnioskowania o tym, czy społeczności są statystycznie istotne.
Najczęściej zadawane pytania
Który algorytm wybrać — Louvain, Leiden, Girvan-Newman czy Infomap?
Louvain jest szybką, szeroko stosowaną podstawą dla dużych sieci. Leiden jest preferowanym wyborem, gdy ważna jest poprawność, ponieważ gwarantuje wewnętrznie połączone społeczności i zazwyczaj osiąga wyższą modularność. Girvan-Newman generuje dendrogram przydatny do eksploracji hierarchicznej, ale jest zbyt wolny dla dużych sieci. Infomap jest dobrze przystosowany do sieci skierowanych lub opartych na przepływie, gdzie ścieżka losowego wędrowca ma znaczenie.
Czy muszę z góry określić liczbę społeczności?
Nie. Louvain, Leiden i Infomap automatycznie określają liczbę społeczności na podstawie struktury sieci. Girvan-Newman generuje pełny dendrogram, z którego można odczytać dowolną liczbę społeczności; zazwyczaj wybierany jest podział maksymalizujący Q.
Skąd mam wiedzieć, czy znalezione społeczności są znaczące?
Wynik modularności Q stanowi wewnętrzną miarę jakości danych; wartości powyżej około 0,3–0,5 sugerują nietrywialną strukturę społeczności. Poza tym społeczności powinny być walidowane z wiedzą dziedzinową, atrybutami węzłów lub zewnętrznymi etykietami. Wysokie Q samo w sobie nie dowodzi znaczenia socjologicznego ani biologicznego.
Co się dzieje, gdy wyniki różnią się w zależności od uruchomienia?
Optymalizacja modularności jest heurystyką i różne uruchomienia mogą dawać nieco inne podziały, szczególnie w Louvain. Uruchom algorytm wielokrotnie (co najmniej 10–100 razy w przypadku dużych sieci) i raportuj podział z najwyższym Q. Leiden jest bardziej stabilny niż Louvain, ponieważ jego krok udoskonalania jest bardziej dokładny, ale powtarzane uruchomienia pozostają dobrą praktyką.
Pokrewne metody
Źródła
Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.
Otwórz odnośnik DOISkopiowano.Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.
Otwórz odnośnik do publikacjiSkopiowano.