Modularidad (redes)

La modularidad es una medida de la estructura de redes o grafos que cuantifica la fuerza de división de una red en módulos (también llamados grupos, clústeres o comunidades). Las redes con alta modularidad presentan conexiones densas entre los nodos dentro de los módulos, pero conexiones dispersas entre nodos de diferentes módulos. La modularidad se utiliza frecuentemente en métodos de optimización para detectar la estructura de comunidades en redes. Las redes biológicas, incluidos los cerebros animales, exhiben un alto grado de modularidad. Sin embargo, la maximización de la modularidad no es estadísticamente consistente y encuentra comunidades en su propio modelo nulo, es decir, en grafos completamente aleatorios; por lo tanto, no puede utilizarse para encontrar estructuras de comunidades estadísticamente significativas en redes empíricas. Además, se ha demostrado que la modularidad tiene un límite de resolución y, por consiguiente, no puede detectar comunidades pequeñas.

Muchos problemas científicamente importantes pueden representarse y estudiarse empíricamente mediante redes. Por ejemplo, los patrones biológicos y sociales, la World Wide Web, las redes metabólicas, las redes tróficas, las redes neuronales y las redes patológicas son problemas del mundo real que pueden representarse matemáticamente y estudiarse topológicamente para revelar algunas características estructurales inesperadas. ^{[ 1 ]} La mayoría de estas redes poseen una cierta estructura de comunidad que tiene una importancia sustancial para comprender la dinámica de la red. Por ejemplo, una comunidad social estrechamente conectada implicará una tasa de transmisión de información o rumores más rápida entre sus miembros que una comunidad poco conectada. Así, si una red se representa mediante una serie de nodos individuales conectados por enlaces que significan un cierto grado de interacción entre los nodos, las comunidades se definen como grupos de nodos densamente interconectados que están escasamente conectados con el resto de la red. Por lo tanto, puede ser imperativo identificar las comunidades en las redes, ya que las comunidades pueden tener propiedades bastante diferentes, como el grado del nodo, el coeficiente de agrupamiento, la intermediación, la centralidad, ^{[ 2 ]} etc., de las de la red promedio. La modularidad es una de esas medidas que, al maximizarse, da lugar a la aparición de comunidades en una red determinada.

La modularidad es la fracción de aristas que caen dentro de los grupos dados menos la fracción esperada si las aristas se distribuyeran al azar. El valor de la modularidad para grafos no ponderados y no dirigidos se encuentra en el rango${\displaystyle [-1/2,1]}$[ ^{3 ]} Es positivo si el número de aristas dentro de los grupos excede el número esperado por azar. Para una división dada de los vértices de la red en algunos módulos, la modularidad refleja la concentración de aristas dentro de los módulos en comparación con la distribución aleatoria de enlaces entre todos los nodos, independientemente de los módulos ^.

Existen diferentes métodos para calcular la modularidad. ^{[ 1 ]} En la versión más común del concepto, la aleatorización de las aristas se realiza de manera que se preserve el grado de cada vértice. Consideremos un grafo con${\displaystyle n}$nodos y${\displaystyle m}$enlaces ( aristas ) de tal manera que el grafo pueda dividirse en dos comunidades utilizando una variable de pertenencia.${\displaystyle s}$. Si un nodo${\displaystyle v}$pertenece a la comunidad 1,${\displaystyle s_{v}=1}$, o si${\displaystyle v}$pertenece a la comunidad 2,${\displaystyle s_{v}=-1}$Sea la matriz de adyacencia de la red representada por${\displaystyle A}$, dónde${\displaystyle A_{vw}=0}$significa que no hay arista (no hay interacción) entre los nodos${\displaystyle v}$y${\displaystyle w}$y${\displaystyle A_{vw}=1}$significa que hay una arista entre los dos. Además, para simplificar, consideramos una red no dirigida. Por lo tanto${\displaystyle A_{vw}=A_{wv}}$(Pueden existir múltiples aristas entre dos nodos, pero aquí analizamos el caso más simple).

Modularidad${\displaystyle Q}$se define entonces como la fracción de aristas que caen dentro del grupo 1 o 2, menos el número esperado de aristas dentro de los grupos 1 y 2 para un grafo aleatorio con la misma distribución de grados de nodos que la red dada.

