Algoritmo de agrupamiento de gráficos eficiente

19

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 JUNG pero es bastante lento cuando intento eliminar muchos bordes.

¿Puede sugerirme una mejor alternativa para gráficos grandes?

    
pregunta mariosangiorgio 19.01.2012 - 10:44

3 respuestas

12

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

propagación por afinidad es otra opción viable, pero parece menos consistente que el agrupamiento de Markov .

Hay varias otras opciones, pero estas dos son buenas y se adaptan bien al problema específico de agrupar 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 utiliza una métrica adecuada.

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

    
respondido por el Nathan Rice 19.01.2012 - 15:30
9

Agrupación jerárquica

Esto me lo recomendó un amigo. Según 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 de coseno, el índice de Jaccard y la distancia de Hamming entre filas de la matriz de adyacencia. Luego, se agrupan nodos similares en comunidades según esta medida. Existen varios esquemas comunes para realizar la agrupación, siendo los dos más simples la agrupación en 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 completa de enlaces , en el que todos los nodos dentro de cada grupo tienen una similitud mayor que el umbral.

Markov Cluster

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, por falta de un término mejor, extremadamente "poderoso". Pruébalo y verás.

    
respondido por el Dynamic 22.01.2012 - 22:47
5

Para su problema aquí, creo que debería pensar en una manera de asignar los 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á en el valor con el que necesita trabajar para esa dimensión en particular. Después de eso, podrías hacer una simple distancia de Euclid y trabajar con eso.

    
respondido por el viki.omega9 19.01.2012 - 11:52

Lea otras preguntas en las etiquetas