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

Tengo una lista de aproximadamente 100 objetos igraph con un objeto típico que tiene aproximadamente 700 vértices y 3500 bordes.

Me gustaría identificar grupos de vértices dentro de los cuales los vínculos son más probables. Mi plan es luego usar un modelo mixto para predecir cuántos vínculos dentro del grupo tienen los vértices usando los atributos de vértice y grupo.

Algunas personas pueden querer responder a otros aspectos de mi proyecto, lo que sería genial, pero lo que más me interesa es la información sobre las funciones en igraph para agrupar vértices. Me he encontrado con estos algoritmos de detección de comunidades, pero no estoy seguro de sus ventajas y desventajas, o si alguna otra función sería mejor para mi caso. También vi los enlaces aquí , pero no son específicos de igraph. Gracias por su consejo.

A continuación, se incluye un breve resumen sobre los algoritmos de detección de comunidades que se implementan actualmente en igraph:

• edge.betweenness.communityes un proceso de descomposición jerárquica en el que los bordes se eliminan en el orden decreciente de sus puntuaciones de intermediación de bordes (es decir, el número de caminos más cortos que pasan por un borde determinado). Esto está motivado por el hecho de que es más probable que los bordes que conectan diferentes grupos estén contenidos en múltiples rutas más cortas simplemente porque en muchos casos son la ú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 interferencia de bordes y porque las puntuaciones de intermediación tienen que volver a calcularse después de cada eliminación de borde. 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 analizar con este enfoque. Otra desventaja es queedge.betweenness.communityconstruye un dendrograma completo y no le brinda 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.communityes otro enfoque jerárquico, pero es de abajo hacia arriba en lugar de 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 sea localmente óptima (es decir, produce el mayor aumento en el valor actual de modularidad). El algoritmo se detiene cuando ya no es posible aumentar la modularidad, por lo que le proporciona una agrupación y un dendrograma. El método es rápido y es el método que se suele probar como primera aproximación porque no tiene parámetros para ajustar. 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 determinado (dependiendo del número de nodos y bordes, si mal no recuerdo) siempre se fusionarán con las comunidades vecinas.

• walktrap.communityes un enfoque basado en paseos aleatorios. 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 determinada. Walktrap ejecuta caminatas aleatorias cortas de 3-4-5 pasos (dependiendo de uno de sus parámetros) y usa los resultados de estas caminatas aleatorias para fusionar comunidades separadas de una manera ascendente como fastgreedy.community. Nuevamente, puede usar la puntuación de modularidad para seleccionar dónde cortar el dendrograma. Es un poco más lento que el enfoque rápido y codicioso, pero también un poco más preciso (según la publicación original).

• spinglass.communityes 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 los estados de giro c , y las interacciones entre las partículas (es decir, los bordes del gráfico) especifican qué pares de vértices preferirían permanecer en el mismo estado de giro y cuáles prefiero tener diferentes estados de giro. Luego, el modelo se simula para un número determinado de pasos, y los estados de giro 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 puede establecer c hasta 200, lo que probablemente sea suficiente para sus propósitos. 2) Puede haber menos de ccomunidades al final, ya que algunos de los estados de giro pueden quedar vacíos. 3) No se garantiza que los nodos en partes completamente remotas (o desconectadas) de las redes tengan diferentes estados de giro. Es más probable que esto 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 ni determinista (debido a la simulación en sí), pero tiene un parámetro de resolución ajustable que determina los tamaños de los conglomerados. Una variante del método spinglass también puede tener en cuenta enlaces negativos (es decir, enlaces cuyos extremos prefieren estar en comunidades diferentes).

• leading.eigenvector.communityes un enfoque jerárquico de arriba hacia abajo que optimiza nuevamente 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 evaluando el vector propio principal de la llamada matriz de modularidad, y también existe una condición de parada que evita que los grupos estrechamente conectados se dividan más. Debido a los cálculos de vectores propios involucrados, es posible que no funcione 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 rápido y codicioso, aunque es un poco más lento.

• label.propagation.communityes un enfoque simple en el que a cada nodo se le asigna una de las k etiquetas. Luego, el método procede de manera iterativa y reasigna etiquetas a los nodos de manera que cada nodo toma la etiqueta más frecuente de sus vecinos de manera síncrona. 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 según la configuración inicial (que se decide al azar), por lo tanto, se debe ejecutar el método una gran cantidad 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 comunidades 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 la descripción se mide por el número esperado de bits por vértice requeridos para codificar la ruta de un recorrido aleatorio.

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

Puede encontrar un resumen de los diferentes algoritmos de detección de comunidades aquí: http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

En particular, el algoritmo InfoMAP es un recién llegado que podría ser útil (también admite gráficos dirigidos).