Modularidad (redes)

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar

La modularidad es una medida de la estructura de las 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 los nodos en diferentes módulos. La modularidad se usa 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, incluidos los cerebros de animales, exhiben un alto grado de modularidad.

Motivación

Muchos problemas científicamente importantes se pueden representar y estudiar empíricamente usando 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.La mayoría de estas redes poseen una cierta estructura comunitaria que tiene una importancia sustancial en la construcción de un entendimiento sobre 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. 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 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 y la centralidad.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 distribuyeran al azar. El valor de la modularidad para gráficos no ponderados y no dirigidos se encuentra en el rango { estilo de visualización [-1 / 2,1]}. Es positivo si el número de aristas dentro de los grupos excede el número esperado en base al 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.

Existen diferentes métodos para calcular la modularidad. 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 nortenodos y metroenlaces (bordes) de modo que el gráfico se pueda dividir en dos comunidades utilizando una variable de pertenencia s. Si un nodo vpertenece a la comunidad 1, s_{v}=1o si vpertenece a la comunidad 2, s_{v}=-1. Deje que la matriz de adyacencia para la red esté representada por A, donde {displaystyle A_{vw}=0}significa que no hay borde (sin interacción) entre los nodos vy significa wque A _ {{vw}} = 1hay un borde entre los dos. También por simplicidad consideramos una red no dirigida. De este modoA_{{vw}}=A_{{wv}}. (Es importante tener en cuenta que pueden existir múltiples bordes entre dos nodos, pero aquí evaluamos el caso más simple).

La modularidad qse 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 grado de nodo que la red dada.

El número esperado de aristas se calculará utilizando el concepto de un modelo de configuración. El modelo de configuración es una realización aleatoria de una red particular. Dada una red con nortenodos, donde cada nodo vtiene un grado de nodo {displaystyle k_{v}}, 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, incluso permitiendo bucles automáticos. (que ocurre cuando un stub se vuelve a cablear a otro stub del mismo nodo) y varios 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.

Número esperado de aristas entre nodos

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

Consideremos cada uno de los {displaystyle k_{v}}stubs del nodo vy creemos 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 i-th stub se conecta a uno de los kwstubs del nodo wen este gráfico aleatorio en particular. Si no es así, entonces {displaystyle I_{i}^{(v,w)}=0}. Dado que el i-th stub del nodo vpuede conectarse a cualquiera de los 2m-1stubs restantes con la misma probabilidad, y dado que hay kwstubs a los que puede conectarse asociado con el nodo 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 vy wes justo {displaystyle J_{vw}=sum _{i=1}^{k_{v}}I_{i}^{(v,w)}}, por lo que el valor esperado de esta cantidad es{displaystyle E[J_{vw}]=Eleft[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 metroes grande, descartan la resta de 1en el denominador anterior y simplemente usan la expresión aproximada { estilo de visualización { frac {k_ {v} k_ {w}} {2m}}}para el número esperado de aristas entre dos nodos. Además, en una gran red aleatoria, la cantidad de bucles automáticos y múltiples bordes es muy pequeña. Ignorar los bucles automáticos y los bordes múltiples permite suponer que hay como máximo un borde entre dos 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 1, lo que significa que uno puede aproximar la probabilidad de que exista un borde entre los nodos vy wcomo { estilo de visualización { frac {k_ {v} k_ {w}} {2m}}}.

Modularidad

Por lo tanto, la diferencia entre el número real de aristas entre el nodo vy wy el número esperado de aristas entre ellos es

{ estilo de visualización A_ {vw} - { frac {k_ {v} k_ {w}} {2m}}}

La suma de todos los pares de nodos da la ecuación de modularidad, 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 Ec. 3 vale para la partición en dos comunidades solamente. La partición jerárquica (es decir, la partición en dos comunidades, luego las dos subcomunidades se dividen 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 c comunidades.

{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 vértices de un extremo en la comunidad i y el otro en la comunidad j:e_{{ij}}=sum_{{vw}}{frac {A_{{vw}}}{2m}}1_{{ven c_{i}}}1_{{wen c_{ j}}}

y a i es la fracción de los extremos de las aristas que están unidas a los vértices en la comunidad i:a_{i}={frac{k_{i}}{2m}}=sum_{{j}}e_{{ij}}

Ejemplo de detección de comunidad múltiple

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

ID de nodo12345678910
10110000001
21010000000
31100000000
40000110001
50001010000
60001100000
70000000111
80000001010
90000001100
101001001000

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 representan en la figura 2.

Formulación de matriz

Una formulación alternativa de la modularidad, particularmente útil en algoritmos de optimización espectral, es la siguiente. Definir {displaystyle S_{vr}}ser 1si el vértice vpertenece al grupo ry en { estilo de visualización 0}caso contrario. Despuésdelta (c_{v},c_{w})=sum_{r}S_{{vr}}S_{{wr}}

y por lo tantoQ={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}}}{matemáticas{BS}}),

donde Sestá la matriz (no cuadrada) que tiene elementos { estilo de visualización S_ {v}}y Bes la llamada matriz de modularidad, que tiene elementosB _ {{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 { estilo de visualización 0}.

Para redes divididas en solo dos comunidades, se puede definir alternativamente {displaystyle s_{v}=pm 1}para indicar la comunidad a la que vpertenece el nodo, lo que luego conduce a{displaystyle Q={1 sobre 4m}sum _{vw}B_{vw}s_{v}s_{w}={1 sobre 4m}mathbf {s} ^{mathrm {T} } matemáticasbf {Bs},}

donde sestá el vector columna con elementos { estilo de visualización s_ {v}}.

Esta función tiene la misma forma que el hamiltoniano de un vidrio giratorio 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 números arbitrarios de comunidades es equivalente a un vaso giratorio de Potts y también se pueden desarrollar algoritmos similares para este caso.

Límite de resolución

La modularidad compara la cantidad de aristas dentro de un grupo con la cantidad esperada de aristas que uno encontraría en el racimo si la red fuera una red aleatoria con la misma cantidad de nodos y donde cada nodo mantiene su grado, pero las aristas se unen aleatoriamente. 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 aristas 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 borde único entre los dos clústeres como un signo de una fuerte correlación entre los dos clústeres, y la optimización de la modularidad conduciría a la fusión de los dos clústeres, independientemente de las características de los clústeres. 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. Por esta razón, optimizar la modularidad en redes grandes no resolvería 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.

Métodos multiresolución

Hay 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 bucle propio, que aumenta (r>0) o disminuye (r<0) la aversión de los nodos a formar comunidades; 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.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 multirresolución. Sin embargo, se ha demostrado que estos métodos tienen limitaciones cuando las comunidades son de tamaño muy heterogéneo.

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.

El algoritmo de Leiden que además evita comunidades desconectadas.

El algoritmo Vienna Graph Clustering (VieClus), un algoritmo memético paralelo.

Contenido relacionado

Multigrafo

En matemáticas, y más específicamente en teoría de grafos, un multigrafo es un grafo al que se le permite tener múltiples aristas es decir, aristas que...

Grado (teoría de grafos)

En teoría de grafos, el grado de un vértice de un gráfico es el número de aristas que inciden en el vértice; en un multigrafo, un bucle contribuye 2 al...

Distancia (teoría de grafos)

En el campo matemático de la teoría de grafos, la distancia entre dos vértices en un gráfico es el número de aristas en un camino más corto que los...
Más resultados...
Te puede interesar
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save
cancelcheck_circle