Modularidad (redes)

Medida de la estructura de la comunidad de red.

Ejemplo de medición de modularidad y coloración en una red sin escala .

La modularidad es una medida de la estructura de redes o gráficos que mide la fuerza de división de una red en módulos (también llamados grupos, clusters o comunidades). Las redes con alta modularidad tienen conexiones densas entre los nodos dentro de los módulos, pero conexiones escasas entre nodos en diferentes módulos. La modularidad se utiliza a menudo en métodos de optimización para detectar estructuras comunitarias 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, gráficos completamente aleatorios, y por lo tanto no puede usarse para encontrar estructuras comunitarias estadísticamente significativas en redes empíricas. Además, se ha demostrado que la modularidad sufre un límite de resolución y, por tanto, es incapaz de detectar comunidades pequeñas.

Motivación

Muchos problemas científicamente importantes pueden representarse y estudiarse empíricamente utilizando redes. Por ejemplo, los patrones biológicos y sociales, la World Wide Web, las redes metabólicas, las redes alimentarias, 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 comunitaria que tiene una importancia sustancial para construir una comprensión sobre 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 ellos que una comunidad poco conectada. Así, si una red está representada por un número 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 sólo 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 de 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, cuando se maximiza, conduce a la aparición de comunidades en una red determinada.

Definición

La modularidad es la fracción de las aristas que se encuentran dentro de los grupos dados menos la fracción esperada si las aristas se distribuyeran al azar. El valor de la modularidad para gráficos no ponderados y no dirigidos se encuentra en el rango . ^[3] Es positivo si el número de aristas dentro de los grupos excede el número esperado según el 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. ${\displaystyle [-1/2,1]}$

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 para preservar el grado de cada vértice. Considere un gráfico con nodos y enlaces ( bordes ) de modo que el gráfico pueda dividirse en dos comunidades utilizando una variable de pertenencia . Si un nodo pertenece a la comunidad 1, o si pertenece a la comunidad 2 ,. Deje que la matriz de adyacencia de la red esté representada por , donde significa que no hay borde (sin interacción) entre los nodos y significa que hay un borde entre los dos. También por simplicidad consideramos una red no dirigida. De este modo . (Es importante tener en cuenta que pueden existir múltiples aristas entre dos nodos, pero aquí evaluamos el caso más simple). ${\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}}$

Luego, la modularidad se define como la fracción de aristas que se encuentran dentro del grupo 1 o 2, menos el número esperado de aristas dentro de los grupos 1 y 2 para un gráfico aleatorio con la misma distribución de grados de nodo que la red dada. ${\displaystyle Q}$

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 nodos, donde cada nodo tiene un grado de nodo , el modelo de configuración corta cada borde en dos mitades, y luego cada mitad de borde, llamado trozo , se vuelve a cablear aleatoriamente con cualquier otro trozo de la red, incluso permitiendo auto-bucles. (que ocurre cuando un trozo se vuelve a cablear a otro trozo del mismo nodo) y múltiples bordes entre los mismos dos nodos. Por lo tanto, aunque la distribución de grados de nodo del gráfico permanece intacta, el modelo de configuración da como resultado una red completamente aleatoria. ${\displaystyle n}$ ${\displaystyle v}$ ${\displaystyle k_{v}}$

Número esperado de aristas entre nodos

Ahora considere dos nodos y , con grados de nodo y respectivamente, de una red recableada aleatoriamente como se describe anteriormente. Calculamos el número esperado de aristas completas entre estos nodos. ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle k_{v}}$ ${\displaystyle k_{w}}$

Consideremos cada uno de los trozos de nodo y creemos variables indicadoras asociadas para ellos, si el -ésimo trozo se conecta a uno de los trozos de nodo en este gráfico aleatorio en particular. Si no es así, entonces . Dado que el -ésimo trozo del nodo se puede conectar a cualquiera de los trozos restantes con la misma probabilidad (mientras que es el número de aristas en el gráfico original), y dado que hay trozos a los que se puede conectar asociados con el nodo , evidentemente ${\displaystyle k_{v}}$ ${\displaystyle v}$ ${\displaystyle I_{i}^{(v,w)}}$ ${\displaystyle i=1,\ldots ,k_{v}}$ ${\displaystyle I_{i}^{(v,w)}=1}$ ${\displaystyle i}$ ${\displaystyle k_{w}}$ ${\displaystyle w}$ ${\displaystyle I_{i}^{(v,w)}=0}$ ${\displaystyle i}$ ${\displaystyle v}$ ${\displaystyle 2m-1}$ ${\displaystyle m}$ ${\displaystyle k_{w}}$ ${\displaystyle w}$

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

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

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

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

