Gráfica de algoritmos de agrupación que consideran pesos negativos

8

Tengo una instancia de gráfico con bordes dirigidos ponderados cuyos valores pueden estar en el rango [-1,1]. Necesito agrupar en este gráfico, para encontrar grupos en los que los vértices están más correlacionados.

Busqué varios algoritmos basados ​​en gráficos de agrupación o de detección comunitaria, pero la mayoría de ellos no funcionan debido a los pesos negativos. Hasta ahora he aplicado el algoritmo spinglass (se llama así en la biblioteca igraph , es un algoritmo basado en el modelo de Potts) que parece funcionar con pesos positivos y negativos.

¿Existen otros algoritmos para agrupar o detectar comunidades en gráficos que tienen pesos de borde negativos y positivos?

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

Ewybe
fuente
¿Qué representan los pesos?
eliasah
@eliasah Hice una actualización para explicar eso
Ewybe
¿Intentaste usar otra escala? Esa podría ser una buena solución utilizando un método de agrupación regular basado en el algoritmo de centralidad intermedia por ejemplo.
eliasah
@eliasah Escalar estos datos puede que no sea tan fácil porque estoy interesado en preservar el significado de la correlación
Ewybe
1
Para el agrupamiento, ¿es realmente necesario el signo de la correlación? La correlación inversa también es una relación bastante fuerte . Vea mi respuesta a continuación.
HA SALIDO - Anony-Mousse

Respuestas:

2

¿Has intentado asignar los valores a [0; 2]?

Entonces muchos algoritmos pueden funcionar.

Considere, por ejemplo, Dijkstra: requiere pesos de borde no negativos, pero si conoce el mínimo ade los bordes, puede ejecutarlo x-ay obtener la ruta sin ciclo más corta.

Actualización: para los valores de correlación, puede estar interesado en los valores absolutos abs(x)(¡que es la fuerza de la correlación!) O es posible que desee dividir el gráfico en dos temporalmente: primero en las correlaciones positivas, luego en las correlaciones negativas solo si el signo es tan importante para la agrupación y los enfoques anteriores no funcionan.

HA SALIDO - Anony-Mousse
fuente
Eso es de alguna manera lo que he sugerido, dijo que "perderá el significado de la correlación". ¿Qué piensas sobre eso?
eliasah
Con su descripción actualizada, abs (x) puede funcionar aún mejor.
HA SALIDO - Anony-Mousse
Sin embargo, creo que [0,2] es más representativo. Grafos ponderados por lo general tienen importancia muy grande sobre estos asuntos a la centralidad de cómputo, distancia, diámetro, etc.
eliasah
1
Eso no significa que no puedas discriminar después. ¿Lo has probado , los resultados aún pueden ser útiles?
HA SALIDO - Anony-Mousse
1
Luego intente con el otro enfoque: encontrar grupos positivos y negativos por separado.
HA SALIDO - Anony-Mousse
1

Sí, hay un algoritmo llamado 'Propagación de afinidad' que funciona con pesos negativos; Creo que esto se implementa en sklearn (consulte la documentación aquí ). Una referencia de lo que está sucediendo detrás de escena se puede encontrar aquí .

¡Espero que sea lo que estás buscando!

squattyroo
fuente
No conocía este algoritmo, parece ser una buena solución. Ciertamente lo intentaré. Gracias.
Ewybe
Hasta donde yo sé, la agrupación de Propagación de afinidad no podrá considerar simultáneamente correlaciones positivas y negativas al tiempo que las separa. Para el caso, creo que la tarea es contradictoria.
micans
0

Me parece que el problema que describe se conoce como el problema de agrupación de correlación . Esta información debería ayudarlo a encontrar algunas implementaciones, como:

Tenga en cuenta algunos algoritmos de detección de la comunidad también han sido modificados con el fin de procesar las redes firmados, por ejemplo Amelio'13 , Sharma'12 , Anchuri'12 , etc. Sin embargo, no pude encontrar ninguna aplicación a disposición del público.

Vincent Labatut
fuente
0

Eche un vistazo a este código , es bastante escalable, funciona con bordes positivos y negativos y resuelve el grupo de correlación (CC) como un caso especial (r = 0). Sin embargo, para el caso de CC (maximizando los enlaces positivos y minimizando los enlaces negativos dentro de los clústeres), sugeriría otros métodos que están especializados en resolver este objetivo.

Para ilustrar, la agrupación de correlaciones (a diferencia de lo que persigue la literatura sobre detección comunitaria) no tiene en cuenta la densidad positiva de las agrupaciones, por lo que cuando una red tiene pocos vínculos negativos (la mayoría de los casos del mundo real), toda la red se coloca en una sola racimo.

Esmailian
fuente