¿Existen implementaciones de algoritmos para la detección de comunidades en gráficos?

Question

Estoy buscando implementaciones de algoritmos de detección de comunidades, como el algoritmo Girvan-Newman (2002). He visitado los sitios web de varios investigadores en este campo (Newman, Santo, etc.) pero no he podido encontrar ningún código. Me imagino que alguien publicó implementaciones de estos algoritmos (¿tal vez incluso un kit de herramientas?), Pero parece que no puedo encontrarlo.

Answer 1

Los algoritmos de detección de comunidad a veces son parte de una biblioteca (como JUNG para java) o una herramienta (consulte Gephi). Cuando los autores publican un nuevo método, a veces hacen que su código esté disponible. Por ejemplo, los métodos Louvain y Infomap.

Nota al margen: El algoritmo de Girvan-Newman a veces todavía se usa, pero en su mayoría ha sido reemplazado por métodos más rápidos y precisos. Para una buena visión general del tema, recomiendo Community detection algorithms: a comparative analysis o el más largo Community detection in graphs (103 páginas).

Answer 2

Puede probar la biblioteca SNAP (Stanford Network Analysis Platform, http://snap.stanford.edu/), que incluye algoritmos Modularity, Girvan-Newman y Clauset-Newman-Moore. Está escrito en C++ y está bajo la licencia BSD. Como lo han usado varios documentos (ver, http://snap.stanford.edu/papers.html), debería ser bueno.

Answer 3

Usted debe echar un vistazo a la igraph library:

• 7 algoritmos de detección de la comunidad (incluyendo aquellos mencionado anteriormente):
  • Edgebetweenness (Girvan-Newman enlace enfoque basado en el carácter central),
  • Walktrap (enfoque basado en el paseo al azar de Pons-Latapy),
  • Leading Eigenvectors (enfoque espectral de Newman),
  • Fast Greedy (Clauset et. al optimización modularidad),
  • Label Propagación (Raghavan et. al),
  • Lovaina (Blondel et. al, optimización modularidad),
  • Spinglass (Reichardt-Bornholdt, optimización de modularidad),
  • InfoMap (Rosvall -Bergstrom, enfoque basado en la compresión).
• otras funciones relacionadas con: la modularidad proceso, se ocupan de las estructuras jerárquicas, etc.
• Disponible en R, C y Python
• de código abierto

Para mi opinión, la herramienta más completa para detección comunitaria Para más detalles, compruebe también: What are the differences between community detection algorithms in igraph?

Answer 4

Hemos puesto en marcha recientemente our algorithm, que se basa en constante Modelo Potts, rápido optimización de Lovaina, y la ecuación mapa fiable de InfoMap para redes ponderados y firmados. Here es el proyecto Java de código abierto + un archivo ejecutable.