método de Lovaina

---

El método de Louvain para la detección de comunidades es un método para extraer comunidades de grandes redes creado por Blondel et al . ^[1] de la Universidad de Lovaina (la fuente del nombre de este método). El método es un método de optimización codicioso que parece ejecutarse en el tiempo donde está la cantidad de nodos en la red. ^[2]${\displaystyle O(n\cdot \log n)}$${\ estilo de visualización n}$

La inspiración para este método de detección de comunidades es la optimización de la modularidad a medida que avanza el algoritmo. La modularidad es un valor de escala entre −0,5 (agrupación no modular) y 1 (agrupación totalmente modular) que mide la densidad relativa de los bordes dentro de las comunidades con respecto a los bordes fuera de las comunidades. La optimización de este valor teóricamente da como resultado la mejor agrupación posible de los nodos de una red determinada. Pero debido a que pasar por todas las iteraciones posibles de los nodos en grupos no es práctico, se utilizan algoritmos heurísticos.

En el Método Louvain de detección de comunidades, primero se encuentran pequeñas comunidades optimizando la modularidad localmente en todos los nodos, luego cada pequeña comunidad se agrupa en un nodo y se repite el primer paso. El método es similar al método anterior de Clauset, Newman y Moore ^[3] que conecta comunidades cuya fusión produce el mayor aumento en la modularidad.

El valor a optimizar es la modularidad , definida como un valor en el rango que mide la densidad de enlaces dentro de las comunidades en comparación con los enlaces entre comunidades. ^[1] Para un gráfico ponderado, la modularidad se define como:${\ estilo de visualización [-1/2,1]}$

${\displaystyle Q={\frac {1}{2m}}\sum \limits_{ij}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}} {\bigg]}\delta (c_{i},c_{j}),}$

Para maximizar este valor de manera eficiente, el Método Louvain tiene dos fases que se repiten iterativamente.

---