Modularidad

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

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

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

Es importante señalar que la Ec. 3 es válido sólo para la partición en dos comunidades. La partición jerárquica (es decir, dividir en dos comunidades, luego las dos subcomunidades se dividen en dos subcomunidades más pequeñas solo para maximizar Q ) es un enfoque posible para identificar múltiples comunidades en una red. Además, (3) se puede generalizar para dividir una red en comunidades c . ^[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}}$

Ejemplo de detección de comunidades múltiples

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

Fig 1. Red de muestra correspondiente a la matriz de Adyacencia con 10 nodos, 12 aristas.

Fig 2. Particiones de red que maximizan Q. Máximo Q=0,4896

Las comunidades en el gráfico están representadas por los grupos de nodos rojo, verde y azul en la Fig. 1. Las particiones comunitarias óptimas se representan en la Fig. 2.

Formulación matricial

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

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

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

${\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 indivisa también es siempre . ${\displaystyle 0}$

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

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

¿Dónde está el vector columna con elementos ? ^[1] ${\displaystyle s}$ ${\displaystyle s_{v}}$

Esta función tiene la misma forma que el hamiltoniano de un vidrio giratorio de Ising , una conexión que se ha aprovechado para crear algoritmos informáticos simples, por ejemplo utilizando recocido simulado , para maximizar la modularidad. La forma general de la modularidad para números arbitrarios de comunidades es equivalente a un vaso giratorio de Potts y también se pueden desarrollar algoritmos similares para este caso. ^[7]

Sobreajuste

Aunque el método de maximización de la modularidad está motivado por calcular una desviación de un modelo nulo, esta desviación no se calcula de manera estadísticamente consistente. ^[8] Debido a esto, el método encuentra notoriamente comunidades de alta puntuación en su propio modelo nulo ^[9] (el modelo de configuración), que por definición no puede ser estadísticamente significativo. Debido a esto, el método no se puede utilizar para obtener de manera confiable una estructura comunitaria estadísticamente significativa en redes empíricas.

Límite de resolución

La modularidad compara la cantidad de aristas dentro de un clúster con la cantidad esperada de aristas que se encontrarían en el clúster si la red fuera una red aleatoria con la misma cantidad de nodos y donde cada nodo mantiene su grado, pero, por lo demás, las aristas están unidas aleatoriamente. Este modelo nulo aleatorio supone implícitamente que cada nodo puede conectarse a cualquier otro nodo de la red. Sin embargo, esta suposición no es razonable si la red es muy grande, ya que el horizonte de un nodo incluye una pequeña parte de la red, ignorando la mayor parte. 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. Entonces, 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, la modularidad interpretaría un solo borde entre los dos grupos como un signo de una fuerte correlación entre los dos grupos, y la optimización de la modularidad conduciría a la fusión de los dos grupos, independientemente de las características de los grupos. Por lo tanto, incluso los gráficos completos débilmente interconectados, que tienen la mayor densidad posible de bordes internos y representan las comunidades mejor identificables, se fusionarían mediante optimización de modularidad si la red fuera lo suficientemente grande. ^[10] Por esta razón, optimizar 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]

Métodos multiresolución

Hay 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 autobucle , 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 de 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] Optimizando la modularidad para los 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. propia comunidad, de ahí el nombre de métodos multiresolución . Sin embargo, se ha demostrado que estos métodos tienen limitaciones cuando las comunidades son muy heterogéneas en tamaño. ^[13]

Herramientas de software

Hay un par de herramientas de software disponibles que pueden calcular agrupaciones en gráficos con buena modularidad.

Implementación original del método de Lovaina multinivel . ^[14]

El algoritmo de Leiden que además evita comunidades desconectadas. ^[15]

El algoritmo Vienna Graph Clustering (VieClus), un algoritmo memético paralelo. ^[dieciséis]

Ver también

• Red compleja
• Estructura comunitaria
• modelo nulo
• Teoría de la percolación

Referencias

