Método de Louvain

El método de Louvain para detección de comunidades permite extraer comunidades de redes grandes. Fue creado por Blondel et al. y toma su nombre de la filiación de los autores, la Universidad Católica de Lovaina (Bélgica). Se trata de un algoritmo de optimización codicioso cuyo tiempo de ejecución está dado por $O(n*log(n))$.

Optimización de la Modularidad

Este método de detección de comunidades busca optimizar la modularidad, un número entre -0.5 y 1 que compara la densidad de aristas dentro y fuera de una comunidad. Teóricamente, optimizando este valor iteración a iteración se obtiene la mejor posible agrupación de los nodos de una red. Sin embargo, pasar por todas las iteraciones posibles de los nodos a grupos resulta poco práctico y por lo tanto se usan distintas heurísticas. En el Método de Louvain de detección de comunidades, primero se encuentran comunidades pequeñas optimizando la modularidad localmente para todos los nodos, luego cada comunidad pequeña se asocia a un nodo y se repite el proceso hasta alcanzar la convergencia. El método es similar al método de Clauset, Newman y Moore que conecta las comunidades cuya amalgama produzca el aumento más grande en modularidad.

Algoritmo

El valor a optimizar es la modularidad, definido como un número entre -0.5 y 1. Para una red pesada, la modularidad está definida por:

$Q=\frac{1}{2m}\sum _{ij}[A_{ij}-\frac{k_i{k}_j}{2m}]\delta (c_i,c_j)$

• $A_{i,j}$ representa el peso de la arista entre los nodos $i$ y $j$;
• $k_i$ es la suma de los pesos de las aristas del nodo $i$.
• $2m$ es la suma de todos los pesos de las aristas en la red;
• $c_i$ es la comunidad del nodo $i$;
• $\delta$ es la función de delta.

Para maximizar este valor eficientemente, el Método de Louvain tiene dos fases que son repetidas iterativamente.

Primero, cada nodo en la red está asignado a su comunidad propia. Entonces para cada nodo $i$, el cambio en modularidad está dado por la diferencia de remover el nodo $i$ de su comunidad y agregarlo a la comunidad de cada uno de sus vecinos. Este valor es fácilmente calculable en dos pasos: (1) sacando al nodo $i$ de su comunidad original, y (2) insertando al nodo $i$ a la comunidad del nodo $j$, donde el nodo $j$ es vecino del nodo $i$. Las dos ecuaciones son bastante similares, y la ecuación para paso (2) es:$i$$i$$j$$i$$i$$i$$j$

$\mathrm{\Delta }Q=[\frac{{\mathrm{\Sigma }}_{in}+2k_{i,in}}{2m}-(\frac{{\mathrm{\Sigma }}_{tot}+k_i}{2m}{)}^2]-[\frac{{\mathrm{\Sigma }}_{in}}{2m}-(\frac{{\mathrm{\Sigma }}_{tot}}{2m}{)}^2-(\frac{k_i}{2m}{)}^2]$

Donde ${\mathrm{\Sigma }}_{in}$es la suma de todos los pesos de los enlaces dentro de la comunidad i a la que se está moviendo el nodo; ${\mathrm{\Sigma }}_{tot}$es la suma de todos los pesos de los enlaces a los nodos de la comunidad i a la que se está moviendo el nodo,$k_i$es el grado ponderado del nodo i, $k_{i,im}$ es la suma de los pesos de los enlaces entre el nodo i y otros nodos en la comunidad a la que i se está moviendo, y $m$es la suma de los pesos de todos los enlaces en la red. Luego, una vez que se calcula este valor para todas las comunidades a las que está conectado, el nodo i se coloca en la comunidad que resultó en el mayor aumento de modularidad. Si no es posible un aumento, el nodo i permanece en su comunidad original. Este proceso se aplica de forma repetida y secuencial a todos los nodos hasta que no se pueda producir un aumento de la modularidad. Una vez que se alcanza este máximo local de modularidad, la primera fase ha finalizado.$i$

En la segunda fase del algoritmo, agrupa todos los nodos de la misma comunidad y crea una nueva red donde los nodos son las comunidades de la fase anterior. Todos los enlaces entre nodos de la misma comunidad ahora están representados por auto-bucles en el nuevo nodo de comunidad y los enlaces de múltiples nodos en la misma comunidad a un nodo en una comunidad diferente están representados por bordes ponderados entre comunidades. Una vez que se crea la nueva red, la segunda fase ha finalizado y la primera fase se puede volver a aplicar a la nueva red.

Usos anteriores

• Twitter Red social (2.4 millones de nodos, 38 millones de enlaces) por Josep Pujol, Vijay Erramilli, y Pablo Rodríguez: Los autores exploran el problema de particionar Redes Sociales En línea en máquinas diferentes.
• Red de teléfono celular (4 millones de nodos, 100 millones de enlaces) por Derek Greene, Donal Doyle, y Padraig Cunningham: estrategias de seguimiento de comunidades para identificar comunidades dinámicas de redes sociales diferentes.
• Detectando especies basado en el modelado de redes dinámicas.

Comparación a otros métodos

Al comparar los métodos de optimización de la modularidad, las dos medidas de importancia son la velocidad y el valor de la modularidad resultante. Una mayor velocidad es mejor ya que muestra que un método es más eficiente que otros y un valor de mayor modularidad es deseable ya que apunta a tener comunidades mejor definidas. Los métodos comparados son, el algoritmo de Clauset, Newman y Moore, Pons y Latapy, y Wakita y Tsurumi.

Comparación de optimizaciones de modularidad

	Kárate	Arxiv	Internet	Web nd.edu	Teléfono	Web uk-2005	Web WebBase 2001
nodos/aristas	34/77	9k/24k	70k/351k	325k/1M	2.6M/6.3M	39M/783M	118M/1B
Clauset, Newman, y Moore	.38/0s	.772/3.6s	.692/799s	.927/5034s	-/-	-/-	-/-
Pons y Latapy	.42/0s	.757/3.3s	.729/575s	.895/6666s	-/-	-/-	-/-
Wakita Y Tsurumi	.42/0s	.761/0.7s	.667/62s	.898/248s	.56/464s	-/-	-/-
Louvain Método	.42/0s	.813/0s	.781/1s	.935/3s	.769/134s	.979/738s	.984/152mn

-/- En la tabla refiere a un método que tomó encima 24hrs para correr. Dicha tabla muestra que el Método de Louvain es mejor que muchos modelos similares tanto en modularidad como en tiempo.

Véase también

• Estructura comunitaria
• Ciencia de redes
• K-Medias