Algoritmo eficiente de agrupación de gráficos

Estoy buscando un algoritmo eficiente para encontrar grupos en un gráfico grande (tiene aproximadamente 5000 vértices y 10000 bordes).

Hasta ahora estoy usando el algoritmo Girvan-Newman implementado en la biblioteca Java de JUNG, pero es bastante lento cuando intento eliminar muchos bordes.

¿Me puede sugerir una mejor alternativa para gráficos grandes?

Yo personalmente sugiero la agrupación de Markov . Lo he usado varias veces en el pasado con buenos resultados.

La propagación de afinidad es otra opción viable, pero parece menos consistente que la agrupación de Markov.

Hay varias otras opciones, pero estas dos son buenas desde el primer momento y se adaptan bien al problema específico de la agrupación de gráficos (que puede ver como matrices dispersas). La medida de distancia que está utilizando también es una consideración. Su vida será más fácil si está utilizando una métrica adecuada.

Encontré este documento mientras buscaba puntos de referencia de rendimiento, es una buena encuesta sobre el tema.

Agrupación jerárquica

Esto me lo recomendó un amigo. De acuerdo con Wikipedia :

En este método, se define una medida de similitud que cuantifica algún tipo (generalmente topológico) de similitud entre pares de nodos. Las medidas de uso común incluyen la similitud del coseno, el índice Jaccard y la distancia de Hamming entre las filas de la matriz de adyacencia. Luego se agrupan nodos similares en comunidades de acuerdo con esta medida. Existen varios esquemas comunes para realizar la agrupación, los dos más simples son la agrupación de un solo enlace, en la que dos grupos se consideran comunidades separadas si y solo si todos los pares de nodos en diferentes grupos tienen una similitud menor que un umbral dado, y la agrupación de enlaces completa , en el que todos los nodos dentro de cada grupo tienen una similitud mayor que el umbral.

Racimo de Markov

Esto es lo que uso en tu situación. Es un algoritmo muy útil. Encontré un enlace a un buen PDF sobre el algoritmo. Es un gran algoritmo y, a falta de un término mejor, extremadamente "poderoso". Pruébalo y verás.

Para su problema aquí, creo que debería pensar en una forma de asignar vértices-bordes a un conjunto de coordenadas para cada vértice. No estoy seguro de si hay una mejor manera de hacer esto. Pero, creo que podría comenzar representando cada vértice como una dimensión y luego, el valor de borde de un vértice particular se convertiría en el valor con el que necesita trabajar para esa dimensión particular. Después de eso, podría hacer una simple distancia de Euclides y trabajar con eso.