El número esperado de aristas se calculará utilizando el concepto de modelo de configuración . ^{[ 4 ]} El modelo de configuración es una realización aleatoria de una red particular. Dada una red con${\displaystyle n}$nodos, donde cada nodo${\displaystyle v}$tiene un grado de nodo${\displaystyle k_{v}}$El modelo de configuración divide cada arista en dos mitades, y luego cada mitad, denominada segmento , se reconecta aleatoriamente con cualquier otro segmento de la red, permitiendo incluso bucles (que ocurren cuando un segmento se reconecta con otro segmento del mismo nodo) y aristas múltiples entre los mismos dos nodos. Por lo tanto, aunque la distribución del grado de los nodos del grafo permanece intacta, el modelo de configuración da como resultado una red completamente aleatoria.

Ahora consideremos dos nodos${\displaystyle v}$y${\displaystyle w}$, con grados de nodo${\displaystyle k_{v}}$y${\displaystyle k_{w}}$respectivamente, a partir de una red reconectada aleatoriamente como se describió anteriormente. Calculamos el número esperado de aristas completas entre estos nodos.

Consideremos cada uno de los${\displaystyle k_{v}}$fragmentos de nodo${\displaystyle v}$y crear variables indicadoras asociadas${\displaystyle I_{i}^{(v,w)}}$para ellos,${\displaystyle i=1,\ldots ,k_{v}}$, con${\displaystyle I_{i}^{(v,w)}=1}$si el${\displaystyle i}$El stub -th resulta estar conectado a uno de los${\displaystyle k_{w}}$fragmentos de nodo${\displaystyle w}$en este grafo aleatorio en particular. Si no es así, entonces${\displaystyle I_{i}^{(v,w)}=0}$. Desde el${\displaystyle i}$-º stub del nodo${\displaystyle v}$puede conectarse a cualquiera de los${\displaystyle 2m-1}$restos con igual probabilidad (mientras${\displaystyle m}$es el número de aristas en el grafo original), y dado que hay${\displaystyle k_{w}}$stubs a los que puede conectarse asociado con el nodo${\displaystyle w}$, evidentemente

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

El número total de aristas completas${\displaystyle J_{vw}}$entre${\displaystyle v}$y${\displaystyle w}$es solo${\displaystyle J_{vw}=\sum _ {i=1}^{k_{v}}I_{i}^{(v,w)}}$, por lo tanto, el valor esperado de esta cantidad es

${\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}}}$

Muchos textos hacen entonces las siguientes aproximaciones, para redes aleatorias con un gran número de aristas. Cuando${\displaystyle m}$es grande, eliminan la resta de${\displaystyle 1}$en el denominador anterior y simplemente use la expresión aproximada${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$para el número esperado de aristas entre dos nodos. Además, en una red aleatoria grande, el número de bucles propios y aristas múltiples es infinitesimalmente pequeño. ^{[ 5 ]} Ignorar los bucles propios y las aristas múltiples permite suponer que hay como máximo una arista entre cualquier par de nodos. En ese caso,${\displaystyle J_{vw}}$se convierte en una variable indicadora binaria, por lo que su valor esperado es también la probabilidad de que sea igual a${\displaystyle 1}$, lo que significa que se puede aproximar la probabilidad de que exista una arista entre nodos${\displaystyle v}$y${\displaystyle w}$como${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$.

Por lo tanto, la diferencia entre el número real de aristas entre nodos${\displaystyle v}$y${\displaystyle w}$y el número esperado de aristas entre ellos es

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

La suma sobre todos los pares de nodos da como resultado la ecuación de modularidad,${\displaystyle Q}$. ^{[ 1 ]}

La ecuación 3 es válida solo para la partición en dos comunidades. La partición jerárquica (es decir, la partición en dos comunidades, y luego la partición de estas dos subcomunidades en dos subcomunidades más pequeñas para maximizar Q ) es un posible enfoque para identificar múltiples comunidades en una red. Además, (3) puede generalizarse para la partición de una red en c comunidades. ^{[ 6 ]}

donde e _ij es la fracción de aristas con un vértice extremo en la comunidad i y el otro en la comunidad j :

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

y a _i es la fracción de extremos de aristas que están unidos a vértices en la comunidad i :

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

Consideramos una red no dirigida con 10 nodos y 12 aristas y la siguiente matriz de adyacencia.

Las comunidades en el gráfico están representadas por los grupos de nodos rojos, verdes y azules en la Figura 1. Las particiones óptimas de la comunidad se muestran en la Figura 2.

Una formulación alternativa de la modularidad, útil particularmente en algoritmos de optimización espectral, es la siguiente. ^{[ 1 ]} Definir${\displaystyle S_{vr}}$ser${\displaystyle 1}$si vértice${\displaystyle v}$pertenece al grupo${\displaystyle r}$y${\displaystyle 0}$De lo contrario. Entonces

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

y por lo tanto

${\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} ),}$

