Boost Graph Library: BGL existe-t-il un algorithme soigné intégré à BGL pour la détection de communautés?

Question

Quelqu'un utilise-t-il BGL pour les gros serveurs de production?

• De combien de nœuds votre réseau est-il composé?
• Comment gérez-vous la détection de la communauté
• BGL dispose-t-il de méthodes intéressantes pour détecter les communautés?
• Parfois, deux communautés peuvent être liées par un ou deux bords, mais ces bords ne sont pas fiables et peuvent disparaître. Parfois, il n'y a pas d'arête du tout.

Quelqu'un pourrait-il parler brièvement de la façon de résoudre ce problème? S'il vous plaît, ouvrez mon esprit et inspirez-moi.

Jusqu'à présent, j'ai réussi à déterminer si deux nœuds sont situés sur une île (au sein d'une communauté). de manière peu coûteuse, mais je dois maintenant déterminer quels sont les deux nœuds situés sur des îles distinctes qui sont les plus proches l'un de l'autre. Nous ne pouvons que faire un usage minimal de données géographiques peu fiables.

Si nous le comparons au figuré à un continent et à une île et le sortons du contexte de la distance sociale. Je veux déterminer quels sont les deux bouts de terre les plus proches l'un de l'autre dans un plan d'eau.

Answer 1

J'ai utilisé BGL pour les graphiques comportant des millions de nœuds, mais la taille du graphique que vous pouvez utiliser dépend de l'algorithme que vous essayez d'exécuter. Vous pouvez rapidement calculer les distances entre les nœuds. Il existe 4 algorithmes de chemins les plus courts qui s'appliquent le mieux en fonction de vos données: (paires de points uniques, pour toutes les paires de points, graphes clairsemés et denses, ...).

En ce qui concerne la détection de communauté, il n’existe aucun algorithme intégré à BGL spécialement conçu à cet effet (mais vous pouvez peut-être en ajouter un lorsque vous avez terminé votre projet). Quelques algorithmes peuvent être utiles pour créer un algorithme de détection de communauté. Les algorithmes max-flow / min-cut sont généralement utilisés dans la détection de la communauté (s'il y a beaucoup de flux possible entre deux nœuds, alors ils sont susceptibles d'être dans la même communauté, s'il n'y a pas beaucoup de flux, la coupe minimale est susceptible de représenter des routes entre les communautés ). Il existe également des méthodes heuristiques pour ordonner aux nœuds du graphe de réduire bande passante . Nœuds constituant les " communautés " sont susceptibles d'être proches les uns des autres dans un tel ordre.

Answer 2

Pour autant que je sache, BGL n’a aucun algorithme spécifique à la détection de la communauté.

Par "îlot" voulez-vous dire un sous-graphe déconnecté?

De plus, les graphiques n’ont aucune notion de "distance".

Vous devez définir cette "distance sociale". Une fois que vous avez terminé, une grande partie du travail est effectuée.

Il existe de nombreuses méthodes répertoriées sur la page vers laquelle vous êtes lié. La plupart d'entre elles nécessitent simplement de définir quelque chose comme une métrique "distance", puis de brancher vos définitions dans l'algorithme.

@ David Nehme

Les graphiques sans arêtes de poids ne concernent que la connectivité, ils n'ont aucune notion de distance. Si vous voulez parler d'un réseau, vous pouvez parler de distance. Toutefois, un graphique sans poids d'arête n'a pas de distance, sauf si vous souhaitez supposer un poids d'arête implicite de 1 pour tous les bords. Mais cela ne fait que transformer le graphique en réseau.

Il parle également de la distance entre deux graphes déconnectés. Pour modéliser cela, vous devez introduire un concept externe pour la distance entre les nœuds, séparé de la distance de bord.