Método de Lovaina

Algoritmo de detección de comunidades y agrupamiento

El método de Lovaina para la detección de comunidades es un método para extraer comunidades no superpuestas de redes grandes 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 voraz que parece ejecutarse en el tiempo donde es el número de nodos en la red. ^[2] ${\displaystyle O(n\cdot \log n)}$ ${\displaystyle n}$

Optimización de la modularidad

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 (agrupamiento no modular) y 1 (agrupamiento totalmente modular) que mide la densidad relativa de los bordes dentro de las comunidades con respecto a los bordes fuera de las comunidades. Optimizar este valor teóricamente da como resultado la mejor agrupación posible de los nodos de una red dada. Pero como pasar por todas las iteraciones posibles de los nodos en grupos no es práctico, se utilizan algoritmos heurísticos.

En el método de detección de comunidades de Louvain, 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. Se demostró que el algoritmo de Louvain identifica correctamente la estructura de la comunidad cuando existe, en particular en el modelo de bloques estocásticos. ^[4]

Algoritmo

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: ${\displaystyle [-1/2,1]}$

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

dónde:

• ${\displaystyle A_{ij}}$representa el peso del borde entre los nodos y ; ver Matriz de adyacencia ; ${\displaystyle i}$ ${\displaystyle j}$
• ${\displaystyle k_{i}}$y son la suma de los pesos de los bordes unidos a los nodos y , respectivamente; ${\displaystyle k_{j}}$ ${\displaystyle i}$ ${\displaystyle j}$
• ${\displaystyle m}$es la suma de todos los pesos de los bordes en el gráfico;
• ${\displaystyle N}$es el número total de nodos en el gráfico;
• ${\displaystyle c_{i}}$y son las comunidades a las que pertenecen los nodos y ; y ${\displaystyle c_{j}}$ ${\displaystyle i}$ ${\displaystyle j}$
• ${\displaystyle \delta }$¿Es la función delta de Kronecker :

${\displaystyle {\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{if }}c_{i}{\text{ and }}c_{j}{\text{ are the same cluster}}\\0&{\text{otherwise}}\end{cases}}\end{aligned}}}$

Con base en la ecuación anterior, la modularidad de una comunidad se puede calcular como: ^[5] ${\displaystyle c}$

${\displaystyle {\begin{aligned}Q_{c}&={\dfrac {1}{2m}}\sum _{i}\sum _{j}A_{ij}\mathbf {1} \left\{c_{i}=c_{j}=c\right\}-\left(\sum _{i}{\dfrac {k_{i}}{2m}}\mathbf {1} \left\{c_{i}=c\right\}\right)^{2}\\&={\frac {\Sigma _{in}}{2m}}-\left({\frac {\Sigma _{tot}}{2m}}\right)^{2}\end{aligned}}}$

dónde

• ${\displaystyle \Sigma _{in}}$es la suma de los pesos de los bordes entre los nodos dentro de la comunidad (cada borde se considera dos veces); y ${\displaystyle c}$
• ${\displaystyle \Sigma _{tot}}$es la suma de todos los pesos de los bordes de los nodos dentro de la comunidad (incluidos los bordes que se vinculan a otras comunidades).

Como los nodos en diferentes comunidades no contribuyen a la modularidad , se puede escribir como: ${\displaystyle Q}$

${\displaystyle Q=\sum _{c}Q_{c}}$

Para maximizar la modularidad de manera eficiente, el Método Lovaina tiene dos fases que se repiten iterativamente.

Fase 1:

1. En primer lugar, a cada nodo de la red se le asigna su propia comunidad.

2. A continuación, para cada nodo , se calcula el cambio en la modularidad al eliminarlo de su propia comunidad y trasladarlo a la comunidad de cada vecino de . Este valor se calcula en dos pasos: ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$

(a) Calcule el cambio en la modularidad al eliminar un nodo de su comunidad original. ${\displaystyle \Delta Q}$ ${\displaystyle i}$

