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.¿Existen implementaciones de algoritmos para la detección de comunidades en gráficos?
Respuesta
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).
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.
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?
También está disponible en Mathematica ahora: https://github.com/szhorvat/IGraphM Todas las funciones de detección de la comunidad están cubiertas. – Szabolcs
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.
- 1. Algoritmos para la detección de isomorfismo subgráfico
- 2. Implementaciones de algoritmos para evaluar circuitos
- 3. Algoritmos de detección de acordes?
- 4. Aprendizaje de algoritmos de gráficos
- 5. implementaciones del mundo real de "algoritmos clásicos"
- 6. Boost Graph Library: ¿Hay algún algoritmo ordenado en BGL para la detección de comunidades?
- 7. implementaciones de "La gramática de gráficos" en paquetes estadísticos
- 8. ¿Algoritmos de detección de imágenes duplicados?
- 9. ¿Guardando gráficos muy grandes en algoritmos de partición de gráficos de disco/transmisión?
- 10. Algoritmos/implementaciones de reconocimiento/identificación de huellas dactilares
- 11. ¿Qué algoritmos determinísticos de recolección de basura existen?
- 12. ¿Existen algoritmos para calcular las rectas de límite de sprites dibujados sobre un fondo monocromático?
- 13. ¿Existen implementaciones de matriz dispersa optimizadas para el almacenamiento en C#?
- 14. implementaciones nth_element Complejidades
- 15. ¿Dónde puedo encontrar software de detección facial, algoritmos, etc.?
- 16. ¿Qué tipo de algoritmos gráficos geniales puedo implementar?
- 17. Entrada de muestra para varios algoritmos
- 18. Algoritmos de gráfico incremental
- 19. ¿Cuál es un buen patrón para almacenar implementaciones de una interfaz y recuperar implementaciones específicas?
- 20. Algoritmos para laberintos 3D
- 21. Existen implementaciones (preferiblemente de código abierto) del modelo "Sociedad de la Mente"
- 22. Biblioteca de Javascript para gráficos (en el sentido matemático)
- 23. Biblioteca de teoría de gráficos para Smalltalk
- 24. biblioteca de gráficos para scala
- 25. ¿Existen algoritmos bien conocidos para contar pasos basados en el acelerómetro?
- 26. ¿Qué patrones temporales existen para neo4j o las bases de datos de gráficos?
- 27. ¿Existe una implementación de la idea se describe en "Detección NearDuplicates de rastreo web"
- 28. ¿Detección de la cara en Android?
- 29. ¿Existen implementaciones de membresía/seguridad más modernas que ASP.NET Membership Provider?
- 30. Guía para principiantes de la programación de gráficos 3D
Ver: [matlab-networks-toolbox] (https://github.com/ivan-brugere/matlab-networks-toolbox) – kenorb