Skip to main content
LibreTexts - Ukrayinska

17.7: Структура спільноти та модульність

  1. Last updated
  2. Save as PDF
  • Page ID
    67577

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

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

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

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

    На малюнку 17.7.1 показаний приклад спільнот в мережі.

    Існують буквально десятки різних способів визначення та виявлення спільнот у мережі. Але тут ми обговоримо лише один метод, який зараз широко використовується дослідниками мережевої науки: метод Лувена, запропонований Вінсентом Блонделем та співавт. у 2008 році [77]. Це дуже швидкий, ефективний евристичний алгоритм, який максимізує модульність непереливної структури спільноти через ітераційний, ієрархічний процес оптимізації.

    Рис. 17.13 PNG

    Модульність заданого набору спільнот в мережі визначається наступним чином [78]:

    \[Q= \frac{|E_{in}|- \langle{E_{in} \rangle}}{|E|} \label{(17.35)} \]

    Ось кількість ребер,\(|E|\) це кількість ребер всередині спільноти (тобто тих, які не перетинають кордонів між громадами), і\(\langle{|E_{in}|} \rangle\) очікувана кількість ребер всередині спільноти, якщо топологія була чисто випадковою.\(|E_{in}|\) Віднімання\(\langle{|E_{in}|} \rangle\) на чисельнику штрафує тривіальну структуру спільноти, наприклад, розглядати всю мережу єдиною спільнотою, яка тривіально максимізує\({|E_{in}|}\).

    Метод Лувена знаходить оптимальну структуру спільноти, яка максимізує модульність на наступних кроках:

    1. Спочатку кожен вузол присвоюється власній спільноті, де сам вузол є єдиним членом спільноти. Тому кількість початкових спільнот дорівнює кількості вузлів.
    2. Кожен вузол розглядає кожного зі своїх сусідів і оцінює, чи збільшить приєднання до сусідської спільноти модульність структури спільноти. Оцінивши всіх сусідів, він приєднається до спільноти сусіда, яка досягає максимального збільшення модульності (лише якщо зміна позитивна; інакше вузол залишиться у власній спільноті). Це буде неодноразово застосовуватися для всіх вузлів, поки більше не буде досягнуто позитивного посилення.
    3. Результат кроку 2 перетворюється на нову мета-мережу на більш високому рівні, шляхом агрегування вузлів, які належали одній спільноті, в мета-вузол, представляючи ребра, які існували всередині кожної спільноти, як вагу самоциклу, прикріпленого до мета-вузла, і представляючи ребра, що існували між спільноти як ваги мета-ребер, які з'єднують мета-вузли.
    4. Вищезазначені два кроки повторюються до тих пір, поки більше не буде можливим поліпшення модульності.

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

    На жаль, NetworkX не має цього методу Лувена як вбудованої функції, але його реалізація Python була розроблена і вільно випущена Томасом Айно, який доступний з perso.crans.org/aynaud/communities/. Як тільки ви встановите його, новий модуль спільноти стає доступним у Python. Ось приклад:

    Код 17.22.PNG

    Тут тестуються дві важливі функції в модулі спільноти. Перший - best_partition, який генерує структуру спільноти за допомогою методу Лувена. Результат задається у вигляді словника, де ключі та значення є ідентифікаторами вузлів та ідентифікаторами спільноти відповідно. Друга функція, показана вище, - модульність, яка отримує структуру спільноти та мережу та повертає значення модульності, досягнуте даними спільнотами.

    Вправа\(\PageIndex{1}\)

    Візуалізуйте структуру спільноти на графіку Карате Клубу, використовуючи ідентифікатори спільноти як кольори вузлів.

    Вправа\(\PageIndex{2}\)

    Імпортуйте великий набір мережевих даних на ваш вибір з веб-сайту мережевих даних Марка Ньюмана: http://www-personal.umich.edu/~mejn/netdata/ Визначте його структуру спільноти за допомогою методу Лувена та візуалізуйте її, якщо це можливо.

    Вправа\(\PageIndex{3}\)

    Виконайте швидкий пошук літератури в Інтернеті для інших алгоритмів виявлення спільноти (наприклад, метод Гірвана-Ньюмана, метод перколяції\(k\) -кліка, метод випадкової ходьби тощо). Виберіть один з них і прочитайте літературу, щоб дізнатися, як це працює. Якщо програмне забезпечення є, спробуйте його самостійно на графіку Карате Клубу або в будь-якій іншій мережі і подивіться, чим результат відрізняється від результату методу Лувена.