Algorithme de regroupement de graphes efficace

Je cherche un algorithme efficace pour trouver des clusters sur un grand graphe (il a environ 5000 sommets et 10000 arêtes).

Jusqu'à présent, j'utilise l'algorithme Girvan – Newman implémenté dans la bibliothèque Java JUNG mais il est assez lent lorsque j'essaie de supprimer beaucoup d'arêtes.

Pouvez-vous me proposer une meilleure alternative pour les grands graphiques?

Je suggère personnellement le clustering de Markov . Je l'ai utilisé plusieurs fois dans le passé avec de bons résultats.

La propagation d'affinité est une autre option viable, mais elle semble moins cohérente que le clustering de Markov.

Il existe diverses autres options, mais ces deux sont prêtes à l'emploi et bien adaptées au problème spécifique des grappes de grappes (que vous pouvez visualiser comme des matrices clairsemées). La mesure de distance que vous utilisez est également une considération. Votre vie sera plus facile si vous utilisez une métrique appropriée.

J'ai trouvé cet article en cherchant des repères de performance, c'est un bon aperçu du sujet.

Classification hiérarchique

Cela m'a été recommandé par un ami. Selon Wikipedia :

Dans cette méthode, on définit une mesure de similitude quantifiant un type (généralement topologique) de similitude entre les paires de nœuds. Les mesures couramment utilisées incluent la similitude cosinus, l'indice de Jaccard et la distance de Hamming entre les lignes de la matrice d'adjacence. Ensuite, on regroupe des nœuds similaires en communautés selon cette mesure. Il existe plusieurs schémas communs pour effectuer le regroupement, les deux plus simples étant le clustering à liaison unique, dans lequel deux groupes sont considérés comme des communautés distinctes si et seulement si toutes les paires de nœuds dans des groupes différents ont une similitude inférieure à un seuil donné, et un clustering de liaison complet , dans lequel tous les nœuds de chaque groupe ont une similitude supérieure au seuil.

Cluster de Markov

C'est ce que j'utilise dans votre situation. C'est un algorithme très utile. J'ai trouvé un lien vers un joli PDF sur l'algorithme. C'est un excellent algorithme et, à défaut d'un meilleur terme, extrêmement "puissant". Essayez-le et voyez.

Pour votre problème ici, je pense que vous devriez penser à un moyen de mapper les sommets-bords à un ensemble de coordonnées pour chaque sommet. Je ne sais pas s'il existe une meilleure façon de procéder. Mais, je pense que vous pourriez commencer par représenter chaque sommet comme une dimension, puis la valeur de l'arête d'un sommet particulier deviendrait la valeur avec laquelle vous devez travailler pour cette dimension particulière. Après cela, vous pourriez faire une distance Euclide simple et travailler avec cela.