(b) Calcule el cambio en modularidad al insertar un nodo aislado (es decir, un nodo no tiene conexiones y está en una comunidad solo de sí mismo) en la comunidad del nodo vecino, denotado . ${\displaystyle \Delta Q}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle c_{j}}$

A continuación, mostraremos la derivación para (b). Las ecuaciones para (a) son similares y se pueden calcular mediante métodos similares.

En primer lugar, calculamos la modularidad del grupo aislado de nodos , al que llamaremos . Aquí asumimos que no hay bucles, y por lo tanto, para todos los valores de : ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle A_{\mu \mu }=0}$ ${\displaystyle \mu }$

${\displaystyle {\begin{aligned}Q_{i}^{\text{prev}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{i}=1}\sum _{\nu =1}^{N_{i}=1}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{i}=1}{\dfrac {k_{\mu }}{2m}}\right)^{2}\\&=-\left({\dfrac {k_{i}}{2m}}\right)^{2}\end{aligned}}}$

A continuación, calculamos la modularidad del clúster antes de añadir el nuevo nodo . Ya hemos calculado esta ecuación: ${\displaystyle c_{j}}$ ${\displaystyle i}$

${\displaystyle {\begin{aligned}Q_{j}^{\text{prev}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}}{\dfrac {k_{\mu }}{2m}}\right)^{2}\end{aligned}}}$

Finalmente, calculamos la modularidad del clúster después de haber agregado un nuevo nodo : ${\displaystyle c_{j}}$ ${\displaystyle i}$

${\displaystyle {\begin{aligned}Q_{j}^{\text{updated}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{2m}}\right)^{2}\end{aligned}}}$

Podemos reescribir el primer término de la siguiente manera:

${\displaystyle {\begin{aligned}{\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}A_{\mu \nu }&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2\sum _{\mu =1}^{N_{j}+1}A_{\mu ,N_{j}+1}\right]\\&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]\end{aligned}}}$

donde representa la suma de los pesos de todos los bordes que van entre el nodo y los nodos de la comunidad . En otras palabras, es el grado del nodo dentro de la comunidad . ${\displaystyle k_{i}^{(j)}}$ ${\displaystyle i}$ ${\displaystyle c_{j}}$ ${\displaystyle k_{i}^{(j)}}$ ${\displaystyle i}$ ${\displaystyle c_{j}}$

Podemos reescribir el segundo término como:

${\displaystyle {\begin{aligned}\left(\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{2m}}\right)^{2}&=\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}{\dfrac {k_{\mu }k_{\nu }}{(2m)^{2}}}\\&=\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}{\dfrac {k_{\mu }k_{\nu }}{(2m)^{2}}}+2k_{N_{j}+1}\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{(2m)^{2}}}+{\dfrac {(k_{N_{j}+1})^{2}}{(2m)^{2}}}\\&={\dfrac {1}{(2m)^{2}}}\left[\left(\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}\right)\left(\sum _{\nu =1}^{N_{j}}k_{\nu }+k_{N_{j}+1}\right)\right]\\&=\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\end{aligned}}}$

Juntando todo esto tenemos:

${\displaystyle {\begin{aligned}Q_{j}^{\text{updated}}&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]-\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\end{aligned}}}$

Juntando las ecuaciones para , , y , podemos calcular el cambio en la modularidad al agregar un nodo aislado al clúster . Esto a veces se denomina ganancia : ^[1] ${\displaystyle Q_{i}^{\text{prev}}}$ ${\displaystyle Q_{j}^{\text{prev}}}$ ${\displaystyle Q_{j}^{\text{updated}}}$ ${\displaystyle \Delta Q}$ ${\displaystyle i}$ ${\displaystyle c_{j}}$

$${\displaystyle {\begin{aligned}\Delta Q&=Q_{j}^{\text{updated}}-Q_{j}^{\text{prev}}-Q_{i}^{\text{prev}}\\&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]-\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\\&-\left[{\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}}{\dfrac {k_{\mu }}{2m}}\right)^{2}-\left({\dfrac {k_{i}}{2m}}\right)^{2}\right]\end{aligned}}}$$

