Optimizando el código vectorizado para la adyacencia de gráficos

Question

Estoy escribiendo algunos códigos de Aprendizaje automático en MATLAB, y estoy representando un gráfico con una matriz de adyacencia A, y un agrupamiento del gráfico con una matriz Z definida de las siguientes maneras.

A: a_ij es 1 si hay un borde entre el nodo iy el nodo j. 0 de lo contrario. Z: z_ij es 1 si el nodo j está en el grupo i. 0 de lo contrario.

Estoy calcular una matriz de N, que es el número de aristas entre las agrupaciones, que se define de la siguiente manera:

N: n_ij es el número de aristas entre los nodos en el grupo I y nodos en el grupo j. n_ii es el número de bordes dentro del cluster i.

N se puede calcular por:

N = zAz' 

donde z' es-z transpuesta.

Si tengo muchos nodos, entonces calcular esto lleva algo de tiempo, pero ese no es el problema. El problema es que muevo los nodos del clúster al clúster muchas veces, y cada vez que quiero calcular N.

Así que el problema es el siguiente: dado que sé N, y que luego muevo el nodo i del clúster c_1 al clúster c_2, ¿cómo puedo actualizar N de manera eficiente?

Answer 1

para ir de Z a Z + U, actualizar

N ← N + 'Z (UA) + Z (AU)' + UAU'
Z ← Z + U.

Z y U (y A, si tiene sentido para su gráfico) deberían tener representaciones dispersas. En teoría, al menos, esto hace más o menos en el código compilado lo que haría en C: escanear los vecinos de i, disminuyendo los recuentos de bordes hacia y desde el clúster anterior e incrementando los recuentos de bordes hacia y desde el nuevo clúster de i . En la práctica, es posible que necesite transponer Z para alinearlo correctamente con la representación de matriz dispersa de Matlab y ejecutar la actualización Z ← Z + U reemplazando dos filas completas para que las entradas recién puestas a cero no se traten como distintas de cero.