PL 
EnglishDomyślny
Українська🔵 Wykrywanie społeczności (Louvain)
Wykrywaj społeczności w sieci, zachłannie maksymalizując modularność metodą Louvain. Obserwuj lokalne przenoszenie węzłów i agregację społeczności, które odtwarzają ukrytą strukturę w miarę wzrostu Q.
O tej symulacji
Ta symulacja implementuje metodę Louvain, zachłanny algorytm wykrywania społeczności w sieci poprzez maksymalizację modularności Q. Graf jest generowany za pomocą stochastycznego modelu blokowego z zasadzonymi społecznościami, a następnie algorytm naprzemiennie wykonuje dwie fazy: lokalne przenoszenie, gdzie każdy wierzchołek zachłannie przeskakuje do sąsiedniej społeczności dającej największy przyrost Q, oraz agregację, gdzie wynikowe społeczności są zwijane w superwęzły, tworząc mniejszy graf dla kolejnego poziomu. Powtarzanie tych dwóch faz buduje hierarchiczny rozkład sieci, a modularność rośnie monotonicznie, aż żaden pojedynczy ruch nie może jej już poprawić.
🔬 Co przedstawia
Losowy graf zbudowany za pomocą stochastycznego modelu blokowego: wierzchołki są przypisane do zasadzonych grup, krawędzie wewnątrz grupy pojawiają się z prawdopodobieństwem pin, a krawędzie między grupami z prawdopodobieństwem pout. Uruchomienie Louvain na tym grafie odzyskuje (lub nie, gdy pin i pout są bliskie) zasadzoną strukturę. Odczyty na żywo śledzą modularność Q, liczbę wykrytych społeczności oraz bieżący przebieg/poziom w miarę zbiegania algorytmu.
🎮 Jak korzystać
Wybierz predefiniowany układ — 3 bloki, 4 bloki, Słaba struktura lub Losowy (bez struktury) — albo samodzielnie ustaw Wierzchołki, Zasadzone społeczności, pin i pout i naciśnij Wygeneruj graf. Użyj Krok, aby wykonać jeden przebieg lokalnego przenoszenia plus agregacji naraz, lub Autoodtwarzanie, by uruchomić go w sposób ciągły z wybraną Prędkością, Pauza, by zatrzymać, oraz Reset, by wrócić do stanu początkowego bez klastrowania. Możesz też przeciągnąć dowolny wierzchołek myszą lub dotykiem, by przestawić układ skierowany siłami bez wpływu na klastrowanie.
💡 Czy wiesz, że?
Domyślny predefiniowany układ „3 bloki” (60 wierzchołków, 3 zasadzone społeczności, pin = 0,50, pout = 0,03) jest celowo łatwy: prawdopodobieństwo połączenia wewnątrz grupy jest znacznie wyższe niż między grupami, więc Louvain zwykle odzyskuje trzy zasadzone bloki w zaledwie kilku przebiegach. Przełącz na „Słaba struktura” lub „Losowy”, by zobaczyć, jak modularność z trudem rośnie, a nawet nie potrafi w ogóle sensownie podzielić grafu na grupy.
Najczęściej zadawane pytania
Czym jest modularność i co oznacza wzór?
Modularność Q mierzy, o ile gęściej połączone są wierzchołki w tej samej społeczności w porównaniu z tym, czego oczekiwano by w losowym grafie o tej samej sekwencji stopni. Wzór Q = (1/2m)·Σ[A_ij − k_i k_j/2m]·δ(c_i,c_j) sumuje, dla każdej pary wierzchołków w tej samej społeczności, rzeczywistą wagę krawędzi A_ij minus oczekiwaną wagę k_i k_j/2m przy losowym połączeniu. Q mieści się w przybliżeniu w zakresie od -0,5 do 1, a wyższe wartości oznaczają silniejszą strukturę społeczności.
Jak faza lokalnego przenoszenia decyduje, dokąd trafia wierzchołek?
Dla każdego wierzchołka algorytm tymczasowo usuwa go z bieżącej społeczności i rozważa przeniesienie do dowolnej społeczności, do której należy jeden z jego sąsiadów. Oblicza przyrost modularności dla każdej kandydującej społeczności i przenosi wierzchołek do tej, która daje największy dodatni przyrost, lub pozostawia go na miejscu, jeśli żaden ruch nie pomaga. Powtarza się to dla każdego wierzchołka, w wielu przebiegach, aż pełny przebieg nie przyniesie już żadnych ruchów.
Co dzieje się podczas fazy agregacji?
Gdy lokalne przenoszenie się ustabilizuje, każda wykryta społeczność jest zwijana w pojedynczy superwęzeł. Krawędzie między dwiema społecznościami stają się pojedynczą ważoną krawędzią między ich superwęzłami, a krawędzie wewnątrz społeczności stają się pętlą własną na superwęźle, przechowującą ich łączną wagę wewnętrzną. Lokalne przenoszenie jest następnie ponownie uruchamiane na tym mniejszym grafie, efektywnie szukając społeczności społeczności, dlatego proces tworzy hierarchię poziomów, a nie pojedynczy płaski podział.
Dlaczego algorytm czasem nie znajduje zasadzonych społeczności?
Louvain jest zachłanną heurystyką, a nie dokładnym optymalizatorem, więc może wykonywać tylko ruchy, które natychmiast poprawiają modularność, i może utknąć w optimum lokalnym. Gdy pin i pout są bliskie sobie, jak w predefiniowanych układach „Słaba struktura” lub „Losowy”, zasadzone grupy nie są w rzeczywistości dużo gęstsze niż reszta grafu, więc sygnał modularności do wykrycia przez algorytm jest znikomy, przez co może on łączyć, dzielić lub pomijać prawdziwe grupy.
Czy przeciąganie wierzchołków wpływa na wykryte społeczności?
Nie. Przeciąganie zmienia jedynie pozycję (x, y) wierzchołka na ekranie w układzie skierowanym siłami używanym do rysowania; nie dotyka leżących u podstaw danych o sąsiedztwie, na których operuje Louvain. Sam krok układu po prostu uruchamia w każdej klatce prostą symulację odpychania/przyciągania między wszystkimi parami wierzchołków i krawędziami, aby obraz pozostał czytelny, całkowicie niezależnie od logiki wykrywania społeczności.