algorithm - 优化图形邻接的矢量化代码

Question

我正在 MATLAB 中编写一些机器学习代码，我正在用邻接矩阵 A 表示一个图，并用按以下方式定义的矩阵 Z 对图进行聚类。

A:如果节点 i 和节点 j 之间存在边，则 a_ij 为 1。 0 否则。Z:如果节点 j 在簇 i 中，则 z_ij 为 1。 0 否则。

我正在计算一个矩阵 N，它是簇之间的边数，按以下方式定义:

N:n_ij 是簇 i 中的节点与簇 j 中的节点之间的边数。 n_ii 是簇 i 内的边数。

N 可以通过以下方式计算:

N = zAz'

其中 z' 是 z 转置的。

如果我有很多节点，那么计算这个需要一些时间，但这不是问题。问题是，我多次将节点从一个集群移动到另一个集群，并且每次我都想计算 N。

所以问题如下:假设我知道 N，然后我将节点 i 从集群 c_1 移动到集群 c_2，我如何才能以有效的方式更新 N？

Answer 1

要从 Z 到 Z + U，更新

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

Z 和 U(以及 A，如果它对您的图形有意义)应该具有稀疏表示。至少在理论上，这或多或少地在编译代码中做了我在 C 中会做的事情:扫描 i 的邻居，将边数递减到 i 的旧簇和从 i 的旧簇递增边数到从我的新集群。在实践中，您可能需要转置 Z 以使其与 Matlab 的稀疏矩阵表示正确对齐，并通过替换两整行来执行更新 Z ← Z + U，以便新归零的条目不会被视为非零。