Algoritmo eficiente de agrupamento de gráficos

Estou procurando um algoritmo eficiente para encontrar clusters em um gráfico grande (ele possui aproximadamente 5000 vértices e 10.000 arestas).

Até agora, estou usando o algoritmo Girvan-Newman implementado na biblioteca java JUNG, mas é bastante lento quando tento remover muitas arestas.

Você pode me sugerir uma alternativa melhor para gráficos grandes?

Eu pessoalmente sugiro o agrupamento de Markov . Eu usei várias vezes no passado com bons resultados.

A propagação de afinidade é outra opção viável, mas parece menos consistente do que o cluster Markov.

Existem várias outras opções, mas essas duas são prontas para uso e adequadas ao problema específico dos gráficos de cluster (que você pode visualizar como matrizes esparsas). A medida de distância que você está usando também é uma consideração. Sua vida será mais fácil se você estiver usando uma métrica adequada.

Eu encontrei este artigo enquanto procurava referências de desempenho, é uma boa pesquisa sobre o assunto.

Agrupamento hierárquico

Isso me foi recomendado por um amigo. De acordo com a Wikipedia :

Neste método, define-se uma medida de similaridade quantificando algum tipo (geralmente topológico) de similaridade entre pares de nós. As medidas comumente usadas incluem a semelhança de cosseno, o índice de Jaccard e a distância de Hamming entre as linhas da matriz de adjacência. Em seguida, agrupa-se nós semelhantes nas comunidades de acordo com essa medida. Existem vários esquemas comuns para executar o agrupamento, sendo os dois mais simples o clustering de ligação única, em que dois grupos são considerados comunidades separadas se e somente se todos os pares de nós em grupos diferentes tiverem similaridade menor que um determinado limite e o clustering de link completo , em que todos os nós em cada grupo têm semelhança maior que o limite.

Markov Cluster

É isso que eu uso na sua situação. É um algoritmo muito útil. Encontrei um link para um bom PDF sobre o algoritmo. É um ótimo algoritmo e, por falta de um termo melhor, extremamente "poderoso". Tente e veja.

Para o seu problema aqui, acho que você deve pensar em uma maneira de mapear vértices-arestas para um conjunto de coordenadas para cada vértice. Não tenho certeza se existe uma maneira melhor de fazer isso. Mas acho que você poderia começar representando cada vértice como uma dimensão e, em seguida, o valor da aresta de um vértice específico se tornaria o valor com o qual você precisa trabalhar para essa dimensão específica. Depois disso, você poderia fazer uma distância Euclid simples e trabalhar com isso.