Hispanopedia Wiki
Articulo de referencia

Método de Lovaina

El método de Louvain para la detección de comunidades es un método de optimización voraz destinado a extraer comunidades no superpuestas de grandes redes creadas por Blondel et ...

Hispanopedia WikiContenido en espanolLectura gratuita

El método de Louvain para la detección de comunidades es un método de optimización voraz destinado a extraer comunidades no superpuestas de grandes redes creadas por Blondel et al . [ 1 ] de la Universidad de Louvain (fuente del nombre de este método).

Optimización de la modularidad

La inspiración para este método de detección de comunidades reside en la optimización de la modularidad a medida que avanza el algoritmo. La modularidad es un valor en una escala entre -1 (agrupamiento no modular) y 1 (agrupamiento totalmente modular) que mide la densidad relativa de aristas dentro de las comunidades con respecto a las aristas fuera de ellas. Teóricamente, optimizar este valor da como resultado la mejor agrupación posible de los nodos de una red dada. Sin embargo, dado que recorrer todas las configuraciones posibles de los nodos en grupos resulta poco práctico, se utilizan algoritmos heurísticos.

En el método de Louvain para la detección de comunidades, primero se encuentran comunidades pequeñas optimizando la modularidad localmente en todos los nodos, luego cada comunidad pequeña 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 [ 2 ] que conecta comunidades cuya fusión produce el mayor aumento en la modularidad. Aunque el algoritmo de Louvain puede identificar correctamente la estructura de la comunidad cuando su evidencia es suficientemente fuerte en redes artificiales, en particular aquellas muestreadas del modelo de bloques estocásticos asociativos [ 3 ] , es propenso a encontrar comunidades espurias en grafos aleatorios [ 4 ] y se ha demostrado que sobreajusta sistemáticamente los datos empíricos [ 5 ] [ 6 ] .

Descripción del algoritmo

Modularidad

El valor a optimizar es la modularidad , definida como un valor en el rango[−1,1]{\displaystyle [-1,1]}que mide la densidad de enlaces dentro de las comunidades en comparación con los enlaces entre comunidades. [ 1 ] Para un grafo ponderado, la modularidad se define como:

Q=12metro∑i=1norte∑j=1norte[Aij−kikj2metro]δ(doi,doj),{\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:

  • Aij{\displaystyle A_{ij}}representa el peso de la arista entre los nodos i y j ; véase Matriz de adyacencia ;
  • ⁠ki{\displaystyle k_{i}}y​​kj{\displaystyle k_{j}}son la suma de los pesos de las aristas conectadas a los nodos i y j , respectivamente;
  • m es la suma de todos los pesos de las aristas en el grafo;
  • N es el número total de nodos en el grafo;
  • ⁠doi{\displaystyle c_{i}}y​​doj{\displaystyle c_{j}}son las comunidades a las quepertenecen los nodos i y j ; y
  • δ{\displaystyle \delta }es la función delta de Kronecker :

δ(doi,doj)={1si doi y doj son el mismo grupo0de lo contrario{\displaystyle {\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{si }}c_{i}{\text{ y }}c_{j}{\text{ son el mismo clúster}}\\0&{\text{en otro caso}}\end{cases}}\end{aligned}}}

Basándonos en la ecuación anterior, la modularidad de una comunidad c se puede calcular como: [ 7 ]

