UK 
EnglishТипова
Polski🔵 Виявлення спільнот (Лувен)
Виявляйте спільноти у мережі, жадібно максимізуючи модулярність методом Лувена. Спостерігайте локальні переміщення вузлів і агрегацію спільнот, що відновлюють закладену структуру зі зростанням Q.
Схожі симуляції
Про цю симуляцію
Ця симуляція реалізує метод Лувена — жадібний алгоритм для виявлення спільнот у мережі шляхом максимізації модулярності Q. Граф генерується за стохастичною блоковою моделлю із закладеними спільнотами, а потім алгоритм чергує дві фази: локальне переміщення, коли кожен вузол жадібно переходить до тієї сусідньої спільноти, яка дає найбільше зростання Q, та агрегацію, коли отримані спільноти згортаються в супервузли, утворюючи менший граф для наступного рівня. Повторення цих двох фаз будує ієрархічну декомпозицію мережі, а модулярність монотонно зростає, доки жоден окремий рух більше не може її покращити.
🔬 Що показано
Випадковий граф, побудований за стохастичною блоковою моделлю: вузли розподіляються по закладених групах, ребра всередині групи з'являються з імовірністю pin, а ребра між групами — з імовірністю pout. Запуск Лувена на цьому графі відновлює (або не відновлює, коли pin і pout близькі) закладену структуру. Живі показники відстежують модулярність Q, кількість виявлених спільнот і поточний прохід/рівень у міру збіжності алгоритму.
🎮 Як користуватися
Оберіть пресет — 3 blocks, 4 blocks, Weak structure або Random (без структури) — або самостійно задайте Nodes, Planted communities, pin і pout та натисніть Regenerate graph. Використовуйте Step, щоб виконати один прохід локального переміщення плюс агрегацію за раз, або Auto-run, щоб дозволити безперервне відтворення з обраною Speed, Pause для зупинки та Reset для повернення до початкового некластеризованого стану. Ви також можете перетягувати будь-який вузол мишею чи дотиком, щоб перевпорядкувати силову розкладку, не впливаючи на кластеризацію.
💡 Чи знали ви?
Типовий пресет «3 blocks» (60 вузлів, 3 закладені спільноти, pin = 0.50, pout = 0.03) навмисно простий: імовірність з'єднання всередині групи набагато вища за міжгрупову, тож Лувен зазвичай відновлює три закладені блоки лише за кілька проходів. Перемкніться на «Weak structure» або «Random», щоб побачити, як модулярності важко зростати, або навіть як граф взагалі не вдається розділити на змістовні групи.
Часті запитання
Що таке модулярність і що означає формула?
Модулярність Q вимірює, наскільки щільніше з'єднані вузли всередині однієї спільноти порівняно з тим, що очікувалося б у випадковому графі з тією ж послідовністю степенів. Формула Q = (1/2m)·Σ[A_ij − k_i k_j/2m]·δ(c_i,c_j) підсумовує для кожної пари вузлів у одній спільноті фактичну вагу ребра A_ij мінус очікувану вагу k_i k_j/2m при випадковому з'єднанні. Q приблизно змінюється від -0,5 до 1, і вищі значення вказують на сильнішу структуру спільнот.
Як фаза локального переміщення вирішує, куди перемістити вузол?
Для кожного вузла алгоритм тимчасово вилучає його з поточної спільноти і розглядає переміщення до будь-якої спільноти, до якої належить один із його сусідів. Він обчислює приріст модулярності для кожної кандидатської спільноти й переміщує вузол туди, де приріст найбільший позитивний, або залишає його на місці, якщо жоден рух не допомагає. Це повторюється для кожного вузла протягом кількох проходів, доки повний прохід не перестане давати переміщення.
Що відбувається під час фази агрегації?
Щойно локальне переміщення стабілізується, кожна виявлена спільнота згортається в один супервузол. Ребра між двома спільнотами стають одним зваженим ребром між їхніми супервузлами, а ребра всередині спільноти стають петлею на супервузлі, що зберігає їхню сумарну внутрішню вагу. Потім локальне переміщення повторно запускається на цьому меншому графі, фактично шукаючи спільноти спільнот, тому процес створює ієрархію рівнів, а не єдиний плоский розподіл.
Чому алгоритм іноді не може знайти закладені спільноти?
Лувен — це жадібна евристика, а не точний оптимізатор, тому він може слідувати лише рухам, які негайно покращують модулярність, і може застрягти в локальному оптимумі. Коли pin і pout близькі один до одного, як у пресетах «Weak structure» чи «Random», закладені групи насправді не набагато щільніші за решту графа, тож алгоритму майже нема якого сигналу модулярності виявляти, і він може об'єднати, розділити або пропустити справжні групи.
Чи впливає перетягування вузлів на виявлені спільноти?
Ні. Перетягування лише змінює екранну позицію (x, y) вузла в силовій розкладці, що використовується для малювання; воно не торкається базових даних суміжності, з якими працює Лувен. Сам крок розкладки просто запускає щокадру просту симуляцію відштовхування/притягання між усіма парами вузлів і ребрами, щоб зберегти зображення читабельним, повністю окремо від логіки виявлення спільнот.