gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:43:04 24 4
gpt4 key购买 nike

我正在 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?

最佳答案

要从 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,以便新归零的条目不会被视为非零。

关于algorithm - 优化图形邻接的矢量化代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9549427/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com