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

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

6 голосов
/ 04 марта 2012

Я пишу некоторый код машинного обучения в 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?

1 Ответ

2 голосов
/ 04 марта 2012

Чтобы перейти от Z к Z + U, обновите

N & larr; N + Z (AU ') + (UA) Z' + UAU '
Z & larr; Z + U.

Z и U (и A, если это имеет смысл для вашего графа) должны иметь разреженные представления. Теоретически, по крайней мере, это делает более или менее в скомпилированном коде , что я бы делал в C: сканировать соседние элементы i, уменьшая счетчик ребер до старого кластера i и увеличивая счетчик ребер до и из нового кластера. На практике вам может понадобиться транспонировать Z, чтобы выровнять его с правильным представлением разреженной матрицы Matlab и выполнить обновление Z & larr; Z + U путем замены двух целых строк, чтобы вновь обнуленные записи не обрабатывались как ненулевые.

...