tutorial plotting node network color r igraph

plotting - vertex label color igraph



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

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 lazos son más probables. Mi plan es usar un modelo mixto para predecir cuántas várices dentro del grupo tienen vértices y atributos de 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. Vi los enlaces here también, pero no son específicos de igraph. Gracias por su consejo.

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

  • edge.betweenness.community es un proceso de descomposición jerárquica en el que los bordes se eliminan en el orden decreciente de sus puntajes de intersecció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 los bordes que conectan diferentes grupos tienen más probabilidades de estar contenidos en múltiples caminos más cortos simplemente porque en muchos casos son la única opción para ir de un grupo a otro. Este método arroja buenos resultados, pero es muy lento debido a la complejidad computacional de los cálculos de la periferia de los bordes y porque los puntajes de interdependencia tienen que volver a calcularse después de cada eliminación de los bordes. Sus gráficos con ~ 700 vértices y ~ 3500 bordes 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 que edge.betweenness.community construye un dendrograma completo y no le proporciona ninguna orientación sobre dónde cortar el dendrograma para obtener los grupos finales, por lo que tendrá que usar alguna otra medida para decidirlo (por ejemplo, la modularidad). puntuación de las particiones en cada nivel del dendrograma).

  • fastgreedy.community es otro enfoque jerárquico, pero es bottom-up en lugar de top-down. 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 de manera iterativa, de modo que cada fusión es localmente óptima (es decir, produce el mayor incremento en el valor actual de la modularidad). El algoritmo se detiene cuando ya no es posible aumentar la modularidad, por lo que le ofrece un agrupamiento y un dendrograma. El método es rápido y es el método que generalmente se prueba como una primera aproximación porque no tiene parámetros para sintonizar. Sin embargo, se sabe que sufre un límite de resolución, es decir, las comunidades que se encuentran por debajo de un umbral de tamaño determinado (dependiendo del número de nodos y bordes si recuerdo correctamente) siempre se fusionarán 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, entonces es más probable que las caminatas permanezcan dentro de la misma comunidad porque solo hay unas pocas aristas que conducen fuera de una comunidad determinada. Walktrap ejecuta recorridos cortos aleatorios de 3-4-5 pasos (según uno de sus parámetros) y utiliza los resultados de estos recorridos aleatorios para fusionar comunidades separadas de una manera ascendente como fastgreedy.community . De nuevo, 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.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 los estados de espín 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 espín y cuáles prefieren tener diferentes estados de giro. Luego se simula el modelo para un número dado de pasos, y los estados de giro de las partículas al final definen las comunidades. Las consecuencias son las siguientes: 1) Al final nunca habrá más que c comunidades, aunque puede establecer c hasta tan alto como 200, lo que probablemente sea suficiente para sus propósitos. 2) Al final puede haber menos comunidades c ya que 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, así que no me preocuparía por eso. El método no es particularmente rápido y no es 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 los enlaces negativos (es decir, los enlaces cuyos puntos finales prefieren estar en comunidades diferentes).

  • 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 misma produce un aumento significativo en la modularidad. La división se determina evaluando el autovector principal de la llamada matriz de modularidad, y también existe una condición de detención que impide que los grupos estrechamente conectados se dividan más. Debido a los cálculos de eigenvector implicados, podría no funcionar en gráficos degenerados en los que el solucionador de vectores propios de ARPACK es inestable. En gráficos no degenerados, es probable que arroje un puntaje de modularidad más alto que el método codicioso rápido, 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 k etiquetas. El método luego procede iterativamente y vuelve a asignar etiquetas a los nodos de forma que cada nodo toma la etiqueta más frecuente de sus vecinos de forma síncrona. El método se detiene cuando la etiqueta de cada nodo es una de las etiquetas más frecuentes en su vecindad. Es muy rápido pero produce diferentes resultados basados ​​en la configuración inicial (que se decide al azar), por lo tanto, uno debe ejecutar el método una gran cantidad de veces (digamos, 1000 veces para un gráfico) y luego generar un etiquetado de consenso, que podría ser tedioso.

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

De todos modos, probablemente iría con fastgreedy.community o walktrap.community como 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.