¿Cuáles son las diferencias entre los algoritmos de detección de la comunidad en igraph?

Aquí hay un breve resumen sobre los algoritmos de detección de la comunidad implementados actualmente en igraph:

• edge.betweenness.community es un proceso de descomposición jerárquica en el que las aristas se eliminan en el orden decreciente de su puntuación entre aristas (es decir, el número de caminos más cortos que pasan a través de una arista dada). Esto está motivado por el hecho de que los bordes que conectan diferentes grupos son más propensos a estar contenidos en múltiples caminos más cortos simplemente porque en muchos casos son los única opción para ir de un grupo a otro. Este método produce buenos resultados, pero es muy lento debido a la complejidad computacional de los cálculos de la diferencia de bordes y porque las puntuaciones de la diferencia tienen que volver a calcularse después de cada eliminación de bordes. Sus gráficos con ~700 vértices y ~3500 aristas están alrededor del límite de tamaño superior de los gráficos que son factibles de ser analizados con este enfoque. Otra desventaja es que edge.betweenness.community construye un dendrograma completo y no le da ninguna orientación sobre dónde cortar el dendrograma para obtener los grupos finales, por lo que tendrá que usar alguna otra medida para decidir eso (por ejemplo, la puntuación de modularidad de las particiones en cada nivel del dendrograma).

• fastgreedy.community es otro enfoque jerárquico, pero es de abajo hacia arriba en lugar de arriba hacia abajo. Intenta optimizar una función de calidad llamada modularidad de una manera codiciosa. Inicialmente, cada vértice pertenece a una comunidad separada, y las comunidades se fusionan iterativamente de modo que cada fusión es localmente óptimo (es decir, produce el mayor aumento en el valor actual de la modularidad). El algoritmo se detiene cuando ya no es posible aumentar la modularidad, por lo que le da una agrupación, así como un dendrograma. El método es rápido y es el método que generalmente se intenta como una primera aproximación porque no tiene parámetros para afinar. Sin embargo, se sabe que sufre de un límite de resolución, es decir, las comunidades por debajo de un umbral de tamaño dado (dependiendo del número de nodos y bordes si I recuerde correctamente) siempre se fusionará con las comunidades vecinas.

• walktrap.community es un enfoque basado en caminatas aleatorias. La idea general es que si realiza caminatas aleatorias en el gráfico, es más probable que las caminatas permanezcan dentro de la misma comunidad porque solo hay unos pocos bordes que conducen fuera de una comunidad dada. Walktrap realiza caminatas aleatorias cortas de 3-4-5 pasos (dependiendo de uno de sus parámetros) y utiliza los resultados de estas caminatas aleatorias para fusionar por separado comunidades de una manera ascendente como fastgreedy.community. Una vez más, puede usar la puntuación de modularidad para seleccionar dónde cortar el dendrograma. Es un poco más lento que el enfoque fast greedy, pero también un poco más preciso (según la publicación original).

• spinglass.community es un enfoque de la física estadística, basado en el llamado modelo de Potts. En este modelo, cada partícula (es decir, vértice) puede estar en uno de c estados de espín, y las interacciones entre las partículas (es decir, los bordes del grafo) especifica qué pares de vértices preferirían permanecer en el mismo estado de espín y cuáles prefieren tener diferentes estados de espín. El modelo se simula para un número dado de pasos, y los estados de espín de las partículas al final definen las comunidades. Las consecuencias son las siguientes: 1) Nunca habrá más de c comunidades al final, aunque se puede establecer c a tan alto como 200, que es probable que sea suficiente para sus propósitos. 2) Puede haber menos que c comunidades al final como algunos de los estados spin pueden quedar vacíos. 3) No se garantiza que los nodos en partes completamente remotas (o no conectadas) de las redes tengan diferentes estados de giro. Esto es más probable que sea un problema solo para gráficos desconectados, por lo que no me preocuparía por eso. El método no es particularmente rápido y no determinista (debido a la simulación en sí), pero tiene un parámetro de resolución sintonizable que determina los tamaños del clúster. Una variante de la el método spinglass también puede tener en cuenta enlaces negativos (es decir, enlaces cuyos puntos finales prefieren estar en diferentes comunidades).

• leading.eigenvector.community es un enfoque jerárquico de arriba hacia abajo que optimiza de nuevo la función de modularidad. En cada paso, el gráfico se divide en dos partes de manera que la separación en sí produce un aumento significativo en la modularidad. La división se determina mediante la evaluación del vector propio líder de la llamada matriz de modularidad, y también hay una parada condición que impide que los grupos estrechamente conectados se dividan aún más. Debido a los cálculos de vectores propios involucrados, podría no funcionar en gráficos degenerados donde el solucionador de vectores propios ARPACK es inestable. En gráficos no degenerados, es probable que produzca una puntuación de modularidad más alta que el método fast greedy, aunque es un poco más lento.

• label.propagation.community es un enfoque simple en el que a cada nodo se le asigna una de las etiquetas k. El método entonces procede iterativamente y re-asigna etiquetas a los nodos de una manera que cada nodo toma la etiqueta más frecuente de sus vecinos de una manera sincrónica. El método se detiene cuando la etiqueta de cada nodo es una de las etiquetas más frecuentes en su vecindario. Es muy rápido pero produce resultados diferentes en función de la configuración inicial (que se decide aleatoriamente), por lo tanto, se debe ejecutar el método un gran número de veces (digamos, 1000 veces para un gráfico) y luego construir un etiquetado de consenso, que podría ser tedioso.

Igraph 0.6 también incluirá el algoritmo de detección de comunidad Infomap de última generación, que se basa en principios teóricos de la información; intenta construir una agrupación que proporcione la longitud de descripción más corta para un recorrido aleatorio en el gráfico, donde la longitud de descripción se mide por el número esperado de bits por vértice necesarios para codificar la ruta de un recorrido aleatorio.

De todos modos, probablemente iría con fastgreedy.community o walktrap.community como una primera aproximación y luego evaluar otros métodos cuando resulta que estos dos no son adecuados para un problema particular por alguna razón.