La modularidad es una medida de la estructura de redes o grafos que mide la fuerza de la 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 dispersas entre nodos en diferentes módulos. La modularidad se utiliza a menudo en métodos de optimización para detectar la estructura de la comunidad 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, grafos completamente aleatorios, y por lo tanto no se puede utilizar para encontrar estructuras de comunidad estadísticamente significativas en redes empíricas. Además, se ha demostrado que la modularidad sufre un límite de resolución y, por lo tanto, no puede detectar comunidades pequeñas.
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 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 rumores entre ellos que una comunidad débilmente conectada. Por lo tanto, si una red está representada por 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 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.
La modularidad es la fracción de las aristas que caen dentro de los grupos dados menos la fracción esperada si las aristas se distribuyeran aleatoriamente. El valor de la modularidad para grafos no ponderados y no dirigidos se encuentra en el rango . [3] Es positiva 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 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 de preservar el grado de cada vértice. Considere un grafo con nodos y enlaces ( aristas ) de manera que el grafo se pueda dividir en dos comunidades usando una variable de pertenencia . Si un nodo pertenece a la comunidad 1, , o si pertenece a la comunidad 2, . Sea la matriz de adyacencia para la red representada por , donde significa que no hay arista (no hay interacción) entre nodos y y significa que hay una arista entre los dos. También para simplificar, consideramos una red no dirigida. Por lo tanto . (Es importante notar que pueden existir múltiples aristas entre dos nodos, pero aquí evaluamos el caso más simple).
La modularidad 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 gráfico aleatorio con la misma distribución de grados de nodo que la red dada.
El número esperado de aristas 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 particular. Dada una red con nodos, donde cada nodo tiene un grado de nodo , el modelo de configuración corta cada arista en dos mitades, y luego cada mitad de arista, llamada stub , se recablea aleatoriamente con cualquier otro stub en la red, incluso permitiendo autobucles (que ocurren cuando un stub se recablea a otro stub del mismo nodo) y múltiples aristas entre los mismos dos nodos. Por lo tanto, aunque la distribución del grado de nodo del grafo permanece intacta, el modelo de configuración da como resultado una red completamente aleatoria.
Ahora, consideremos dos nodos y , con grados de nodo y respectivamente, de una red reconectada aleatoriamente como se describió anteriormente. Calculamos la cantidad esperada de aristas completas entre estos nodos.
Consideremos cada uno de los stubs del nodo y creemos variables indicadoras asociadas para ellos, , con si el -ésimo stub se conecta a uno de los stubs del nodo en este gráfico aleatorio en particular. Si no lo hace, entonces . Dado que el -ésimo stub del nodo puede conectarse a cualquiera de los stubs restantes con igual probabilidad (mientras que es el número de aristas en el gráfico original), y dado que hay stubs a los que puede conectarse asociados con el nodo , evidentemente
El número total de aristas completas entre y es simplemente , por lo que el valor esperado de esta cantidad es
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 anterior y simplemente usan la expresión aproximada para la cantidad esperada de aristas entre dos nodos. Además, en una red aleatoria grande, la cantidad de bucles propios y aristas múltiples es extremadamente pequeña. [5] Ignorar los bucles propios y las aristas múltiples permite asumir que hay como máximo una arista 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 uno puede aproximar la probabilidad de que exista una arista entre los nodos y como .
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
Sumando todos los pares de nodos se obtiene la ecuación de modularidad, . [1]
Es importante señalar que 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 las dos subcomunidades divididas a su vez 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 la partición de una red en c comunidades. [6]
donde e ij es la fracción de aristas con un vértice final en la comunidad i y el otro en la comunidad j :
y a i es la fracción de extremos de aristas que están unidos a vértices en la comunidad i :
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] Defina si el vértice pertenece al grupo y en caso contrario. Entonces
y por lo tanto
donde es la matriz (no cuadrada) que tiene elementos y es la llamada matriz de modularidad, que tiene elementos
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 .
Para redes divididas en solo dos comunidades, se puede definir alternativamente indicar la comunidad a la que pertenece el nodo, lo que luego conduce a
donde es el vector columna con elementos . [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 explotado para crear algoritmos informáticos simples, por ejemplo, utilizando 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 está motivado por el cálculo de una desviación de un modelo nulo, esta desviación no se calcula de una manera estadísticamente consistente. [8] Debido a esto, el método encuentra notoriamente comunidades de alto puntaje 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 de comunidad estadísticamente significativa en redes empíricas.
La modularidad compara el número de aristas dentro de un grupo con el número esperado de aristas que uno encontraría en el grupo si la red fuera una red aleatoria con el mismo número de nodos y donde cada nodo mantiene su grado, pero las aristas están unidas aleatoriamente. Este modelo nulo aleatorio supone implícitamente que cada nodo puede unirse a cualquier otro nodo de la red. Sin embargo, esta suposición es irrazonable 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 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 la modularidad puede ser menor que uno. Si esto sucede, una sola arista entre los dos grupos sería interpretada por la modularidad 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 grafos completos débilmente interconectados, que tienen la mayor densidad posible de aristas internas y representan las mejores comunidades identificables, se fusionarían mediante la optimización de la modularidad si la red fuera lo 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 la 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 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 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 multiresolución . Sin embargo, se ha demostrado que estos métodos tienen limitaciones cuando las comunidades son muy heterogéneas en tamaño. [13]
Hay un par de herramientas de software disponibles que pueden calcular agrupamientos en gráficos con buena modularidad.
Implementación original del método de Louvain multinivel . [14]
El algoritmo de Leiden que además evita las comunidades no conectadas. [15]
El algoritmo Vienna Graph Clustering (VieClus), un algoritmo memético paralelo. [16]
{{cite journal}}
: CS1 maint: multiple names: authors list (link)