Modularidad (redes)

Para otros usos, consulte Modularidad .

Ciencia de la red
Teoría
Grafico Red compleja Contagio Mundo pequeño Sin escamas Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de redes
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neural artificial Interdependiente Semántico Espacial Dependencia Flujo en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Círculo Vecindario Camino Vértice Lista  / matriz de adyacencia Lista  / matriz de incidencia Tipos Bipartito Completo Dirigido Hiper Multi Aleatorio Ponderado
MétricaAlgoritmos
Centralidad La licenciatura Motivo Agrupación Distribución de titulaciones Assortividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős – Rényi Barabási – Albert Modelo de fitness Watts – Strogatz Exponencial aleatorio (ERGM) Geométrico aleatorio (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Entropía máxima Configuración suave Benchmark LFR Dinámica Red booleana basado en agente Epidemia / SIR
LizaCategorias
Temas Software Científicos de la red Categoría: Teoría de redes Categoría: Teoría de grafos
v t mi

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

La modularidad es una medida de la estructura de redes o gráficos que mide la fuerza de la división de una red en módulos (también llamados grupos, clústeres 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 los métodos de optimización para detectar la estructura de la comunidad en las redes. Sin embargo, se ha demostrado que la modularidad sufre un límite de resolución y, por tanto, es incapaz de detectar pequeñas comunidades. Las redes biológicas, incluido el cerebro de los animales, exhiben un alto grado de modularidad.

Motivación

Muchos problemas de importancia científica 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 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 comunitaria que tiene una importancia sustancial en la construcción de un entendimiento con respecto a la dinámica de la red. Por ejemplo, una comunidad social estrechamente conectada implicará una tasa más rápida de transmisión de información o rumor entre ellos que una comunidad débilmente conectada. Por lo tanto, si una red está representada por varios 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 solo 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 la de la red media. 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 los bordes que caen dentro de los grupos dados menos la fracción esperada si los bordes se distribuyen 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 sobre la base del azar. Para una división dada de los vértices de la red en algunos módulos, la modularidad refleja la concentración de bordes 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 los bordes 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 se pueda dividir 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 y${\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}$significa que hay una ventaja entre los dos. También por simplicidad, consideramos una red no dirigida. Así . (Es importante tener en cuenta que pueden existir múltiples aristas entre dos nodos, pero aquí evaluamos el caso más simple).${\displaystyle A_{vw}=A_{wv}}$

Entonces, la modularidad se define como la fracción de bordes que caen dentro del grupo 1 o 2, menos el número esperado de bordes 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 bordes se calculará utilizando el concepto de un modelo de configuración . ^[4] El modelo de configuración es una realización aleatoria de una red en 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 medio borde, llamado stub , se vuelve a cablear aleatoriamente con cualquier otro stub en la red (excepto él mismo), incluso permitiendo auto-bucles (que ocurren cuando un stub se vuelve a cablear a otro stub 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 bordes entre nodos

Ahora consideran dos nodos v y w , con grados de nodo y , respectivamente, desde una red reconectado al azar como se describió anteriormente. Calculamos el número esperado de bordes completos entre estos nodos.${\displaystyle k_{v}}$${\displaystyle k_{w}}$

Sea el número total de stubs en la red :${\displaystyle l}$

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

( 1 )

Consideremos cada uno de los talones de nodo v y crear asociados variables indicadoras para ellos, con si el i-ésimo trozo pasa a conectarse a uno de los talones de nodo w en este gráfico al azar en particular. Si no es así, entonces . Dado que el i-ésimo stub del nodo v puede conectarse a cualquiera de los stubs restantes con la misma probabilidad, y dado que hay stubs a los que puede conectarse asociado con el nodo w , evidentemente${\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}}}$

El número total de aristas completas entre v y w es justo , por lo que el valor esperado de esta cantidad es${\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}}}$

