Sto cercando un algoritmo efficiente per trovare cluster su un grande grafico (ha circa 5000 vertici e 10000 spigoli).
Finora utilizzo l'algoritmo Girvan-Newman implementato nella libreria java JUNG ma è piuttosto lento quando tento di rimuovere molti bordi.
Puoi suggerirmi un'alternativa migliore per i grafici di grandi dimensioni?
Personalmente suggerisco clustering Markov . L'ho usato diverse volte in passato con buoni risultati.
La propagazione dell'affinità è un'altra opzione praticabile, ma sembra meno coerente del clustering Markov .
Ci sono varie altre opzioni, ma queste due sono buone e pronte per il problema specifico dei grafici di clustering (che puoi vedere come matrici sparse). Anche la misura della distanza che stai utilizzando è una considerazione. La tua vita sarà più facile se utilizzi una metrica appropriata.
Ho trovato questo documento mentre cercavo i benchmark delle prestazioni, è una buona indagine sull'argomento .
Questo mi è stato consigliato da un amico. Secondo Wikipedia :
In this method one defines a similarity measure quantifying some (usually topological) type of similarity between node pairs. Commonly used measures include the cosine similarity, the Jaccard index, and the Hamming distance between rows of the adjacency matrix. Then one groups similar nodes into communities according to this measure. There are several common schemes for performing the grouping, the two simplest being single-linkage clustering, in which two groups are considered separate communities if and only if all pairs of nodes in different groups have similarity lower than a given threshold, and complete linkage clustering, in which all nodes within every group have similarity greater than threshold.
Questo è quello che uso nella tua situazione. È un algoritmo molto utile. Ho trovato un collegamento a un bel PDF sull'algoritmo. È un ottimo algoritmo e, per mancanza di un termine migliore, estremamente "potente". Provalo e vedi.
Per il tuo problema qui, penso che dovresti pensare a un modo per mappare i vertici-bordi a un insieme di coordinate per ogni vertice. Non sono sicuro se c'è un modo migliore per farlo. Ma, penso che potresti iniziare rappresentando ciascun vertice come una dimensione e quindi, il valore del bordo per un particolare vertice diventerebbe il valore con cui dovrai lavorare per quella particolare dimensione. Dopo potrai fare una semplice distanza Euclide e lavorare con quello.
Leggi altre domande sui tag algorithms graph cluster