Ottimizzazione del codice vettoriale per la adiacenza del grafico

Question

Sto scrivendo del codice di Machine Learning in MATLAB e sto rappresentando un grafico con una matrice di adiacenza A e un raggruppamento del grafico con una matrice Z definita nei modi seguenti.

A: a_ij è 1 se c'è uno spigolo tra il nodo i e il nodo j. 0 altrimenti. Z: z_ij è 1 se il nodo j è nel cluster i. 0 altrimenti.

sto calcolo di una matrice N, che è il numero di spigoli tra cluster, definito nel modo seguente:

N: n_ij è il numero di archi tra i nodi del cluster i e j nodi del cluster. n_ii è il numero di spigoli all'interno del cluster i.

N può essere calcolato:

N = zAz' 

dove z' è z-recepita.

Se ho molti nodi, il calcolo richiede un po 'di tempo, ma non è questo il problema. Il problema è che sposto un sacco di volte i nodi da cluster a cluster, e ogni volta voglio calcolare N.

Quindi il problema è il seguente: Dato che conosco N, e che quindi spostare nodo dal cluster c_1 al cluster c_2, come posso aggiornare N in modo efficiente?

Answer 1

Per passare da Z a Z + U, aggiornare

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

Z e U (e A, se ha senso per il grafico) dovrebbero avere rappresentazioni sparse. In teoria, almeno, questo fa più o meno nel codice compilato cosa farei in C: scansionare i vicini di i, decrementare i conteggi degli edge da e verso il vecchio cluster di i e incrementare i conteggi degli edge da e verso il nuovo cluster di i . In pratica, potrebbe essere necessario trasporre Z per farlo allineare con la rappresentazione di matrice sparse di Matlab e eseguire l'aggiornamento Z ← Z + U sostituendo due intere righe in modo che le voci appena azzerate non vengano trattate come non nerali.