1. Newman, MEJ (2006). "Modularidad y estructura comunitaria en redes". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 103 (23): 8577–8696. arXiv : física/0602124 . Código bibliográfico : 2006PNAS..103.8577N. doi : 10.1073/pnas.0601602103 . PMC  1482622 . PMID  16723398.
2. Newman, MEJ (2007). Palgrave Macmillan, Basingstoke (ed.). "Matemáticas de redes". La enciclopedia de economía New Palgrave (2 ed.).
3. Brandes, U .; Delling, D.; Gaertler, M.; Gorke, R.; Hoefer, M.; Nikoloski, Z.; Wagner, D. (febrero de 2008). "Sobre la agrupación en modularidad". Transacciones IEEE sobre conocimiento e ingeniería de datos . 20 (2): 172–188. doi :10.1109/TKDE.2007.190689. S2CID  150684.
4. van der Hofstad, Remco (2013). "Capítulo 7" (PDF) . Gráficos aleatorios y redes complejas . Archivado (PDF) desde el original el 18 de diciembre de 2013 . Consultado el 8 de diciembre de 2013 .
5. "Ciencia de la red". Albert-László Barabási. Archivado desde el original el 5 de marzo de 2020 . Consultado el 20 de marzo de 2020 .
6. Clauset, Aaron y Newman, MEJ y Moore, Cristopher (2004). "Encontrar estructura comunitaria en redes muy grandes". Física. Rev. E. 70 (6): 066111. arXiv : cond-mat/0408187 . Código bibliográfico : 2004PhRvE..70f6111C. doi : 10.1103/PhysRevE.70.066111. PMID  15697438. S2CID  8977721.{{cite journal}}: CS1 maint: multiple names: authors list (link)
7. Joerg Reichardt y Stefan Bornholdt (2006). "Mecánica estadística de detección comunitaria". Revisión física E. 74 (1): 016110. arXiv : cond-mat/0603718 . Código bibliográfico : 2006PhRvE..74a6110R. doi : 10.1103/PhysRevE.74.016110. PMID  16907154. S2CID  792965.
8. Peixoto, Tiago P. (2021). "Detección comunitaria descriptiva versus inferencial: trampas, mitos y verdades a medias". arXiv : 2112.00183 .
9. Guimerá, Roger; Sales-Pardo, Marta (19 de agosto de 2004), "Modularidad a partir de fluctuaciones en gráficos aleatorios y redes complejas", Physical Review , 70 (2): 025101, arXiv : cond-mat/0403660 , Bibcode :2004PhRvE..70b5101G, doi :10.1103/PhysRevE.70.025101, PMC 2441765 , PMID  15447530 
10. Santo Fortunato y Marc Barthelemy (2007). "Límite de resolución en detección comunitaria". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 104 (1): 36–41. arXiv : física/0607100 . Código Bib : 2007PNAS..104...36F. doi : 10.1073/pnas.0605965104 . PMC 1765466 . PMID  17190818. 
11. JM Kumpula; J. Saramäki; K. Kaski y J. Kertész (2007). "Resolución limitada en la detección de comunidades de redes complejas con el enfoque del modelo de Potts". Revista física europea B. 56 (1): 41–45. arXiv : cond-mat/0610370 . Código Bib : 2007EPJB...56...41K. doi :10.1140/epjb/e2007-00088-4. S2CID  4411525.
12. Alex Arenas, Alberto Fernández y Sergio Gómez (2008). "Análisis de la estructura de redes complejas a diferentes niveles de resolución". Nueva Revista de Física . 10 (5): 053039. arXiv : física/0703218 . Código Bib : 2008NJPh...10e3039A. doi :10.1088/1367-2630/10/5/053039. S2CID  11544197.
13. Andrea Lancichinetti y Santo Fortunato (2011). "Límites de maximización de la modularidad en la detección comunitaria". Revisión física E. 84 (6): 066122. arXiv : 1107.1155 . Código bibliográfico : 2011PhRvE..84f6122L. doi : 10.1103/PhysRevE.84.066122. PMID  22304170. S2CID  16180375.
14. Primera implementación del algoritmo de Louvain, archivado desde el original el 17 de marzo de 2021 , consultado el 30 de noviembre de 2020
15. Repositorio de algoritmos de Leiden, 15 de diciembre de 2021, archivado desde el original el 26 de noviembre de 2020 , consultado el 30 de noviembre de 2020
16. Repositorio de agrupación de gráficos de Viena, 13 de abril de 2021, archivado desde el original el 21 de octubre de 2020 , consultado el 30 de noviembre de 2020