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]
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:
dónde:
- representa el peso del borde entre los nodos y ; ver Matriz de adyacencia ;
- y son la suma de los pesos de los bordes unidos a los nodos y , respectivamente;
- es la suma de todos los pesos de los bordes en el gráfico;
- es el número total de nodos en el gráfico;
- y son las comunidades a las que pertenecen los nodos y ; y
- ¿Es la función delta de Kronecker :
Con base en la ecuación anterior, la modularidad de una comunidad se puede calcular como: [5]
dónde
- es la suma de los pesos de los bordes entre los nodos dentro de la comunidad (cada borde se considera dos veces); y
- 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:
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:
(a) Calcule el cambio en la modularidad al eliminar un nodo de su comunidad original.
(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 .
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 :
A continuación, calculamos la modularidad del clúster antes de añadir el nuevo nodo . Ya hemos calculado esta ecuación:
Finalmente, calculamos la modularidad del clúster después de haber agregado un nuevo nodo :
Podemos reescribir el primer término de la siguiente manera:
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 .
Podemos reescribir el segundo término como:
Juntando todo esto tenemos:
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]
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.
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.
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
Referencias
- ^ abcd 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.
- ^ 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.
- ^ ab 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.
- ^ 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.
- ^ https://eecs.wsu.edu/~ananth/papers/Ghosh_IPDPS18.pdf [ URL básica PDF ]
- ^ 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].
- ^ 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 .
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Wakita, Ken; Tsurumi, Toshiyuki (2007). "Encontrar la estructura de la comunidad en redes sociales a gran escala". arXiv : cs/0702048 .
- ^ 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.
- ^ 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