Pajek: Análisis y visualización de comunidades (1/2)

Detectando comunidades con el método de agrupamiento de Louvain y VOS

Pajek

Detectando comunidades (Pajek y PajekXXL)

El algoritmo de detección de la comunidad de Louvain está disponible en Pajek y PajekXXL 3.02 o posterior.
A partir de la versión 3.04, la implementación ofrece el parámetro de resolución. De esta forma, los usuarios tienen control sobre el tamaño y la cantidad de comunidades encontradas (la resolución 1 significa el método estándar de Louvain, las resoluciones más altas producen un mayor número de clústeres, las resoluciones más bajas producen un menor número de clústeres).
En esta versión, el algoritmo estándar de Louvain fue reemplazado por el algoritmo Multi-Level Coarsening + Multi-Level Refinement.

A partir de la versión 3.05 activada, se incluye el número de parámetro de reinicios. Eso permite ejecutar la optimización varias veces y seleccionar la mejor partición en todas las ejecuciones.

A partir de la versión 3.05, está disponible otro algoritmo de detección de comunidad (VOS Clustering). El uso es muy similar al uso del método de Louvain, por lo tanto, explicaremos el uso solo del método de Louvain. En Louvain, la modularidad del método se optimiza en VOS Clustering VOS quality. La comparación de los resultados obtenidos por ambos métodos se puede encontrar aquí.

Ambos algoritmos son muy rápidos y se pueden aplicar a enormes redes dispersas que contienen cientos de millones de vértices. Los valores de las líneas (si los hay) también se tienen en cuenta en ambos algoritmos.
Hay dos algoritmos disponibles (para más información, consulte: Algoritmos de búsqueda local multinivel para clústeres de modularidad):

1. Multi-Level Coarsening + Single Refinement: realiza solo el refinamiento de la partición obtenida en el último nivel (la partición más grosera).
2. Multi-Level Coarsening + Multi-Level Refinement - realiza iterativamente la fase de engrosamiento y refinamiento para cada nivel obtenido.

Secuencia de pasos en Pajek

1. Descargue el archivo de red de muestra (25069 vértices, 62608 bordes) y cárguelo en Pajek / PajekXXL.
2. Comience la búsqueda en la comunidad:  Network/Create Partition/Communities/Louvain Method
3. Por lo general, se necesitan varios niveles. Pajek devuelve la mejor partición de acuerdo a todos los niveles.
   El número de conglomerados (NC) en niveles disminuye (los conglomerados más pequeños se fusionan con los más grandes en niveles posteriores).
   Por otro lado, aumenta la modularidad (Q) (o calidad VOS) de la partición (que se informa junto con la cantidad de clústeres).
   Pruebe el algoritmo con diferentes valores de parámetro de resolución (la resolución 1 significa el método estándar de Louvain, las resoluciones más altas producen un mayor número de clústeres, las resoluciones más bajas producen un menor número de clústeres).
   Para encontrar soluciones tan buenas (y tantas) como sea posible en los vértices del algoritmo se tienen en cuenta de forma aleatoria. Debido a eso, el algoritmo generalmente arroja resultados diferentes en cada ejecución. Por lo tanto, se recomienda ejecutar el algoritmo con varios reinicios que seleccionan la mejor partición de todos los reinicios.
