utd*_*ant 6 algorithm optimization matlab graph-theory matrix
我正在MATLAB中编写一些机器学习代码,我用一个邻接矩阵A表示一个图形,并用以下列方式定义矩阵Z的图形聚类.
答:如果节点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？
要从 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，以便新归零的条目不会被视为非零。