Модульность (сети)

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Составная часть Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список  / матрица смежности Список  / матрица заболеваемости Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
МетрикиАлгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес-модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия / SIR
СпискиКатегории
Темы Программное обеспечение Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

Модульность - это одна из мер структуры сетей или графов, которая измеряет силу разделения сети на модули (также называемые группами, кластерами или сообществами). Сети с высокой модульностью имеют плотные связи между узлами в модулях, но редкие связи между узлами в разных модулях. Модульность часто используется в методах оптимизации для определения структуры сообщества в сетях. Однако было показано, что модульность страдает пределом разрешения и, следовательно, не может обнаруживать небольшие сообщества. Биологические сети, включая мозг животных, обладают высокой степенью модульности.

Мотивация [ править ]

Многие важные с научной точки зрения проблемы могут быть представлены и эмпирически изучены с использованием сетей. Например, биологические и социальные модели, Всемирная паутина, метаболические сети, пищевые сети, нейронные сети и патологические сети - это проблемы реального мира, которые можно математически представить и топологически изучить, чтобы выявить некоторые неожиданные структурные особенности. ^[1]Большинство этих сетей обладают определенной структурой сообщества, которая имеет существенное значение для понимания динамики сети. Например, тесно связанное социальное сообщество подразумевает более высокую скорость передачи информации или слухов между ними, чем слабо связанное сообщество. Таким образом, если сеть представлена ​​рядом отдельных узлов, соединенных связями, которые обозначают определенную степень взаимодействия между узлами, сообщества определяются как группы плотно связанных узлов, которые лишь редко связаны с остальной частью сети. Следовательно, может быть необходимо идентифицировать сообщества в сетях, поскольку сообщества могут иметь совершенно разные свойства, такие как степень узла, коэффициент кластеризации, промежуточность, центральность. ^[2]и т. д., от средней сети. Модульность - одна из таких мер, которая при максимальном увеличении приводит к появлению сообществ в данной сети.

Определение [ править ]

Модульность - это доля ребер, попадающих в указанные группы, за вычетом ожидаемой доли, если ребра были распределены случайным образом. Значение модульности для невзвешенных и неориентированных графиков лежит в диапазоне . ^[3] Положительно, если количество ребер в группах превышает количество, ожидаемое на основе случайности. Для данного разделения вершин сети на несколько модулей модульность отражает концентрацию ребер внутри модулей по сравнению со случайным распределением связей между всеми узлами независимо от модулей.${\ displaystyle [-1 / 2,1]}$

Существуют разные методы расчета модульности. ^[1] В наиболее распространенной версии концепции рандомизация ребер выполняется так, чтобы сохранить степень каждой вершины. Рассмотрим граф с узлами и связями ( ребрами ), такой, что граф можно разделить на два сообщества с помощью переменной принадлежности . Если узел принадлежит сообществу 1 , или если принадлежит сообществу 2 ,. Пусть матрица смежности для сети представлена ​​как , где означает, что нет края (нет взаимодействия) между узлами и и${\displaystyle n}$ ${\displaystyle m}$${\displaystyle s}$${\displaystyle v}$${\displaystyle s_{v}=1}$${\displaystyle v}$${\displaystyle s_{v}=-1}$${\displaystyle A}$${\displaystyle A_{vw}=0}$${\displaystyle v}$${\displaystyle w}$${\displaystyle A_{vw}=1}$означает, что между ними есть грань. Также для простоты мы рассматриваем неориентированную сеть. Итак . (Важно отметить, что между двумя узлами может существовать несколько ребер, но здесь мы оцениваем простейший случай).${\displaystyle A_{vw}=A_{wv}}$

Модульность затем определяется как доля ребер, которые попадают в группу 1 или 2, за вычетом ожидаемого количества ребер в группах 1 и 2 для случайного графа с тем же распределением степеней узлов, что и данная сеть.${\displaystyle Q}$

Ожидаемое количество ребер должно быть вычислено с использованием концепции модели конфигурации . ^[4] Модель конфигурации - это рандомизированная реализация конкретной сети. Учитывая сеть с узлами, где каждый узел имеет степень узла , модель конфигурации разрезает каждое ребро на две половины, а затем каждое половинное ребро, называемое заглушкой , случайным образом переплетается с любым другим заглушкой в ​​сети (кроме себя), даже разрешение петель (которые возникают, когда заглушка перенаправляется на другую заглушку из того же узла) и множественные ребра между теми же двумя узлами. Таким образом, даже несмотря на то, что распределение степеней узлов графа остается неизменным, модель конфигурации приводит к полностью случайной сети.${\displaystyle n}$${\displaystyle v}$${\displaystyle k_{v}}$

Ожидаемое количество ребер между узлами [ править ]

Теперь рассмотрим два узла v и w со степенями узлов и соответственно из случайно перепрограммированной сети, как описано выше. Мы вычисляем ожидаемое количество полных ребер между этими узлами.${\displaystyle k_{v}}$${\displaystyle k_{w}}$

Пусть общее количество заглушек в сети будет :${\displaystyle l}$

${\displaystyle l=\sum _{u}k_{u}=2m}$

