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

Чтобы узнать о других целях, см. Модульность .

Пример измерения и раскраски модульности на безмасштабной сети .

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

Мотивация

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

Определение

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

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

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

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

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

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

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

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

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

$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$ в знаменателе выше и просто используйте приближенное выражение ${\frac {k_{v}k_{w}}{2m}}$ для ожидаемого количества ребер между двумя узлами. Кроме того, в большой случайной сети количество петель и мультиребер исчезающе мало. Игнорирование петель и мультиребер позволяет предположить, что между любыми двумя узлами существует не более одного ребра. В этом случае $J_{vw}$ становится бинарной индикаторной переменной, поэтому ее ожидаемое значение также является вероятностью того, что она равна $1$, что означает, что можно аппроксимировать вероятность существования ребра между узлами $v$ и $w$ как ${\frac {k_{v}k_{w}}{2m}}$.

Модульность

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

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

Суммирование по всем парам узлов дает уравнение модульности: $Q$.

$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- сообщества.

$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 )

где eij _{сообществе} — доля ребер, у которых одна концевая вершина находится в сообществе i , а другая — в j :

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

и a _i — это доля концов ребер, прикрепленных к вершинам в сообществе i :

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

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

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

Рис. 1. Пример сети, соответствующей матрице смежности с 10 узлами и 12 ребрами.

Рис. 2. Разделы сети, максимизирующие Q. Максимум Q=0,4896

Идентификатор узла	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.

Формулировка матрицы

Альтернативная формулировка модульности, особенно полезная в алгоритмах спектральной оптимизации, заключается в следующем. Определять $S_{vr}$ быть $1$ если вершина $v$ принадлежит к группе $r$ и $0$ в противном случае. Затем

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

и, следовательно,

$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_{v}$ и $B$ – это так называемая матрица модульности, состоящая из элементов

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

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

Для сетей, разделенных всего на два сообщества, можно альтернативно определить $s_{v}=\pm 1$ чтобы указать сообщество, к какому узлу $v$ принадлежит, что затем приводит к

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

где $s$ вектор-столбец с элементами $s_{v}$.

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

Переоснащение

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

Предел разрешения

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

Методы мультиразрешения

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

Программные инструменты

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

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

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

Алгоритм кластеризации венских графов (VieClus), параллельный меметический алгоритм.

См. также

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