dónde${\displaystyle S}$es la matriz (no cuadrada) que tiene elementos${\displaystyle S_{v}}$y${\displaystyle B}$es la llamada matriz de modularidad, que tiene elementos

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

Todas las filas y columnas de la matriz de modularidad suman cero, lo que significa que la modularidad de una red no dividida también es siempre cero.${\displaystyle 0}$.

Para redes divididas en solo dos comunidades, se puede definir alternativamente${\displaystyle s_{v}=\pm 1}$para indicar la comunidad a la que pertenece el nodo${\displaystyle v}$pertenece, lo que luego lleva a

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

dónde${\displaystyle s}$es el vector columna con elementos${\displaystyle s_{v}}$. ^{[ 1 ]}

Esta función tiene la misma forma que el hamiltoniano de un vidrio de espín de Ising , una conexión que se ha aprovechado para crear algoritmos informáticos sencillos, por ejemplo, mediante recocido simulado , para maximizar la modularidad. La forma general de la modularidad para un número arbitrario de comunidades es equivalente a un vidrio de espín de Potts y también se pueden desarrollar algoritmos similares para este caso. ^{[ 7 ]}

Aunque el método de maximización de la modularidad se basa en el cálculo de una desviación respecto a un modelo nulo, esta desviación no se calcula de forma estadísticamente consistente. ^{[ 8 ]} Por este motivo, el método suele encontrar comunidades con puntuaciones altas en su propio modelo nulo ^{[ 9 ]} (el modelo de configuración), que por definición no pueden ser estadísticamente significativas. Por consiguiente, el método no puede utilizarse para obtener de forma fiable una estructura de comunidad estadísticamente significativa en redes empíricas.

La modularidad compara el número de aristas dentro de un clúster con el número esperado de aristas que se encontrarían en el clúster si la red fuera aleatoria con el mismo número de nodos y donde cada nodo mantuviera su grado, pero las aristas se conectaran aleatoriamente. Este modelo nulo aleatorio asume implícitamente que cada nodo puede conectarse con cualquier otro nodo de la red. Sin embargo, esta suposición es poco razonable si la red es muy grande, ya que el horizonte de un nodo abarca una pequeña parte de la red, ignorando la mayor parte de ella. Además, esto implica que el número esperado de aristas entre dos grupos de nodos disminuye si el tamaño de la red aumenta. Por lo tanto, si una red es lo suficientemente grande, el número esperado de aristas entre dos grupos de nodos en el modelo nulo de modularidad puede ser menor que uno. Si esto sucede, una sola arista entre los dos clústeres sería interpretada por la modularidad como un signo de una fuerte correlación entre ellos, y la optimización de la modularidad llevaría a la fusión de los dos clústeres, independientemente de sus características. Así, incluso los grafos completos débilmente interconectados, que poseen la mayor densidad posible de aristas internas y representan las comunidades mejor identificables, se fusionarían mediante la optimización de la modularidad si la red fuera suficientemente grande. ^{[ 10 ]} Por esta razón, la optimización de la modularidad en redes grandes no lograría resolver comunidades pequeñas, incluso cuando están bien definidas. Este sesgo es inevitable para métodos como la optimización de la modularidad, que se basan en un modelo nulo global. ^{[ 11 ]}

Existen dos enfoques principales que intentan resolver el límite de resolución dentro del contexto de modularidad: la adición de una resistencia r a cada nodo, en forma de un bucle propio , que aumenta ( r > 0 ) o disminuye ( r < 0 ) la aversión de los nodos a formar comunidades; ^{[ 12 ]} o la adición de un parámetro γ > 0 delante del término del caso nulo en la definición de modularidad, que controla la importancia relativa entre los enlaces internos de las comunidades y el modelo nulo. ^{[ 7 ]} Al optimizar la modularidad para valores de estos parámetros en sus respectivos rangos apropiados, es posible recuperar toda la mesoescala de la red, desde la macroescala en la que todos los nodos pertenecen a la misma comunidad, hasta la microescala en la que cada nodo forma su propia comunidad, de ahí el nombre de métodos de multirresolución . Sin embargo, se ha demostrado que estos métodos tienen limitaciones cuando las comunidades son muy heterogéneas en tamaño. ^{[ 13 ]}

Existen varias herramientas de software disponibles que permiten calcular agrupaciones en grafos con buena modularidad.

• Implementación original del método multinivel de Louvain . ^{[ 14 ]}
• El algoritmo de Leiden , que además evita las comunidades no conectadas. ^{[ 15 ]}
• El algoritmo de agrupamiento de grafos de Viena (VieClus), un algoritmo memético paralelo. ^{[ 16 ]}

• Red compleja
• Estructura de la comunidad
• modelo nulo
• teoría de la percolación