17.7: Estructura y Modularidad Comunitaria
- Page ID
- 115766
Los temas finales de este capítulo son la estructura comunitaria y la modularidad de una red. Estos temas han sido estudiados muy activamente en la ciencia de redes durante los últimos años. Estas son propiedades mesoscópicas típicas de una red; ni las propiedades microscópicas (por ejemplo, grados o coeficientes de agrupamiento) ni macroscópicas (por ejemplo, densidad, longitud de ruta característica) pueden decirnos cómo se organiza una red a escalas espaciales intermedias entre esos dos extremos, y por lo tanto, estos conceptos también son muy relevantes para el modelado y la comprensión de sistemas complejos.
Comunidad Un conjunto de nodos que están conectados más densamente entre sí que con el resto de la red. Las comunidades pueden o no solaparse entre sí, dependiendo de sus definiciones.
Modularidad La medida en que una red se organiza en múltiples comunidades.
La Figura 17.7.1 muestra un ejemplo de comunidades en una red.
Hay literalmente docenas de formas diferentes de definir y detectar comunidades en una red. Pero aquí, discutiremos solo un método que ahora es ampliamente utilizado por los investigadores de la ciencia de redes: el método de Lovaina, propuesto por Vincent Blondel et al. en 2008 [77]. Es un algoritmo heurístico muy rápido y eficiente que maximiza la modularidad de la estructura comunitaria no superpuesta a través de un proceso de optimización jerárquica iterativa.
La modularidad de un conjunto dado de comunidades en una red se define de la siguiente manera [78]:
\[Q= \frac{|E_{in}|- \langle{E_{in} \rangle}}{|E|} \label{(17.35)} \]
Aquí,\(|E|\) es el número de bordes,\(|E_{in}|\) es el número de bordes dentro de la comunidad (es decir, aquellos que no cruzan fronteras entre comunidades), y\(\langle{|E_{in}|} \rangle\) es el número esperado de bordes dentro de la comunidad si la topología fuera puramente aleatoria. La resta de\(\langle{|E_{in}|} \rangle\) en el numerador penaliza la estructura trivial de la comunidad, como considerar a toda la red una sola comunidad que trivialmente maximizaría\({|E_{in}|}\).
El método Lovaina encuentra la estructura comunitaria óptima que maximiza la modularidad en los siguientes pasos:
1. Inicialmente, cada nodo es asignado a su propia comunidad donde el nodo en sí es el único miembro de la comunidad. Por lo tanto, el número de comunidades iniciales es igual al número de nodos.
2. Cada nodo considera a cada uno de sus vecinos y evalúa si unirse a la comunidad del vecino aumentaría la modularidad de la estructura comunitaria. Después de evaluar a todos los vecinos, se unirá a la comunidad del vecino que logre el incremento máximo de modularidad (sólo si el cambio es positivo; de lo contrario el nodo permanecerá en su propia comunidad). Esto se aplicará repetidamente para todos los nodos hasta que no se pueda lograr más ganancia positiva.
3. El resultado del Paso 2 se convierte en una nueva meta-red a un nivel superior, agregando nodos que pertenecían a una sola comunidad en un meta-nodo, representando los bordes que existían dentro de cada comunidad como el peso de un auto-bucle unido al meta-nodo, y representando los bordes que existían entre comunidades como los pesos de los meta-bordes que conectan los meta-nodos.
4. Los dos pasos anteriores se repiten hasta que no sea posible más mejora de la modularidad.
Una cosa buena de este método es que está libre de parámetros; no es necesario especificar el número de comunidades ni los criterios para detener el algoritmo. Todo lo que necesita es proporcionar datos de topología de red, y el algoritmo encuentra heurísticamente la estructura de la comunidad que está cerca de ser óptima para lograr la mayor modularidad.
Desafortunadamente, NetworkX no tiene este método de Lovaina como función incorporada, pero su implementación en Python ha sido desarrollada y liberada libremente por Thomas Aymaud, que está disponible en perso.crans.org/aynaud/communities/. Una vez que lo instalas, un nuevo módulo de comunidad estará disponible en Python. Aquí hay un ejemplo:
Aquí se ponen a prueba las dos funciones importantes en el módulo comunitario. El primero es best_partition, que genera una estructura comunitaria utilizando el método Lovaina. El resultado se da como un diccionario donde las claves y los valores son los ID de nodo y los ID de comunidad, respectivamente. La segunda función mostrada anteriormente es la modularidad, que recibe la estructura comunitaria y una red y devuelve el valor de modularidad alcanzado por las comunidades dadas.
Visualice la estructura de la comunidad en la gráfica del Club de Karate utilizando los ID de comunidad como los colores de los nodos.
Importe un gran conjunto de datos de red de su elección desde el sitio web de Network Data de Mark Newman: http://www-personal.umich.edu/~mejn/netdata/ Detecte su estructura comunitaria utilizando el método Lovaina y visualícela si es posible.
Haga una búsqueda rápida de literatura en línea para otros algoritmos de detección de la comunidad (por ejemplo, método\(k\) Girvan-Newman, método de percolación -clique, método de caminata aleatoria, etc.). Elige uno de ellos y lee la literatura para aprender cómo funciona. Si el software está disponible, pruébalo tú mismo en la gráfica de Karate Club o en cualquier otra red y mira en qué se diferencia el resultado del método Lovaina.