Algorithme de regroupement de graphes efficace

20

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?

mariosangiorgio
la source
Avez-vous regardé k-means?
Odé le
Pouvez-vous s'il vous plaît me donner quelques références pour savoir comment l'utiliser sur un graphique?
mariosangiorgio
Je suis passé à l'implémentation JUNG du VoltageClusterer et c'est définitivement rapide. jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/…
mariosangiorgio
1
N'est-ce pas plus approprié pour < cs.stackexchange.com > car il s'agit plus d'informatique que d'ingénieur logiciel?
Oeufcoque Penteano

Réponses:

13

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.

Nathan Rice
la source
Merci, je vais jeter un œil à tous les algorithmes que vous avez suggérés.
mariosangiorgio
Correction: ces algorithmes ont besoin de poids d'entrée qui reflètent la similitude et non la distance. La propriété métrique (inégalité du triangle) n'y entre pas. Il peut être utile de transformer les poids afin qu'ils tombent dans une plage naturelle, par exemple pour les corrélations (Pearson) comme décrit ici ( micans.org/mcl/man/clmprotocols.html#array ), et pour les valeurs E BLAST comme décrit ici ( micans.org/mcl/man/clmprotocols.html#blast ).
micans
10

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.

Dynamique
la source
5

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.

viki.omega9
la source
1
Après avoir lu un peu, j'ai trouvé ceci, ici et je pense que vous devriez y jeter un œil.
viki.omega9