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.

Головна▸ШІ та Машинне навчання▸Детектор Спільнот у Соціальній Мережі — Алгоритм Лувена Наживо

🕸️ Детектор Спільнот у Соціальній Мережі — Алгоритм Лувена Наживо

Спостерігайте, як справжній алгоритм оптимізації модулярності Лувена ітеративно об'єднує вузли симульованого соціального графа у спільноти, максимізуючи справжній показник модулярності наживо під час дослідження мережі.

AI & Machine Learning3DПросунутий60 FPS

Про цю симуляцію

Цей симулятор генерує синтетичну соціальну мережу зі справжньою еталонною кластерною структурою — кілька щільно зв'язаних груп друзів, з'єднаних розсипом рідших міжгрупових ребер — а потім запускає над нею справжній алгоритм Лувена. Кожен рух вузла оцінюється за реальною формулою приросту модулярності, спільноти справді згортаються в супервузли між фазами, а показник модулярності (Q), що відображається на екрані, обчислюється безпосередньо з початкового графа й поточного розбиття — тут немає жодної сценарної анімації.

🔬 Що показано

Вузли розташовані в 3D за допомогою живої симуляції силового розташування — взаємне відштовхування, пружинне притягання вздовж ребер і легке притягання до центроїда спільноти кожного вузла. У міру того, як Лувен перепризначає вузли до спільнот із вищою модулярністю, кольори вузлів одразу оновлюються, а розташування зміщується у видимо розділені кластери, роблячи жадібний локальний пошук алгоритму видимим крок за кроком.

🎮 Як користуватися

Використовуйте «Регенерувати граф» для свіжої випадкової мережі, «Крок фази 1», щоб виконати один прохід фази переміщення вузлів, «Агрегація → Наступний рівень», щоб згорнути поточні спільноти в супервузли, або «Запустити повний алгоритм», щоб дати Лувену автоматично збігтися на всіх рівнях. Повзунок «Роздільна здатність (γ)» переважує штрафний член модулярності наживо, дозволяючи спрямувати алгоритм до грубіших або дрібніших спільнот. Перетягніть, щоб обертати камеру, і прокручуйте для масштабування.

💡 Чи знали ви?

Двофазний трюк Лувена — перемістити вузли, потім стягнути спільноти в окремі супервузли й повторити — це те, що дозволяє йому масштабуватися до мереж із мільйонами вузлів за приблизно лінійний час, тоді як наївний вичерпний пошук розбиття з максимальною модулярністю є NP-складним. Він залишається одним із найпоширеніших алгоритмів виявлення спільнот у мережевій науці — від графів соціальних мереж до мереж білкових взаємодій.

Часті питання

Що таке метод Лувена?

Метод Лувена — це жадібний багаторівневий алгоритм для виявлення спільнот у великих мережах шляхом максимізації функції якості, яка називається модулярністю. Він чергує локальну фазу переміщення вузлів і фазу агрегації графа, і цінується за здатність масштабуватися до мереж із мільйонами вузлів, зазвичай знаходячи розбиття з високою модулярністю за майже лінійний час.

Що таке модулярність і навіщо її максимізувати?

Модулярність (Q) вимірює, наскільки щільніші зв'язки всередині запропонованих спільнот порівняно з тим, що очікувалося б у випадковому графі з такою самою послідовністю ступенів. Q змінюється приблизно від −0,5 до 1; значення вище приблизно 0,3 зазвичай вказують на змістовну структуру спільнот. Лувен жадібно переміщує вузли та об'єднує спільноти, щоб підняти Q якомога вище, хоча, як і більшість методів максимізації модулярності, це евристика, а не гарантований глобальний оптимум.

Як параметр роздільної здатності змінює результат?

Параметр роздільної здатності (γ) масштабує штрафний член у формулі модулярності. Значення нижче 1 послаблюють цей штраф, надаючи перевагу меншій кількості більших спільнот; значення вище 1 посилюють його, надаючи перевагу більшій кількості менших спільнот. Це дозволяє досліджувати структуру мережі з різною деталізацією, не змінюючи базовий граф.

Чому алгоритм працює фазами?

Фаза 1 повторно переміщує окремі вузли в ту сусідню спільноту, яка найбільше підвищує модулярність, доки жоден окремий рух не допомагає. Потім фаза 2 згортає кожну виявлену спільноту в один супервузол, перетворюючи внутрішньоспільнотні ребра на самопетлі, а міжспільнотні ребра — на зважені зв'язки між супервузлами. Повторення обох фаз на дедалі меншому згорнутому графі дозволяє малим локальним об'єднанням складатися у великомасштабну структуру лише за кілька проходів.

Це справжня реалізація чи візуальне наближення?

Це справжня реалізація. Кожен рух вузла оцінюється за реальною формулою приросту модулярності з використанням ступеня кожного вузла та внутрішнього й загального ступеня сусідніх спільнот, граф дійсно агрегується між фазами, а показаний показник модулярності обчислюється безпосередньо з ребер початкового графа й поточного призначення спільнот — це не сценарне чи заздалегідь підготовлене число.

⚙ Під капотом

Справжній алгоритм оптимізації модулярності Лувена ітеративно об'єднує вузли симульованого соціального графа у спільноти, максимізуючи справжній показник модулярності наживо під час дослідження мережі.

Теорія графівВиявлення спільнотLouvainМодулярністьСилове розташування

3D · рушій Three.js / WebGL · ціль 60 кадрів/с · працює повністю на клієнті, без встановлення