¿Hay implementaciones de algoritmos para la detección de la comunidad en gráficos? [cerrado]

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

Author: River, 2011-04-28
Source

4 answers

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

Nota al margen: El algoritmo 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 algoritmos: un análisis comparativo o la detección más larga de la comunidad en gráficos (103 páginas).

 37
Author: job,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-28 18:50:16

Deberías echar un vistazo a la biblioteca igraph :

  • 7 algoritmos de detección de la comunidad (incluidos los mencionados anteriormente):
    • Edgebetweenness (enfoque basado en la centralidad del enlace Girvan-Newman),
    • Walktrap (Pons-Latapy random walk-based approach),
    • Vectores propios principales (enfoque espectral de Newman),
    • Fast Greedy (Clauset et. al modularity optimization),
    • Propagación de etiquetas (Raghavan et. al),
    • Lovaina (Blondel et. al, optimización de modularidad),
    • Spinglass (Reichardt-Bornholdt, optimización de modularidad),
    • InfoMap (Rosvall-Bergstrom, enfoque basado en compresión).
  • Otras funciones relacionadas: modularidad del proceso, manejo de estructuras jerárquicas, etc.
  • Disponible en R, C y Python
  • Código abierto

En mi opinión, la herramienta más completa para la detección comunitaria. Para más detalles, también consulte: ¿Cuáles son las diferencias entre la comunidad ¿algoritmos de detección en igraph?

 25
Author: Vincent Labatut,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:09:37

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

 6
Author: Lingxi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-04-28 02:20:26

Recientemente hemos implementado nuestro algoritmo, que se basa en el Modelo Potts Constante, la optimización rápida de Lovaina y la ecuación de mapa confiable de InfoMap para redes ponderadas y firmadas. Aquí está el proyecto java de código abierto + un jar ejecutable.

 1
Author: P. Esmailian,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-02-13 16:45:50