Модульність – це міра структури мереж або графів, яка вимірює силу поділу мережі на модулі (також звані групами, кластерами або спільнотами). Мережі з високою модульністю характеризуються щільними зв’язками між вузлами всередині окремих модулів і розрідженими зв’язками між вузлами, що належать до різних модулів. Модульність часто використовується в методах оптимізації для виявлення структури спільнот у мережах. Біологічні мережі, зокрема мережі мозку тварин, демонструють високий рівень модульності. Однак максимізація модульності не є статистично узгодженою, оскільки вона виявляє спільноти навіть у власній нульовій моделі, тобто в повністю випадкових графах, і тому не може бути використана для пошуку статистично значущих структур спільнот в емпіричних мережах. Крім того, було показано, що модульність має обмеження роздільної здатності, через що вона не здатна виявляти малі спільноти.

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

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

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

Існують різні методи обчислення модульності. У найпоширенішому варіанті концепції рандомізація ребер виконується таким чином, щоб зберегти степінь кожної вершини. Розглянемо граф з вузли та зв'язки (ребра) такі, що граф можна розділити на дві спільноти за допомогою змінної належності Якщо вузол належить до громади 1, , або якщо належить до громади 2, Нехай матриця суміжності мережі представлена як , де означає, що між вузлами немає ребра (немає взаємодії) і і означає, що між ними є ребро. Також для спрощення ми розглядаємо неорієнтовану мережу. Таким чином .

Між двома вузлами може існувати кілька ребер, але тут розглядається найпростіший випадок.

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

Очікувана кількість ребер має обчислюватися з використанням концепції конфігураційної моделі. Конфігураційна модель є рандомізованою реалізацією певної мережі. Нехай задано мережу з вузлами, де кожен вузол має степінь ​. У конфігураційній моделі кожне ребро розділяється на дві половини, після чого кожна половина ребра, яка називається заглушкою, випадковим чином з’єднується з будь-якою іншою заглушкою в мережі. При цьому допускається утворення петель (які виникають, коли заглушка з’єднується з іншою заглушкою того самого вузла) та множинних ребер між одними й тими самими парами вузлів. Таким чином, хоча розподіл степенів вузлів початкового графа залишається незмінним, конфігураційна модель призводить до повністю випадкової мережі.

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

Давайте розглянемо кожен із заготовки вузла та створити пов'язані змінні індикатора для них, , з якщо -й заглушка випадково підключається до одного з заготовки вузла у цьому конкретному випадковому графі. Якщо ні, то З моменту -й заглушка вузла може підключитися до будь-якого з решта заглушок з однаковою ймовірністю (при цьому – кількість ребер у вихідному графі), а оскільки є заглушки, до яких він може підключитися, пов'язані з вузлом , очевидно

Загальна кількість повних ребер між і просто , тому очікуване значення цієї величини дорівнює

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

Модульність Отже, різниця між фактичною кількістю ребер між вузлами і а очікувана кількість ребер між ними дорівнює

Підсумовування по всіх парах вузлів дає рівняння для модульності, є коректним лише для поділу мережі на дві спільноти. Ієрархічний поділ (тобто поділ на дві спільноти з подальшим поділом кожної з двох підспільнот на дві менші підспільноти з метою максимізації Q) є можливим підходом для виявлення кількох спільнот у мережі. Крім того, рівняння (3) можна узагальнити для поділу мережі на c спільнот.

де eij – частка ребер, одна з кінцевих вершин яких знаходиться в спільноті i, а інша – в спільноті j:

а ai – частка кінців ребер, приєднаних до вершин у спільноті i:

Приклад виявлення кількох спільнот Ми розглядаємо неорієнтовану мережу з 10 вузлами та 12 ребрами та наступною матрицею суміжності.

Ідентифікатор вузла 1 2 3 4 5 6 7 8 9 10 1 0 1 1 0 0 0 0 0 0 1 2 1 0 1 0 0 0 0 0 0 0 3 1 1 0 0 0 0 0 0 0 0 4 0 0 0 0 1 1 0 0 0 1 5 0 0 0 1 0 1 0 0 0 0 6 0 0 0 1 1 0 0 0 0 0 7 0 0 0 0 0 0 0 1 1 1 8 0 0 0 0 0 0 1 0 1 0 9 0 0 0 0 0 0 1 1 0 0 10 1 0 0 1 0 0 1 0 0 0 Спільноти на графіку представлені червоними, зеленими та синіми кластерами вузлів на рис. 1. Оптимальні розподіли спільнот зображені на рис. 2.

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

і отже

де — (неквадратна) матриця з елементами і – це так звана матриця модульності, яка має елементи

Усі рядки та стовпці матриці модульності в сумі дорівнюють нулю, що означає, що модульність нерозділеної мережі також завжди .

Для мереж, поділених лише на дві спільноти, можна альтернативно визначити , щоб позначити спільноту, до якої належить вузол , що приводить до:

де — вектор-стовпець з елементами .

Ця функція має таку ж форму, як і гамільтоніан спінового скла Ізінга, зв'язок, який використовувався для створення простих комп'ютерних алгоритмів, наприклад, з використанням імітованого відпалу, для максимізації модульності. Загальна форма модульності для довільної кількості спільнот еквівалентна спіновому склу Поттса, і для цього випадку також можна розробити подібні алгоритми.

Перенавчання Хоча метод максимізації модульності ґрунтується на оцінюванні відхилення від нульової моделі, це відхилення не обчислюється статистично узгодженим способом Унаслідок цього відомо, що метод виявляє спільноти з високими значеннями модульності навіть у власній нульовій моделі(конфігураційній моделі), яка за визначенням не може мати статистично значущої структури. Тому цей метод не може бути використаний для надійного виявлення статистично значущої структури спільнот в емпіричних мережах.

Межа роздільної здатності Модульність порівнює кількість ребер усередині кластера з очікуваною кількістю ребер, які могли б існувати в цьому кластері, якби мережа була випадковою мережею з такою самою кількістю вузлів, у якій кожен вузол зберігає свій степінь, але ребра в іншому випадку приєднані випадковим чином. Ця випадкова нульова модель неявно припускає, що кожен вузол може бути з’єднаний із будь-яким іншим вузлом мережі. Однак таке припущення є необґрунтованим для дуже великих мереж, оскільки область взаємодії вузла охоплює лише невелику частину мережі, ігноруючи більшу її частину. Крім того, це призводить до того, що очікувана кількість ребер між двома групами вузлів зменшується зі збільшенням розміру мережі.

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

З цієї причини оптимізація модульності у великих мережах не здатна виявляти малі спільноти, навіть якщо вони добре визначені. Це обмеження є неминучим для таких методів, як оптимізація модульності, які ґрунтуються на глобальній нульовій моделі.

Методи багатороздільної здатності Існує два основні підходи, які намагаються вирішити проблему обмеження роздільної здатності в контексті модульності: додавання опору r до кожного вузла у формі самоциклу, що збільшує (r > 0) або зменшує (r < 0) небажання вузлів утворювати спільноти; або додавання параметра γ > 0 перед нульовим членом у визначенні модульності, який контролює відносну важливість між внутрішніми зв'язками спільнот та нульовою моделлю.

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

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

Оригінальна реалізація багаторівневого методу Лувена. Лейденський алгоритм, який додатково уникає незв'язаних спільнот. Алгоритм кластеризації графів Відня (VieClus) – паралельний меметичний алгоритм.

Див. також

Складна мережа Структура громади Теорія перколяції

Посилання