Gráfico de algoritmos de clustering que considere la posibilidad de pesos negativos

Question

Tengo un gráfico de ejemplo con la ponderación dirigida a los bordes, que los valores pueden estar en el rango [-1,1]. Necesito hacer agrupación en clústeres en este gráfico, con el fin de encontrar grupos en los que los vértices están más correlacionados.

He buscado por varios agrupación o comunidad de detección en el gráfico basado en algoritmos, pero la mayoría de ellos no funcionan debido a la negativa de pesos. Hasta ahora he aplicado spinglass (se llama así en igraph de la biblioteca, es un algoritmo basado en el modelo de Potts) algoritmo que parece funcionar con ambos positivos y negativos de pesos.

Hay otros algoritmos para realizar la agrupación o comunidad de detección en los gráficos que tienen efectos negativos y positivos de borde de pesos?

Actualización: el borde de pesos representan las correlaciones, 1 significa que dos vértices están fuertemente correlacionados, -1 que están inversamente correlacionados y 0 significa que son independientes.

Answer 1

¿Has probado la asignación de los valores en [0;2]?

Luego de muchos algoritmos pueden trabajar.

Por ejemplo, considere la posibilidad de Dijkstra: se requiere no negativo borde de pesos, pero si usted sabe que el mínimo a de los bordes, se puede ejecutar en x-a y obtener el menor ciclo-ruta libre.

Actualización: para los valores de correlación, usted puede estar interesado en los valores absolutos abs(x) (que es la fuerza de la correlación!) o puede que quiera romper el gráfico en dos temporal: primer clúster en las correlaciones positivas sólo, a continuación, en las correlaciones negativas sólo si el signo es eso importante para la agrupación y los planteamientos anteriores no funcionan.

Answer 2

Sí, hay un algoritmo llamado 'la Propagación de Afinidad" que trabaja con pesos negativos; creo que este es implementado en sklearn (consulte la documentación de aquí). Una referencia de lo que está pasando detrás de las escenas se puede encontrar aquí.

La esperanza de que lo que usted está buscando!

Answer 3

A mí me parece que el problema que usted describe es conocida como la Correlación de la Agrupación Problema. Esta información debería ayudar a encontrar algunas implementaciones, tales como:

• Este código de Matlab por Shai Bagon
• Este código de Python por GitHub usuario filkry

Nota: algunos de la comunidad de algoritmos de detección también se han modificado con el fin de procesar firmado redes, por ejemplo, Amelio'13, Sharma'12, Anchuri'12, etc. Sin embargo, no podía encontrar ningún públicamente disponible la aplicación.