( 1 )

Давайте рассмотрим каждую из заглушек узла v и создадим для них связанные индикаторные переменные , при этом, если i-ая заглушка будет подключаться к одной из заглушек узла w в этом конкретном случайном графе. Если нет, тогда . Поскольку i-й шлейф узла v может подключаться к любому из оставшихся шлейфов с равной вероятностью, и поскольку существуют шлейфы, к которым он может подключаться, связанный с узлом w , очевидно${\displaystyle k_{v}}$${\displaystyle I_{i}^{(v,w)}}$${\displaystyle i=1,\ldots ,k_{v}}$${\displaystyle I_{i}^{(v,w)}=1}$${\displaystyle k_{w}}$${\displaystyle I_{i}^{(v,w)}=0}$${\displaystyle 2m-1}$${\displaystyle k_{w}}$

${\displaystyle p(I_{i}^{(v,w)}=1)=E[I_{i}^{(v,w)}]={\frac {k_{w}}{2m-1}}}$

Общее количество полных ребер между v и w равно , поэтому ожидаемое значение этого количества равно${\displaystyle J_{vw}}$${\displaystyle J_{vw}=\sum _{i=1}^{k_{v}}I_{i}}$

${\displaystyle E[J_{vw}]=E\left[\sum _{i=1}^{k_{v}}I_{i}^{(v,w)}\right]=\sum _{i=1}^{k_{v}}E[I_{i}^{(v,w)}]=\sum _{i=1}^{k_{v}}{\frac {k_{w}}{2m-1}}={\frac {k_{v}k_{w}}{2m-1}}}$

