What is the Louvain method?

The Louvain method is a greedy, multi-level algorithm for detecting communities in large networks by maximising a quality function called modularity. It alternates between a local node-moving phase and a graph-aggregation phase, and is prized for scaling to networks with millions of nodes while typically finding high-modularity partitions in near-linear time.

What exactly is modularity, and why maximise it?

Modularity (Q) measures how much denser the connections are inside proposed communities than would be expected in a random graph with the same degree sequence. Q ranges roughly from -0.5 to 1; values above about 0.3 usually indicate meaningful community structure. Louvain greedily moves nodes and merges communities to push Q as high as possible, though like most modularity maximisers it is a heuristic, not a guaranteed global optimum.

How does the resolution parameter change the result?

The resolution parameter (γ) scales the penalty term in the modularity formula. Values below 1 relax that penalty, favouring fewer, larger communities; values above 1 tighten it, favouring more, smaller communities. This lets you probe network structure at different granularities without changing the underlying graph.

Why does the algorithm run in phases?

Phase 1 repeatedly moves individual nodes into whichever neighbouring community most increases modularity until no single move helps. Phase 2 then collapses each discovered community into one super-node, turning intra-community edges into self-loops and inter-community edges into weighted links between super-nodes. Repeating both phases on the shrinking condensed graph lets small local merges compound into large-scale structure in only a handful of passes.

Is this a real implementation or a visual approximation?

It is a genuine implementation. Every node move is evaluated with the real modularity-gain formula using each node's degree and its neighbouring communities' internal and total degree, the graph is actually aggregated between phases, and the modularity score shown is computed directly from the original graph's edges and the current community assignment — not a scripted or pre-baked number.

Strona główna▸AI i ML▸Wykrywanie społeczności w sieci społecznościowej

🕸️ Wykrywanie społeczności w sieci społecznościowej — algorytm Louvain na żywo

Obserwuj, jak prawdziwy algorytm optymalizacji modularności Louvain iteracyjnie łączy węzły symulowanego grafu społecznościowego w społeczności, maksymalizując rzeczywisty wynik modularności na żywo podczas eksploracji sieci.

AI i ML3DZaawansowany60 FPS

O tej symulacji

Ten symulator generuje syntetyczną sieć społecznościową z prawdziwą strukturą klastrów odniesienia — kilka gęsto połączonych grup znajomych powiązanych rozproszeniem rzadszych krawędzi międzygrupowych — a następnie uruchamia na niej prawdziwy algorytm Louvain. Każdy ruch węzła jest oceniany rzeczywistym wzorem przyrostu modularności, społeczności są naprawdę zwijane w super-węzły między fazami, a wyświetlany na ekranie wynik modularności (Q) jest obliczany bezpośrednio z oryginalnego grafu i bieżącego podziału — nic tutaj nie jest zaskryptowaną animacją.

🔬 Co pokazuje

Węzły są rozmieszczone w 3D za pomocą żywej symulacji sił — wzajemne odpychanie, sprężyste przyciąganie wzdłuż krawędzi oraz delikatne przyciąganie w stronę centroidu społeczności każdego węzła. Gdy Louvain przypisuje węzły do społeczności o wyższej modularności, kolory węzłów natychmiast się aktualizują, a układ przesuwa się w widocznie rozdzielone klastry, czyniąc zachłanne lokalne przeszukiwanie algorytmu widocznym krok po kroku.

🎮 Jak korzystać

Użyj Nowy graf, aby uzyskać nową losową sieć, Wykonaj krok fazy 1, aby wykonać jedno przejście fazy przesuwania węzłów, Agreguj → następny poziom, aby zwinąć bieżące społeczności w super-węzły, lub Uruchom pełny algorytm, aby Louvain działał automatycznie do zbieżności na wszystkich poziomach. Suwak Rozdzielczość (γ) na żywo zmienia wagę wyrazu kary modularności, pozwalając skierować algorytm w stronę grubszych lub drobniejszych społeczności. Przeciągnij, by obracać kamerę, i przewiń, by przybliżyć.

💡 Czy wiesz, że...

Dwufazowa sztuczka Louvain — przesuń węzły, a następnie zwiń społeczności w pojedyncze super-węzły i powtórz — jest tym, co pozwala mu skalować się do sieci z milionami węzłów w czasie w przybliżeniu liniowym, podczas gdy naiwne wyczerpujące przeszukiwanie w poszukiwaniu podziału maksymalizującego modularność jest NP-trudne. Pozostaje jednym z najczęściej używanych algorytmów wykrywania społeczności w nauce o sieciach, od grafów mediów społecznościowych po sieci oddziaływań białek.

Najczęściej zadawane pytania

Czym jest metoda Louvain?

Metoda Louvain to zachłanny, wielopoziomowy algorytm wykrywania społeczności w dużych sieciach poprzez maksymalizację funkcji jakości zwanej modularnością. Naprzemiennie wykonuje lokalną fazę przesuwania węzłów i fazę agregacji grafu, i jest ceniona za skalowalność do sieci z milionami węzłów, zwykle znajdując podziały o wysokiej modularności w czasie niemal liniowym.

Czym dokładnie jest modularność i po co ją maksymalizować?

Modularność (Q) mierzy, o ile gęstsze są połączenia wewnątrz proponowanych społeczności niż byłoby to oczekiwane w losowym grafie o tej samej sekwencji stopni. Q mieści się w przybliżeniu w zakresie od −0,5 do 1; wartości powyżej około 0,3 zwykle wskazują na znaczącą strukturę społeczności. Louvain zachłannie przesuwa węzły i łączy społeczności, by maksymalnie podnieść Q, choć podobnie jak większość metod maksymalizujących modularność jest to heurystyka, a nie gwarantowane globalne optimum.

Jak parametr rozdzielczości zmienia wynik?

Parametr rozdzielczości (γ) skaluje wyraz kary we wzorze modularności. Wartości poniżej 1 łagodzą tę karę, faworyzując mniej, ale większych społeczności; wartości powyżej 1 ją zaostrzają, faworyzując więcej, mniejszych społeczności. Pozwala to badać strukturę sieci na różnych poziomach szczegółowości bez zmiany bazowego grafu.

Czemu algorytm działa w fazach?

Faza 1 wielokrotnie przesuwa poszczególne węzły do tej sąsiedniej społeczności, która najbardziej zwiększa modularność, aż żaden pojedynczy ruch nie pomaga. Faza 2 następnie zwija każdą odkrytą społeczność w jeden super-węzeł, zamieniając krawędzie wewnątrzspołecznościowe w pętle własne, a krawędzie międzyspołecznościowe w ważone połączenia między super-węzłami. Powtarzanie obu faz na kurczącym się skondensowanym grafie pozwala, by małe lokalne połączenia złożyły się w strukturę wielkoskalową w zaledwie kilku przebiegach.

Czy to prawdziwa implementacja, czy wizualne przybliżenie?

To prawdziwa implementacja. Każdy ruch węzła jest oceniany rzeczywistym wzorem przyrostu modularności z użyciem stopnia każdego węzła oraz wewnętrznego i całkowitego stopnia sąsiednich społeczności, graf jest naprawdę agregowany między fazami, a wyświetlany wynik modularności jest obliczany bezpośrednio z krawędzi oryginalnego grafu i bieżącego przypisania do społeczności — nie jest to zaskryptowana ani z góry ustalona liczba.

⚙ Co pod maską

Graph TheoryCommunity DetectionLouvainModularityForce-Directed Layout

3D · renderer Three.js / WebGL · cel 60 FPS · działa w całości w przeglądarce, bez instalacji