4. Recomendación: Compare las particiones obtenidas en dos ejecuciones con el mismo parámetro de resolución (usando Partitions / Info / Cramer's V, Rajski, Adjusted Rand Index). Si la correlación de las dos particiones es pequeña, es probable que el número de comunidades no sea el correcto, por lo tanto, sugerimos probar el algoritmo con otro valor (más grande o más pequeño) de parámetro de resolución.
   En nuestro caso obtenemos los siguientes resultados para los valores del parámetro de resolución 1.00, 0.50 y 40.00 respectivamente:
   Resolution: 1.00. Modularity: 0.935506. Number of Communities: 166.
   Resolution: 0.50. Modularity: 0.938871. Number of Communities: 105.
   Resolution: 40.00. Modularity: 0.852442. Number of Communities: 500.
   La correlación entre las particiones obtenidas con el mismo valor de parámetro de resolución es la más alta para resolución = 40.00 (Cramer's V = 0.998) por lo tanto usaremos estas comunidades como las correctas (aunque la modularidad es la más pequeña para este valor de parámetro de resolución).
   Importante: la modularidad se puede usar solo para comparaciones de particiones obtenidas con el mismo valor de parámetro de resolución.
5. Podemos ajustar el Maximum Number of Iterations in each Restart, Maximum Number of Levels in each Iteration (Número Máximo de Iteraciones en cada Reinicio, el Número Máximo de Niveles en cada iteración) permitida y el Maximum Number of Repetitions in each Level (Número Máximo de Repeticiones en cada Nivel) permitido. Los valores predeterminados (20, 20 y 50 respectivamente) funcionan bien para la mayoría de las redes.
   Tenga en cuenta que el primer nivel lleva la mayor parte del tiempo, los niveles posteriores se realizan muy rápidamente, especialmente si el número de clústeres identificados en el primer nivel ya es bajo según el número de vértices (el algoritmo se ejecuta en redes reducidas en niveles posteriores).
6. Podemos usar Operations/Network+Partition/Info para calcular la modularidad de la red según la partición o la calidad de VOS de la partición. Se puede usar en cualquier partición (no solo en particiones obtenidas por el método de Louvain o VOS Clustering).
7. En el caso de una red firmada (al menos un valor de línea es negativo) se llama una versión especial del algoritmo de Louvain (maximizando la suma de las líneas positivas positivas y minimizando las negativas dentro de las comunidades).
   Por otro lado, en VOS Clustring, todos los valores de línea se consideran positivos (se tienen en cuenta los valores de línea absolutos).

Visualizando Comunidades

1. Visualizar comunidades usando VOS Mapping y Spring Embedders

Si el número de comunidades y el tamaño de la comunidad más grande no son demasiado altos, podemos utilizar las comunidades obtenidas para obtener una imagen aproximada de toda la red.

Estimación: las redes con hasta 100.000 vértices se pueden visualizar si el número de comunidades no es mayor que 10000, y el tamaño de la comunidad más grande no es mayor que 1000 al mismo tiempo. Esta es solo una estimación aproximada que depende de la memoria de la computadora disponible y su velocidad también. Y, por supuesto, cuánto tiempo estamos listos para esperar;)

En nuestro caso tenemos aprox. 25,000 vértices, 500 comunidades y el tamaño de la comunidad más grande está por debajo de 80.

Para ver el tamaño de la comunidad más grande, podemos ordenar la partición obtenida en orden decreciente (Partition/Canonical Partition/with Decreasing Frequencies) y aplicar Partition/Info a la partición resultante (la primera comunidad es ahora la más grande).

Secuencia de pasos en Pajek

1. Reducir las comunidades (Operations/Network+Partition/Shrink Network) y dejar respuestas predeterminadas cuando se solicite una entrada. Como resultado, obtenemos una red reducida donde los vértices representan a las comunidades y el valor entre dos comunidades representa el valor total de las líneas que conectan los vértices pertenecientes a las dos comunidades. También obtenemos un bucle para cada comunidad, el valor significa la suma de valores de línea dentro de la comunidad.
2. Primero visualizaremos la red contraída obtenida. En esta red, los valores de las líneas son muy importantes (queremos que las comunidades que son más similares se acerquen entre sí). Por lo tanto, debemos usar algún algoritmo de diseño que tenga en cuenta los valores de las líneas como similitudes. El mapeo de VOS y el dibujo de energía son adecuados para este propósito:
1. Corra VOS Mapping en el que los valores son line siempre se tienen en cuenta (como similitudes).
2. Si queremos aplicar el dibujo de energía, primero debemos verificar las Options/Values of Lines/Similarities (en la ventana Draw). Luego ejecuta cualquier dibujo de energía, p. Fruchterman-Reingold (recomendado) o Kamada-Kawai.

Como resultado, obtenemos un diseño de conexiones entre las comunidades.

Red encogida (500 comunidades)

3. Ahora aplicamos las coordenadas de la red contraída a toda la red. Para hacer eso:

- seleccione la red encogida (500 vértices) como la primera red,

- seleccione la red original (25069 vértices) como segunda red,

- seleccione la partición utilizada para la reducción (con dimensión igual a la red original, 25069 en nuestro caso).

Luego ejecute: Networks/Shrink Coordinates (First to Second)/Partition.

En el diseño resultante, los vértices que pertenecen a la misma comunidad se dibujan distribuidos aleatoriamente cerca de su vértice reducido.

Antes de dibujar una red de tal tamaño, es posible que primero necesite aumentar la red más grande que Pajek está dispuesto a dibujar utilizando: Options/Read-Write/Max Vertices to draw

Disposición obtenida (25069 vértices)

4. Puede dibujar vértices dentro de las comunidades también en círculos (Layout/Circular/UsingPartition). Si los círculos son demasiado grandes o demasiado pequeños, puede cambiar su tamaño usando Options/Transform/Resize Cluster Area.

5. Ahora permitamos optimizar vértices y líneas dentro de clusters solamente.

Nuestra red original no está ponderada (todos los valores de línea son 1), por lo tanto, primero le ordenamos a Pajek que no tenga en cuenta los valores de las líneas durante la optimización: Options/Values of lines/Forget 

(La optimización sin tener en cuenta los valores de línea es mucho más rápida, especialmente Kamada-Kawai).

Para optimizar los vértices y las líneas dentro de los clusters solamente, use Layout/Energy/Kamada-Kawai/Optimize Inside Clusters only

Ahora debemos esperar hasta que el contador en la esquina superior derecha de la ventana Dibujar alcance la cantidad total de comunidades.

En la imagen obtenida puede acercar seleccionando un rectángulo con el botón derecho del mouse.

Si los vértices dentro de los conglomerados están demasiado cerca o muy lejos ('nubes' demasiado pequeñas o demasiado grandes) puede cambiar el tamaño del área de los conglomerados utilizando Options/Transform/Resize Cluster Area.

Diseño final (25069 vértices)

6. En el caso de redes grandes, es mejor eliminar líneas y mostrar solo vértices para ver 'nubes'.

Para hacerlo, desmarque Options/Lines/Draw Lines/Edges.

Diseño final sin líneas (25069 vértices)

Diseño final sin líneas (25069 vértices, ampliado):

Diseños finales en EPS o SVG sin líneas (25069 vértices)

Detección de comunidades con Pajek (1)

Detección de comunidades con Pajek 3.6

por Marion Maisonobe | groupe fmr


La nueva versión de Pajek ofrece buenas sorpresas para los exploradores de grafos complejos.

Las nuevas características discutidas aquí se agregaron al software entre mayo de 2012 y septiembre de 2012.

Se han implementado dos algoritmos de detección de comunidades:

Network/Create Partition/Communities

-Louvain method

El primer algoritmo se basa en el método de Louvain [1]. Este método se adapta bien a los grafos ponderados, incluso si están firmados (signed graphs). Al igual que con muchos algoritmos de agrupación, la calidad de la partición se optimiza mediante la maximización de la función de modularidad [2]. El índice de modularidad mide la diferencia entre la densidad de un grafo (o subgrafo) dado y la densidad de un grafo aleatorio que tiene las mismas características (número y peso de los enlaces).

Principio

Maximizar la función de modularidad para particionar un grafo es como asegurarse de que el número y el peso de los enlaces sean mayores dentro de las particiones que entre las particiones. Para expresarlo de manera diferente, la densidad intra-comunitaria debe exceder la densidad intercomunitaria.

El método de Louvain es "de abajo hacia arriba" y multi-nivel. Al inicio del algoritmo, todos los vértices pertenecen a una partición diferente. Se agrupan, por iteración, en particiones de modularidad óptima. En la primera situación óptima, el proceso continúa en el nivel superior: cada partición se trata como un vértice y así sucesivamente. La operación continúa hasta que no hay más ganancia de modularidad posible.

Ventaja

Este enfoque evita la falta de modularidad conocida como el "límite de resolución" [3]. Si asociar una partición del primer nivel con otro resultaría en una pérdida de modularidad, esta asociación no se realizaría por el método de Louvain. Como resultado, no es probable que estructuras pequeñas con buena modularidad estén incrustadas en estructuras mayores y menos significativas. Esto es lo que sucedería con un algoritmo "top-down" aplicado a un grafo grande.

Desventaja

El defecto conocido del método proviene de la sensibilidad del resultado al orden de tratamiento de los vértices. El orden en que los vértices son considerados tiene una influencia sobre la partición. Por lo tanto, puede ser útil realizar permutaciones para asegurar la robustez del resultado [4]. La otra forma es imponer un orden que tenga en cuenta las características de la red [5].

Además del algoritmo convencional de Louvain, Pajek ofrece una variante (con el refinamiento de niveles múltiples) que tiende a dar mejores resultados para grandes grafos. [6] El método de Louvain también está disponible en los software Gephi y NetworkX, así como en la biblioteca de software de I igraph, el algoritmo es más rápido en Pajek que en Gephi.

-VOS Clustering

El método de detección de la comunidad VOS optimiza otra función de calidad que la función de modularidad: la denominada función de agrupación VOS [7]. Esta es una variante ponderada de la modularidad que se ha pensado para el procesamiento de datos bibliométricos. Esta técnica da menos peso que un método clásico con un grado muy alto. A diferencia del método de Louvain, depende de un algoritmo "de arriba hacia abajo". Por esta razón, la única manera de escapar al problema de limitar la resolución es variar el parámetro de resolución.

Este método es adecuado para grafos para los cuales el valor de los enlaces explica la importancia de la similitud entre los vértices. Sus diseñadores querían ser asociados con el algoritmo de agrupación un algoritmo de visualización usando el mismo principio matemático. Este enfoque unificado hace posible evitar inconsistencias entre el resultado del proceso de agrupación y la representación gráfica de este resultado.

Naturalmente, Pajek también ofrece el algoritmo de visualización VOS. Funciona sobre el principio de la optimización de la función de calidad denominada mapeo VOS. Dada la proximidad de los dos métodos de detección, no es ciertamente impensable utilizar la asignación VOS para representar un grafo particionado de acuerdo con el método de Louvain.

Ir más lejos

Se puede encontrar una comparación de los dos métodos de detección en:
http://mrvar.fdv.uni-lj.si/pajek/community/LouvainVOS.htm

Los detalles sobre el uso de estos métodos con Pajek también se pueden encontrar en el sitio: parametrización, evaluación de la calidad de la partición, representación gráfica del resultado.

Desde la interfaz gráfica de Pajek, un acceso directo al software VOSviewer ofrece la posibilidad de obtener rápidamente una representación elegante de la partición.

A continuación se muestra un ejemplo de los datos de colaboración científica holandesa (Fuente: Web of Science 2006-2008):

Referencias

1. V. Blondel, J.-L. Guillaume, R. Lambiotte, et E. Lefebvre, « Fast unfolding of communities in large networks », Journal of Statistical Mechanics, vol. 2008, no 10, sept. 2008.
2. Hay muchos otros métodos para detectar comunidades. Para obtener una visión general de las: S. Fortunato, « Community detections in graphs », Physics and Society, vol. 2010, no 486, p. 75-174.
3. S. Fortunato et M. Barthélemy, « Resolution limit in community detection », Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no 1, p. 36-41, janv. 2007.
4. V. Blondel, G. Krings, et I. Thomas, « Régions et frontières de téléphonie mobile en Belgique et dans l’aire métropolitaine bruxelloise », Brussels studies, no 42, oct. 2010.
5. P. De Meo, E. Ferrara, G. Fiumara, et A. Provetti, « Generalized Louvain method for community detection in large networks », under review, 2011. URL: http://www.emilio.ferrara.name/wp-content/uploads/2011/07/isda2011-k-path.pdf}
6. R. Rotta et A. Noack, « Multilevel local search algorithms for modularity clustering », Journal of Experimental Algorithmics, vol. 16, no 2.3, 2011.
7. L. Waltman, N. J. van Eck, et E. C. M. Noyons, « A unified approach to mapping and clustering of bibliometric networks », Journal of Infometrics, vol. 4, no 4, p. 629-635, oct. 2010.