ⓘ 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 no ..

                                     

ⓘ 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 las autoras, de la Universidad Católica de Lovaina. Se trata de un algoritmo de optimización codicioso cuyo tiempo de ejecución esta dado por O) {\displaystyle O)}.

                                     

1. Optimización de la Modularidad

Este método de detección de comunidades busca optimizar la modularidad, un número entre -1 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.

                                     

2. Algoritmo

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

Donde Σ i n {\displaystyle \Sigma _{in}} es la suma de todos los pesos de los enlaces dentro de la comunidad i la que se esta moviendo el nodo; Σ t o t {\displaystyle \Sigma _{tot}} es la suma de todos los pesos de los enlaces a los nodos de la comunidad i la que se está moviendo el nodo, k i {\displaystyle k_{i}} es el grado ponderado del nodo i, k i, i m {\displaystyle k_{i,im}} es la suma de los pesos de los enlaces entre el nodo i y otros nodos en la comunidad la que i se está moviendo, y m {\displaystyle 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 {\displaystyle 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 la nueva red.

                                     

3. Usos anteriores

  • Twitter Red social 2.4 millones de nodos, 38 millones de enlaces por Josep Pujol, Vijay Erramilli, y Pablo Rodriguez: Los autores exploran el problema de particionar Redes Sociales On-line en máquinas diferentes. ​
                                     

4. 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 ​