graph - harary - ¿Hay implementaciones de algoritmos para la detección de comunidades en gráficos?
graph theory harary (4)
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.
Deberías echarle un vistazo a la biblioteca igraph :
- 7 algoritmos de detección de comunidades (incluidos los mencionados anteriormente):
- Edgebetweenness (enfoque basado en la centralidad del enlace Girvan-Newman),
- Walktrap (enfoque basado en el paseo aleatorio Pons-Latapy),
- Eigenvectores principales (enfoque espectral de Newman),
- Fast Greedy (Clauset et al al optimización de la modularidad),
- Propagación de etiquetas (Raghavan et al.)
- Louvain (Blondel y otros, optimización de la modularidad),
- Spinglass (Reichardt-Bornholdt, optimización de la modularidad),
- InfoMap (Rosvall-Bergstrom, enfoque basado en la compresión).
- Otras funciones relacionadas: modularidad del proceso, tratar con estructuras jerárquicas, etc.
- Disponible en R, C y Python
- Fuente abierta
En mi opinión, la herramienta más completa para la detección de la comunidad. Para más detalles, también verifique: ¿Cuáles son las diferencias entre los algoritmos de detección de comunidades en igraph?
Los algoritmos de detección de comunidades 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 hacen que su código esté disponible. Por ejemplo, los métodos de Louvain e 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 obtener una buena visión general del tema, recomiendo los algoritmos de detección de la comunidad: un análisis comparativo o la detección comunitaria más larga en gráficos (103 páginas).
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 periódicos (ver, http://snap.stanford.edu/papers.html ), debería ser bueno.
Recientemente hemos implementado nuestro algoritmo , que se basa en el modelo de Constant Potts, la rápida optimización de Louvain y la ecuación de mapa confiable de InfoMap para redes ponderadas y firmadas. Here está el proyecto Java de código abierto + un archivo ejecutable.