Qdo=12metro∑i∑jAij1{doi=doj=do}−(∑iki2metro1{doi=do})2=Σinorte2metro−(Σtot2metro)2{\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

  • Σinorte{\displaystyle \Sigma _{in}}es la suma de los pesos de las aristas entre los nodos dentro de la comunidad c (cada arista se considera dos veces); y
  • Σtot{\displaystyle \Sigma _{tot}}es la suma de todos los pesos de las aristas para los nodos dentro de la comunidad (incluidas las aristas que enlazan con otras comunidades).

Como los nodos en diferentes comunidades no contribuyen a la modularidad Q , se puede escribir como:

Q=∑doQdo{\displaystyle Q=\sum _{c}Q_{c}}

El algoritmo del método de Louvain

El método de Louvain funciona repitiendo dos fases. [ 1 ] En la primera fase, los nodos se clasifican en comunidades según cómo cambia la modularidad del grafo cuando un nodo cambia de comunidad. En la segunda fase, el grafo se reinterpreta de manera que las comunidades se consideren nodos individuales. A continuación se ofrece una explicación detallada.

Fase 1

Figura 1: Cada nodo del grafo se asigna aleatoriamente a una comunidad unitaria.
Cada nodo de la red está asignado a su propia comunidad.

El método de Louvain comienza considerando que cada nodo v en un grafo constituye su propia comunidad. Esto se puede observar en la Figura 1, donde cada punto (que representa un nodo) tiene un color único (que indica a qué comunidad pertenece el nodo).

Los nodos se agrupan en comunidades.

Para cada nodo v , consideramos cómo afectará el traslado de v desde su comunidad actual C a una comunidad vecina C' a la modularidad de la partición del grafo. En el pseudocódigo que se muestra a continuación, esto ocurre dentro del bucle for. Seleccionamos la comunidad C' con el mayor cambio en la modularidad y, si el cambio es positivo, trasladamos v a C' ; de lo contrario, lo dejamos donde está. Este proceso continúa hasta que la modularidad deja de mejorar.

Figura 2: Los nodos se asignan a comunidades en función de su modularidad.
función moveNodes(Grafo G, Partición P):  hacer  antigua_modularidad <- actual_modularidad_de_la_partición  para v en V(G), hacer  # encuentra la comunidad que provoca el mayor aumento de modularidad cuando v se mueve a ella.  C' <- argmax(delta_Q) # delta_Q es el cambio en la modularidad  si delta_Q > 0, entonces  mover v a C'  fin si  fin para  actualizar current_modularity_of_partition  mientras current_modularity_of_partition > old_modularity  devolver P función final

[ 8 ]

Este proceso se aplica de forma repetida y secuencial a todos los nodos hasta que no se produzca ningún aumento de modularidad. Una vez alcanzado este máximo local de modularidad, finaliza la primera fase. La figura 2 muestra cómo podría verse el gráfico de la figura 1 tras una iteración de la fase 1.

Fase 2

Las comunidades se reducen a un único nodo.

Para cada comunidad en la partición de nuestro grafo, los nodos individuales que la componen se combinan y la comunidad misma se convierte en un nodo. Las aristas que conectan comunidades distintas se utilizan para ponderar las nuevas aristas que conectan nuestros nodos agregados.

Este proceso se modela en el pseudocódigo, donde la función aggregateGraph devuelve un nuevo grafo cuyos vértices son la partición del grafo original y cuyas aristas se calculan utilizando dicho grafo. Esta función no muestra la ponderación de las aristas, pero una simple modificación permitiría registrar dicha información.

Figura 3: Las comunidades se reducen a un único nodo con aristas ponderadas.
función aggregateGraph(Grafo G, Partición P):  V <- P  E <- [(A,B) | (x,y) está en E(G), x está en A y A está en P, y está en B y B está en P]  devolver Grafo(V,E) función final

[ 8 ]

La figura 3 muestra el aspecto que tendría el gráfico de la figura 2 tras su agregación. Este gráfico es análogo al de la figura 1, ya que cada nodo se asigna a una única comunidad. A partir de aquí, el proceso puede repetirse para que se añadan más nodos a las comunidades existentes hasta alcanzar un nivel óptimo de modularidad.

El pseudocódigo que aparece a continuación muestra cómo las dos funciones anteriores trabajan juntas para completar el proceso.

función louvain(Grafo G, Partición P): hacer P <- moveNodes(G, P) hecho <- length(P) == length(V(G)) # cada comunidad es un nodo único, a pesar de ejecutar moveNodes Si no se ha hecho, entonces: G <- aggregateGraph(G, P) P <- singletonPartition(G) fin si mientras no esté hecho función final función singletonPartition(Grafo G): return [{v} | v está en V(G)] # cada nodo se coloca en su propia comunidad función final

[ 8 ]

complejidad temporal

Generalmente, se supone que el método de Louvain tiene una complejidad temporal deO(norteregistro⁡norte){\displaystyle O(n\log {}n)}Richard Blondel, coautor del artículo que publicó originalmente el método de Louvain, parece apoyar esta noción, [ 9 ] pero otras fuentes afirman que la complejidad temporal es "esencialmente lineal en el número de enlaces en el grafo", [ 10 ] lo que significa que la complejidad temporal sería en cambioO(metro){\displaystyle O(m)}donde m es el número de aristas del grafo. Desafortunadamente, ninguna fuente ha publicado un análisis de la complejidad temporal del método de Louvain, por lo que se intenta realizar uno aquí.

En el pseudocódigo anterior, la función louvain controla la ejecución del algoritmo. Es evidente que dentro de louvain , moveNodes se repetirá hasta que ya no sea posible combinar nodos en comunidades. Esto depende de dos factores: cuánto puede mejorar la modularidad del grafo y, en el peor de los casos, si la modularidad puede mejorar con cada iteración de louvain , depende de la rapidez con que aggregateGraph reduzca el grafo a un solo nodo.

Si en cada iteración de louvain , moveNodes solo puede mover un nodo a una comunidad, entonces aggregateGraph solo podrá reducir el tamaño del grafo en uno. Esto haría que louvain se repitiera v veces. Dado que moveNodes itera a través de todos los nodos de un grafo, esto resultaría en una complejidad temporal deO(norte2){\displaystyle {\mathcal {O}}(n^{2})}donde n es el número de nodos.

No está claro si esta situación es posible, por lo que el resultado anterior debe considerarse una cota aproximada. Blondel et al. afirman en su publicación original que la mayor parte del tiempo de ejecución se invierte en las primeras iteraciones del algoritmo porque "el número de comunidades disminuye drásticamente después de solo unas pocas pasadas". [ 1 ] Esto se puede entender considerando un escenario en el que moveNodes puede mover cada nodo de manera que cada comunidad tenga dos nodos. En este caso, aggregateGraph devolvería un grafo de la mitad del tamaño del original. Si esto continuara, entonces el método de Louvain tendría un tiempo de ejecución denorteregistro2⁡norte{\displaystyle n\log _{2}{n}}Aunque no está claro si este sería el peor caso, el mejor caso, el caso promedio o ninguno de ellos. Además, no hay garantía de que el tamaño del gráfico se reduzca en el mismo factor con cada iteración, por lo que ninguna función logarítmica puede describir perfectamente la complejidad temporal.

Usos anteriores

  • Red social Twitter (2,4 millones de nodos, 38 millones de enlaces) por Josep Pujol, Vijay Erramilli y Pablo Rodríguez: [ 11 ] Los autores exploran el problema de la partición de 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: [ 12 ] Estrategias de seguimiento de comunidades para identificar comunidades dinámicas de diferentes redes sociales dinámicas.
  • Detección de especies en un modelo dinámico basado en redes. [ 13 ]

Desventajas

Louvain produces only non-overlapping communities, which means that each node can belong to at most one community. This is highly unrealistic in many real-world applications. For example, in social networks, most people belong to multiple communities: their family, their friends, their co-workers, old school buddies, etc. In biological networks, most genes or proteins belong to more than one pathway or complex. Furthermore, Louvain has been shown to sometimes produce arbitrarily badly connected communities, and has been effectively superseded (at least in the non-overlapping case) by the Leiden algorithm.

A graph illustrating how communities can become disconnected when using the Louvain algorithm.

A worst case example of an arbitrarily badly connected community is a internally disconnected community. An internally disconnected community arises through the Louvain algorithm when a node that had been acting as a "bridge" between two groups of nodes in its community is moved to a new community, leaving the old one disconnected. The remaining nodes in the old community may also be relocated, but if their connection to the community is strong enough despite the removal of the "bridge" node, they will instead remain in place. For an example of this, see the image to the right; note how the removal of the bridge node, node 0, caused the red community to be split into two disjoint subgroups. While this is the worst-case scenario, there are other, more subtle problems with the Louvain algorithm that can also lead to arbitrarily badly connected communities, such as the formation of communities using nodes that are only weakly connected.

An image depicting how the resolution limit of modularity can cause subcommunities to become hidden.

Another common issue with the Louvain algorithm is the resolution limit of modularity - that is, multiple small communities being grouped together into a larger community. This causes the smaller communities to be hidden; for an example of this, see the visual depiction of the resolution limit to the right. Note how, when the green community is absorbed into the blue community to increase the graph's modularity, the smaller group of nodes that it represented is lost. There is no longer a way to differentiate those nodes from the nodes that were already in the blue community. Conversely, the nodes that were already in the blue community no longer appear distinct from those that were in the green community; in other words, whatever difference caused them to initially be placed in separate communities has been obscured.

Tanto el límite de resolución de la modularidad como el problema de las comunidades arbitrariamente mal conectadas se agravan con cada iteración del algoritmo. En última instancia, lo único que garantiza el algoritmo de Louvain es que las comunidades resultantes no se pueden fusionar; es decir, están bien separadas. Para evitar los problemas derivados de las comunidades arbitrariamente mal conectadas y el límite de resolución de la modularidad, se recomienda utilizar el algoritmo de Leiden , ya que su fase de refinamiento y otros ajustes han corregido estos problemas. [ 8 ]

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

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

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

Véase también

Referencias

  1. 1 2 3 4 5 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. 1 2 Clauset, Aaron; Newman, MEJ; Moore, Cristopher (2004-12-06). "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 .   
  3. ↑ 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 . 
  4. ↑ Guimerà, Roger; Sales-Pardo, Marta; Amaral, Luís A. Nunes (19 de agosto de 2004). "Modularidad a partir de fluctuaciones en grafos aleatorios y redes complejas" . Physical Review E. 70 ( 2) 025101. doi : 10.1103/PhysRevE.70.025101 . PMC 2441765. Recuperado el 8 de octubre de 2013 . 
  5. ↑ Ghasemian, Amir; Hosseinmardi, Homa; Clauset, Aaron (2019). "Evaluación del sobreajuste y el subajuste en modelos de estructura de comunidad de red". IEEE Transactions on Knowledge and Data Engineering : 1–1 . arXiv : 1802.10582 . doi : 10.1109/TKDE.2019.2911585 . ISSN 2326-3865 . 
  6. ↑ Peixoto, Tiago P.; Kirkley, Alec (23 de agosto de 2023). "Modelos implícitos, compresión latente, sesgos intrínsecos y almuerzos baratos en la detección de comunidades" . Physical Review E. 108 ( 2) 024309. American Physical Society. doi : 10.1103/PhysRevE.108.024309 . Recuperado el 18 de marzo de 2024 .
  7. ^ Ghosh, Sayan; Halappanavar, Mahantesh; Tumeo, Antonino; Kalyanaraman, Ananth; Lu, Hao; Chavarría-Miranda, Daniel G.; Khan, Arif; Gebremedhin, Assefaw Hadish (2018). "Algoritmo distribuido de Lovaina para la detección de comunidades de gráficos" (PDF) . Simposio internacional de procesamiento distribuido y paralelo IEEE 2018, IPDPS 2018, Vancouver, BC, Canadá, 21 al 25 de mayo de 2018 . Sociedad de Computación IEEE. págs. 885– 895. doi : 10.1109/IPDPS.2018.00098 . ISBN  978-1-5386-4368-6.
  8. 1 2 3 4 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 .   
  9. ↑ "Método de Lovaina para la detección de comunidades" . perso.uclouvain.be . Consultado el 21/11/2024 .
  10. ↑ "Louvain - Analytics & Algorithms - Ultipa Graph" . www.ultipa.com . Consultado el 21 de noviembre de 2024 .
  11. ↑ Pujol, Josep M.; Erramilli, Vijay; Rodriguez, Pablo (2009). "Divide y vencerás: partición de redes sociales en línea". arXiv : 0905.4918v1 [ cs.NI ].
  12. ↑ 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 del original (PDF) el 12 de mayo de 2013. Consultado el 20 de noviembre de 2014 .
  13. ↑ 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 .  
  14. ↑ Pons, Pascal; Latapy, Matthieu (2006). "Computing Communities in Large Networks Using Random Walks" (PDF) . Journal of Graph Algorithms and Applications . 10 (2): 191– 218. arXiv : cond-mat/0412368 . doi : 10.7155/jgaa.00124 . S2CID 121714719 . 
  15. ↑ Wakita, Ken; Tsurumi, Toshiyuki (2007). "Finding Community Structure in Mega-scale Social Networks". arXiv : cs/0702048 .
  16. ↑ 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 . 
  17. ↑ 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 Lovaina para la detección de comunidades en grandes redes" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html
Lecturas relacionadas
6 articulos
Algoritmo codiciosoAlgoritmo codiciosoUn algoritmo codicioso es cualquier algoritmo que sigue la heurística de resolución de problemas de tomar la decisión localmente óptima en cada eta...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Vicente BlondelVincent Daniel Blondel (nacido el 28 de abril de 1965) es un profesor belga de matemáticas aplicadas , exrector de la Universidad de Lovaina (UCLou...UCLouvainUCLouvainBook celebrating the 25 anniversary of the founding of the Catholic University of Louvain, November 3, 1859. UCLouvain (or Université catholique de...Estructura de la comunidadEstructura de la comunidadEn el estudio de redes complejas , se dice que una red tiene estructura de comunidad si sus nodos pueden agruparse fácilmente en conjuntos (potenci...Modularidad (redes)Modularidad (redes)La modularidad es una medida de la estructura de redes o grafos que cuantifica la fuerza de división de una red en módulos (también llamados grupos...