3. Una vez calculado el cambio en la modularidad para todas las comunidades a las que está conectado el nodo , este se coloca en la comunidad que generó el mayor aumento de modularidad. Si no es posible ningún aumento, el nodo permanece en su comunidad original. ${\displaystyle \Delta Q}$ ${\displaystyle \{c_{j}\}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$

4. Este proceso se aplica repetida y secuencialmente a todos los nodos hasta que no se pueda producir ningún aumento de modularidad. Una vez que se alcanza este máximo local de modularidad, la primera fase ha finalizado.

Fase 2:

La segunda fase del algoritmo implica reducir las comunidades a un solo nodo y repetir los pasos de la Fase 1:

1. Cada comunidad se reduce a un único nodo. Las aristas que conectan nodos de otras comunidades también se reducen a una única arista ponderada. ${\displaystyle c_{j}}$ ${\displaystyle c_{j}}$

2. Una vez creado el nuevo gráfico, la segunda fase ha finalizado y la primera fase se puede volver a aplicar a la nueva red.

Usos anteriores

• Red social Twitter (2,4 millones de nodos, 38 millones de enlaces) por Josep Pujol, Vijay Erramilli y Pablo Rodríguez: ^[6] Los autores exploran el problema de particionar las redes sociales en línea en diferentes máquinas.
• Red de telefonía móvil (4 millones de nodos, 100 millones de enlaces) por Derek Greene, Donal Doyle y Padraig Cunningham: ^[7] Estrategias de seguimiento de la comunidad para identificar comunidades dinámicas de diferentes redes sociales dinámicas.
• Detección de especies en un modelo dinámico basado en redes. ^[8]

Desventajas

Louvain produce únicamente comunidades no superpuestas, lo que significa que cada nodo puede pertenecer a una sola comunidad como máximo. Esto es muy poco realista en muchas aplicaciones del mundo real. Por ejemplo, en las redes sociales, la mayoría de las personas pertenecen a múltiples comunidades: su familia, sus amigos, sus compañeros de trabajo, viejos compañeros de la escuela, etc. En las redes biológicas, la mayoría de los genes o proteínas pertenecen a más de una vía o complejo. Además, se ha demostrado que Louvain a veces produce comunidades arbitrariamente mal conectadas, y ha sido efectivamente reemplazado (al menos en el caso de no superposición) por el algoritmo de Leiden . ^[9]

Comparación con otros métodos de detección de comunidades no superpuestas

Al comparar los métodos de optimización de la modularidad, las dos medidas de importancia son la velocidad y el valor de modularidad resultante. Una velocidad más alta es mejor, ya que muestra que un método es más eficiente que otros, y un valor de modularidad más alto es deseable, ya que indica que hay comunidades mejor definidas. Los métodos comparados son el algoritmo de Clauset, Newman y Moore ^[3] , Pons y Latapy ^{[10] y Wakita y Tsurumi [11]} .

-/- en la tabla se refiere a un método que tardó más de 24 horas en ejecutarse. Esta tabla (de ^{[1] [13]} ) muestra que el método de Louvain supera a muchos métodos de optimización de modularidad similares tanto en la categoría de modularidad como en la de tiempo.

Véase también

• Algoritmo de Leiden
• Modularidad (redes)
• Estructura de la comunidad
• Ciencia de redes
• Agrupamiento de K-medias

Referencias

1. Blondel, Vincent D; Guillaume, Jean-Loup; Lambiotte, Renaud; Lefebvre, Etienne (9 de octubre de 2008). "Despliegue rápido de comunidades en grandes redes". Journal of Statistical Mechanics: Theory and Experiment . 2008 (10): 10008. arXiv : 0803.0476 . Bibcode :2008JSMTE..10..008B. doi :10.1088/1742-5468/2008/10/P10008. S2CID  334423.
2. Lancichinetti, Andrea; Fortunato, Santo (30 de noviembre de 2009). "Algoritmos de detección de comunidades: un análisis comparativo". Physical Review E . 80 (5): 056117. arXiv : 0908.1062 . Bibcode :2009PhRvE..80e6117L. doi :10.1103/physreve.80.056117. ISSN  1539-3755. PMID  20365053. S2CID  14193110.
3. Clauset, Aaron; Newman, MEJ; Moore, Cristopher (6 de diciembre de 2004). "Encontrar la estructura de la comunidad en redes muy grandes". Physical Review E . 70 (6): 066111. arXiv : cond-mat/0408187 . Bibcode :2004PhRvE..70f6111C. doi :10.1103/PhysRevE.70.066111. ISSN  1539-3755. PMID  15697438. S2CID  8977721.
4. Cohen-Addad, Vincent; Kosowski, Adrian; Mallmann-Trenn, Frederik; Saulpic, David (2020). "Sobre el poder de Louvain en el modelo de bloques estocásticos". Avances en sistemas de procesamiento de información neuronal (Neurips 2020) . Curran Associates, Inc. págs. 4055–4066.
5. https://eecs.wsu.edu/~ananth/papers/Ghosh_IPDPS18.pdf ^{[ URL básica PDF ]}
6. Pujol, Josep M.; Erramilli, Vijay; Rodríguez, Pablo (2009). "Divide y vencerás: la partición de las redes sociales en línea". arXiv : 0905.4918v1 [cs.NI].
7. Greene, Derek; Doyle, Dónal; Cunningham, Pádraig (mayo de 2011). Seguimiento de la evolución de las comunidades en redes sociales dinámicas (PDF) (informe técnico). University College Dublin. UCD-CSI-2011-06. Archivado desde el original (PDF) el 2013-05-12 . Consultado el 2014-11-20 .
8. Markovitch, Omer; Krasnogor, Natalio (2018). "Predicción de la emergencia de especies en redes prebióticas complejas simuladas". PLOS ONE . ​​13 (2): e0192871. Bibcode :2018PLoSO..1392871M. doi : 10.1371/journal.pone.0192871 . PMC 5813963 . PMID  29447212. 
9. Traag, VA; Waltman, L.; van Eck, Nueva Jersey (26 de marzo de 2019). "De Lovaina a Leiden: garantizar comunidades bien conectadas". Informes científicos . 9 (1): 5233. arXiv : 1810.08473 . Código Bib : 2019NatSR...9.5233T. doi :10.1038/s41598-019-41695-z. ISSN  2045-2322. PMC 6435756 . PMID  30914743. 
10. Pons, Pascal; Latapy, Matthieu (2006). "Comunidades informáticas en redes grandes mediante paseos aleatorios" (PDF) . Revista de algoritmos y aplicaciones de grafos . 10 (2): 191–218. arXiv : cond-mat/0412368 . doi : 10.7155/jgaa.00124 . S2CID  121714719.
11. Wakita, Ken; Tsurumi, Toshiyuki (2007). "Encontrar la estructura de la comunidad en redes sociales a gran escala". arXiv : cs/0702048 .
12. Blondel, Vincent D.; Guillaume, Jean-Loup; Lambiotte, Renaud; Lefebvre, Etienne (2008). "Despliegue rápido de comunidades en grandes redes". Journal of Statistical Mechanics: Theory and Experiment . 2008 (10): 10008. arXiv : 0803.0476 . Bibcode :2008JSMTE..10..008B. doi :10.1088/1742-5468/2008/10/P10008. S2CID  334423.
13. Aynaud, Thomas; Blondel, Vincent D.; Guillaume, Jean-Loup; Lambiotte, Renaud (2013). "Optimización local multinivel de la modularidad". En Bichot, Charles-Edmond; Siarry, Patrick (eds.). Particionamiento de grafos (1.ª ed.). Wiley (publicado el 13 de febrero de 2013). pp. 315–345. doi :10.1002/9781118601181.ch13. ISBN 978-1-84821-233-6.

• "El método de Louvain para la detección de comunidades en grandes redes" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html