Затем во многих текстах делаются следующие приближения для случайных сетей с большим количеством ребер. Когда m велико, они отбрасывают вычитание 1 в знаменателе выше и просто используют приближенное выражение для ожидаемого количества ребер между двумя узлами. Кроме того, в большой случайной сети количество петель и множественных ребер исчезающе мало. ^[5] Игнорирование петель и множественных ребер позволяет предположить, что между любыми двумя узлами существует не более одного ребра. В этом случае, становится двоичной индикаторной переменной, поэтому ее ожидаемое значение также является вероятностью того, что оно равно 1, что означает, что можно приблизительно оценить вероятность наличия ребра между узлами v и w как .${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$${\displaystyle J_{vw}}$${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$

Модульность [ править ]

Следовательно, разница между фактическим количеством ребер между узлом и и ожидаемым количеством ребер между ними составляет${\displaystyle v}$${\displaystyle w}$

${\displaystyle A_{vw}-{\frac {k_{v}k_{w}}{2m}}}$

Суммирование по всем парам узлов дает уравнение модульности . ^[1]${\displaystyle Q}$

${\displaystyle Q={\frac {1}{2m}}\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]{\frac {s_{v}s_{w}+1}{2}}}$

( 3 )

Важно отметить, что уравнение. 3 годится только для разделения на два сообщества. Иерархическое разделение (т. Е. Разделение на два сообщества, затем два подсообщества, дополнительно разделенных на два меньших подсообщества только для максимизации Q ) является возможным подходом к идентификации нескольких сообществ в сети. Кроме того, (3) можно обобщить для разделения сети на c- сообщества. ^[6]

${\displaystyle Q={\frac {1}{(2m)}}\sum _{vw}\left[A_{vw}-{\frac {k_{v}k_{w}}{(2m)}}\right]\delta (c_{v},c_{w})=\sum _{i=1}^{c}(e_{ii}-a_{i}^{2})}$

( 4 )

где e _ij - доля ребер с одной конечной вершиной в сообществе i, а другая - в сообществе j :

${\displaystyle e_{ij}=\sum _{vw}{\frac {A_{vw}}{2m}}1_{v\in c_{i}}1_{w\in c_{j}}}$

и _я есть доля концов ребер, которые прикреплены к вершинам в сообществе I :

${\displaystyle a_{i}={\frac {k_{i}}{2m}}=\sum _{j}e_{ij}}$

Пример обнаружения нескольких сообществ [ править ]

Мы рассматриваем неориентированную сеть с 10 узлами и 12 ребрами и следующей матрицей смежности.

Сообщества на графике представлены кластерами узлов красного, зеленого и синего цветов на рис. 1. Оптимальные разделы сообщества изображены на рис. 2.

Формулировка матрицы [ править ]

Альтернативная формулировка модульности, особенно полезная в алгоритмах спектральной оптимизации, следующая. ^[1] Определим S _vr равным 1, если вершина v принадлежит группе r, и нулю в противном случае. потом

${\displaystyle \delta (c_{v},c_{w})=\sum _{r}S_{vr}S_{wr}}$

и поэтому

${\displaystyle Q={\frac {1}{2m}}\sum _{vw}\sum _{r}\left[A_{vw}-{\frac {k_{v}k_{w}}{2m}}\right]S_{vr}S_{wr}={\frac {1}{2m}}\mathrm {Tr} (\mathbf {S} ^{\mathrm {T} }\mathbf {BS} ),}$

где S - (неквадратная) матрица, имеющая элементы S _vr, а B - так называемая матрица модульности, которая имеет элементы

${\displaystyle B_{vw}=A_{vw}-{\frac {k_{v}k_{w}}{2m}}.}$

Сумма всех строк и столбцов матрицы модульности равна нулю, что означает, что модульность неразделенной сети также всегда равна нулю.

Для сетей, разделенных всего на два сообщества, можно в качестве альтернативы определить s _v = ± 1, чтобы указать сообщество, к которому принадлежит узел v , что затем приводит к

${\displaystyle Q={1 \over 4m}\sum _{vw}B_{vw}s_{v}s_{w}={1 \over 4m}\mathbf {s} ^{\mathrm {T} }\mathbf {Bs} ,}$

где s - вектор-столбец с элементами s _v . ^[1]

Эта функция имеет ту же форму, что и гамильтониан спинового стекла Изинга , соединение, которое использовалось для создания простых компьютерных алгоритмов, например, с использованием имитационного отжига , чтобы максимизировать модульность. Общая форма модульности для произвольного числа сообществ эквивалентна спин-стеклу Поттса, и аналогичные алгоритмы могут быть разработаны и для этого случая. ^[7]

Предел разрешения [ править ]

Модульность сравнивает количество ребер внутри кластера с ожидаемым количеством ребер, которое можно было бы найти в кластере, если бы сеть была случайной сетью с тем же количеством узлов и где каждый узел сохраняет свою степень, но в противном случае ребра присоединяются случайным образом. Эта случайная нулевая модель неявно предполагает, что каждый узел может быть присоединен к любому другому узлу сети. Однако это предположение неразумно, если сеть очень большая, поскольку горизонт узла включает небольшую часть сети, игнорируя большую ее часть. Более того, это означает, что ожидаемое количество ребер между двумя группами узлов уменьшается, если размер сети увеличивается. Итак, если сеть достаточно велика, ожидаемое количество ребер между двумя группами узлов в нулевой модели модульности может быть меньше единицы. Если это произойдет,единственное ребро между двумя кластерами будет интерпретироваться модульностью как признак сильной корреляции между двумя кластерами, а оптимизация модульности приведет к слиянию двух кластеров, независимо от характеристик кластеров. Таким образом, даже слабо взаимосвязанные полные графы, которые имеют максимально возможную плотность внутренних ребер и представляют наилучшие идентифицируемые сообщества, были бы объединены путем оптимизации модульности, если бы сеть была достаточно большой.и представляли бы лучшие идентифицируемые сообщества, были бы объединены путем оптимизации модульности, если бы сеть была достаточно большой.и представляли бы лучшие идентифицируемые сообщества, были бы объединены путем оптимизации модульности, если бы сеть была достаточно большой.^[8] По этой причине оптимизация модульности в больших сетях не решит проблемы небольших сообществ, даже если они четко определены. Это смещение неизбежно для таких методов, как оптимизация модульности, которые полагаются на глобальную нулевую модель. ^[9]

Методы с несколькими разрешениями [ править ]

Существует два основных подхода, которые пытаются решить предел разрешения в контексте модульности: добавление сопротивления r к каждому узлу в виде петли , которое увеличивается ( r> 0 ) или уменьшается ( r <0 ). отвращение узлов к формированию сообществ; ^[10] или добавление параметра γ> 0 перед термином нулевого регистра в определении модульности, который контролирует относительную важность между внутренними связями сообществ и нулевой моделью. ^[7]Оптимизируя модульность для значений этих параметров в соответствующих диапазонах, можно восстановить весь мезоуровень сети, от макромасштаба, в котором все узлы принадлежат к одному сообществу, до микромасштаба, в котором каждый узел формирует свое собственное сообщество, отсюда и название методов с множественным разрешением . Однако было показано, что эти методы имеют ограничения, когда сообщества очень разнородны по размеру. ^[11]

Перколяция модульных сетей [ править ]

Теория перколяции на модульных сетях изучалась несколькими авторами. ^{[12] [13]}

Распространение эпидемии в модульных сетях [ править ]

Распространение эпидемии недавно изучалось в модульных сетях (сетях с сообществами). ^[14] Поскольку распространение болезни в одной стране может стать пандемией с потенциальными гуманитарными и экономическими последствиями во всем мире, важно разработать модели для оценки вероятности всемирной пандемии. Самый свежий пример - коронавирус, который возник в Китае (конец 2019 года) и распространился по всему миру. В этой статье ^[14] предлагается модель распространения болезни в структурно-модульной сложной сети (имеющей сообщества) и изучается, как количество узловых мостов, соединяющих сообщества, влияет на распространение болезни и критерий объявления пандемии.

Программные инструменты [ править ]

Есть несколько доступных программных инструментов, которые могут вычислять кластеризацию в графах с хорошей модульностью.

Оригинальная реализация многоуровневого метода Лувена. ^[15]

Алгоритм Лейдена, который дополнительно избегает несвязанных сообществ. ^[16]

Алгоритм Венской графической кластеризации (VieClus), параллельный меметический алгоритм. ^[17]

См. Также [ править ]

• Комплексная сеть
• Структура сообщества
• Нулевая модель
• Теория перколяции

Ссылки [ править ]