Muchos textos luego hacen las siguientes aproximaciones, para redes aleatorias con un gran número de aristas. Cuando m es grande, eliminan la resta de 1 en el denominador anterior y simplemente usan la expresión aproximada para el número esperado de bordes entre dos nodos. Además, en una gran red aleatoria, la cantidad de bucles automáticos y múltiples bordes es extremadamente pequeña. ^[5] Ignorar los bucles propios 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 de indicador binario, por lo que su valor esperado es también la probabilidad de que es igual a 1, lo que significa que uno puede aproximar la probabilidad de que un borde existente entre nodos v y w como .${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$${\displaystyle J_{vw}}$${\displaystyle {\frac {k_{v}k_{w}}{2m}}}$

Modularidad

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

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

Sumando sobre todos los pares de nodos da la ecuación para la modularidad, . ^[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 )

Es importante notar que la ecuación. 3 es válido para dividir en dos comunidades solamente. La partición jerárquica (es decir, la partición en dos comunidades, luego las dos subcomunidades se dividieron aún más 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]

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

donde e _ij es la fracción de aristas con un vértice final en la comunidad iy 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 se adjuntan a vértices en la comunidad i :

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

Ejemplo de detección de múltiples comunidades

Consideramos una red no dirigida con 10 nodos y 12 bordes 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. Q máximo = 0,4896

ID de nodo	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

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

Formulación de matriz

Una formulación alternativa de la modularidad, útil particularmente en algoritmos de optimización espectral, es la siguiente. ^[1] Defina S _vr como 1 si el vértice v pertenece al grupo r y cero en caso contrario. Luego

${\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 S es la matriz (no cuadrada) que tiene elementos S _vr y 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 indivisa también es siempre cero.

Para las redes divididas en solo dos comunidades, se puede definir alternativamente s _v = ± 1 para indicar la comunidad a la que pertenece el nodo v , lo que luego conduce a

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

donde s es el vector columna con elementos s _v . ^[1]

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 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]

Límite de resolución

La modularidad compara el número de bordes dentro de un clúster con el número esperado de bordes que uno encontraría en el clúster si la red fuera una red aleatoria con el mismo número de nodos y donde cada nodo mantiene su grado, pero los bordes se adjuntan al azar. Este modelo nulo aleatorio asume 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 bordes entre dos grupos de nodos disminuye si aumenta el tamaño de la red. Entonces, si una red es lo suficientemente grande, el número esperado de bordes entre dos grupos de nodos en el modelo nulo de modularidad puede ser menor que uno. Si esto pasa,La modularidad interpretaría un solo borde entre los dos conglomerados como un signo de una fuerte correlación entre los dos, y la optimización de la modularidad conduciría a la fusión de los dos conglomerados, independientemente de las características de los conglomerados. Por lo tanto, incluso los gráficos completos débilmente interconectados, que tienen la mayor densidad posible de bordes internos y representan las mejores comunidades identificables, se fusionarían mediante la optimización de la modularidad si la red fuera lo suficientemente grande.y representan las mejores comunidades identificables, se fusionarían mediante la optimización de la modularidad si la red fuera lo suficientemente grande.y representan las mejores comunidades identificables, se fusionarían mediante la optimización de la modularidad si la red fuera lo suficientemente grande.^[8] Por esta razón, la optimización de la modularidad en redes grandes no resolvería las 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. ^[9]

Métodos multirresolució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 auto-bucle , que aumenta ( r> 0 ) o disminuye ( r <0 ) la aversión de los nodos a formar comunidades; ^[10] 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 vínculos 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, de ahí el nombre de métodos multirresolución . Sin embargo, se ha demostrado que estos métodos tienen limitaciones cuando las comunidades son muy heterogéneas en tamaño. ^[11]

Percolación de redes modulares

Varios autores han estudiado la teoría de la filtración en redes modulares. ^{[12] [13]}

Propagación de la epidemia en redes modulares

La propagación de la epidemia se ha estudiado recientemente en redes modulares (redes con comunidades). ^[14] Dado que una enfermedad que se propaga en un país podría convertirse en una pandemia con un potencial impacto humanitario y económico a nivel mundial, es importante desarrollar modelos para estimar la probabilidad de una pandemia mundial. Un ejemplo muy reciente es el coronavirus que se inició en China (finales de 2019) y se extendió a nivel mundial. En este artículo, ^[14] se propone un modelo para la propagación de la enfermedad en una red compleja modular estructural (que tiene comunidades) y se estudia cómo el número de nodos puente que conectan las comunidades afecta la propagación de la enfermedad y el criterio para anunciar una pandemia.

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 Louvain multinivel. ^[15]

El algoritmo de Leiden que además evita comunidades desconectadas. ^[dieciséis]

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

Ver también

• Red compleja
• Estructura de la comunidad
• Modelo nulo
• Teoría de la filtració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". The New Palgrave Encyclopedia of Economics (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 clústeres de 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 .
5. "NetworkScience" . Albert-László Barabási . Consultado el 20 de marzo de 2020 .
6. Clauset, Aaron y Newman, MEJ y Moore, Cristopher (2004). "Encontrar estructura comunitaria en redes muy grandes". Phys. 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 .  
7. Joerg Reichardt y Stefan Bornholdt (2006). "Mecánica estadística de detección de comunidades". Revisión E física . 74 (1): 016110. arXiv : cond-mat / 0603718 . Código Bibliográfico : 2006PhRvE..74a6110R . doi : 10.1103 / PhysRevE.74.016110 . PMID 16907154 . S2CID 792965 .  
8. Santo Fortunato y Marc Barthelemy (2007). "Límite de resolución en la detección de comunidades" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 104 (1): 36–41. arXiv : física / 0607100 . Código Bibliográfico : 2007PNAS..104 ... 36F . doi : 10.1073 / pnas.0605965104 . PMC 1765466 . PMID 17190818 .  
9. 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". Diario Europea de Física B . 56 (1): 41–45. arXiv : cond-mat / 0610370 . Código Bibliográfico : 2007EPJB ... 56 ... 41K . doi : 10.1140 / epjb / e2007-00088-4 . S2CID 4411525 . 
10. 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 Bibliográfico : 2008NJPh ... 10e3039A . doi : 10.1088 / 1367-2630 / 10/5/053039 . S2CID 11544197 . 
11. Andrea Lancichinetti y Santo Fortunato (2011). "Límites de la maximización de la modularidad en la detección de comunidades". Revisión E física . 84 (6): 066122. arXiv : 1107.1155 . Código Bibliográfico : 2011PhRvE..84f6122L . doi : 10.1103 / PhysRevE.84.066122 . PMID 22304170 . S2CID 16180375 .  
12. Shai, S; Kenett, DY; Kenett, YN; Fausto, M; Dobson, S; Havlin, S. (2015). "Punto de inflexión crítico que distingue dos tipos de transiciones en estructuras de redes modulares" . Phys. Rev. E . 92 (6): 062805. doi : 10.1103 / PhysRevE.92.062805 . PMID 26764742 . 
13. Dong, Gaogao; Fan, Jingfang; Shekhtman, Louis M; Shai, Saray; Du, Ruijin; Tian, ​​Lixin; Chen, Xiaosong; Stanley, H Eugene; Havlin, Shlomo (2018). "La resiliencia de las redes con estructura comunitaria se comporta como bajo un campo externo" . Actas de la Academia Nacional de Ciencias . 115 (27): 6911–6915. arXiv : 1805.01032 . doi : 10.1073 / pnas.1801588115 . PMC 6142202 . PMID 29925594 .  
14. Valdez, LD; Braunstein, LA; Havlin, S (2020). "Epidemia propagación en redes modulares: El miedo a declarar una pandemia". Phys. Rev. E . 101 (3): 032309. arXiv : 1909.09695 . doi : 10.1103 / PhysRevE.101.032309 . PMID 32289896 . S2CID 202719412 .  
15. Primera implementación del algoritmo de Louvain
16. Repositorio de algoritmos de Leiden
17. Repositorio de agrupación en clústeres de gráficos de Viena