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.