Оптимизация векторизованного кода для смежности графа

Я пишу код машинного обучения в MATLAB, и я представляю граф с матрицей смежности A и кластеризацию графа с матрицей Z, определенной следующими способами.

A: a_ij равно 1, если есть край между узлом i и узлом j. 0 в противном случае. Z: z_ij равно 1, если узел j находится в кластере i. 0 в противном случае.

Я вычисляю матрицу N, которая представляет собой количество ребер между кластерами, определенную следующим образом:

N: n_ij - количество ребер между узлами в кластере i и узлами в кластере j. n_ii - количество ребер внутри кластера i.

N можно вычислить следующим образом:

N = zAz'

где z 'транспонировано по z.

Если у меня много узлов, то вычисление займет некоторое время, но проблема не в этом. Проблема в том, что я перемещаю узлы из кластера в кластер много раз, и каждый раз, когда я хочу вычислить N.

Итак, проблема заключается в следующем: учитывая, что я знаю N и затем перемещаю узел i из кластера c_1 в кластер c_2, как я могу эффективно обновить N?

6
задан Amro 2 May 2012 в 13:59
поделиться