Existe-t-il des implémentations d'algorithmes de détection communautaire dans les graphiques? [fermé]
je suis à la recherche d'implémentations d'algorithmes de détection de communauté, comme L'algorithme de Girvan-Newman (2002). J'ai visité les sites web de plusieurs chercheurs dans ce domaine (Newman, Santo, etc.), mais a été incapable de trouver le code. J'imagine que quelqu'un a publié des implémentations de ces algorithmes (peut-être même une boîte à outils?), mais je n'arrive pas à le trouver.
4 réponses
les algorithmes de détection de communauté font parfois partie d'une bibliothèque (comme JUNG pour java) ou d'un outil (voir Gephi ). Lorsque les auteurs publient une nouvelle méthode, ils mettent parfois leur code à disposition. Par exemple, les méthodes Louvain et Infomap .
Side note: L'algorithme de Girvan-Newman est parfois encore utilisé, mais il a été remplacé la plupart du temps par plus rapide et plus précise méthodes. Pour une bonne vue d'ensemble du sujet, je recommande Community detection algorithms: a comparative analysis ou le plus long Community detection in graphs (103 pages).
vous devriez jeter un oeil à la bibliothèque igraph :
- 7 algorithmes de détection de la communauté (y compris ceux mentionnés ci-dessus)):
- Edgebetweenness (Girvan-Newman lien de centralité),
- Walktrap (Pons-Latapy marche aléatoire),
- à la tête de Vecteurs propres (Newman approche spectrale),
- Fast Greedy (Clauset et. Al la modularité de l'optimisation),
- Label Propagation (Raghavan et. al),
- Louvain (Blondel et. al, optimisation de la modularité),
- Spinglass (Reichardt-Bornholdt, l'optimisation de la modularité),
- InfoMap (Rosvall-Bergstrom, en fonction de compression de l'approche).
- autres fonctions connexes: modularité des processus, traitement des structures hiérarchiques, etc.
- disponible en R, C et Python
- Open source
à mon avis, l'outil le plus complet pour la détection communautaire. Pour plus de détails, voir aussi: quelles sont les différences entre les algorithmes de détection communautaire dans igraph?
vous pouvez essayer la bibliothèque SNAP (Stanford Network Analysis Platform, http://snap.stanford.edu / ), qui inclut les algorithmes de modularité, Girvan-Newman et Clauset-Newman-Moore. Il est écrit en C++, et est sous la licence BSD. Comme un certain nombre de documents ont utilisé (voir, http://snap.stanford.edu/papers.html ), il devrait être bon.
nous avons récemment mis en œuvre notre algorithme , qui est basé sur le modèle constant Potts, l'optimisation rapide de Louvain, et l'équation fiable de carte D'InfoMap pour les réseaux pondérés et signés. Ici est l'open source java du projet + un exécutable jar.