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)