了解 cuthill mckee 聚类

Question

我正在尝试通过 Cuthill-McKee 减少图形邻接矩阵中条目的带宽 算法。

我有以下输入图，我可以得到排列顺序。

import networkx as nx
import matplotlib.pyplot as plt
from networkx.utils import reverse_cuthill_mckee_ordering, cuthill_mckee_ordering

G = nx.gnm_random_graph(n=30, m=55, seed=1)
nxpos = nx.spring_layout(G, dim=2, iterations=10000)
nx.set_node_attributes(G, nxpos, 'pos')
rcm = list(cuthill_mckee_ordering(G))
        

接下来，我重新标记了原始图的节点

d = OrderedDict(zip(G.nodes(), rcm))
H = nx.relabel_nodes(G, mapping=d)
H_adj = nx.adjacency_matrix(H, nodelist=range(len(H.nodes())))
plt.spy(H_adj)
plt.show()

不幸的是，邻接矩阵H_adj没有带状

另一方面，当我尝试以下时 G_adj_rcm 是带状的。

 G_adj_rcm = nx.adjacency_matrix(G, nodelist=rcm)
 plt.spy(G_adj_rcm)
 plt.show()

我不确定重新标记是否不正确，或者我是否无法理解算法的工作原理。澄清为什么 H_adj 没有被带状排列会有很大帮助。

Answer 1

你的重新标记是错误的。您需要根据节点在 rcm 中的位置重新标记节点。以下映射有效。

import networkx as nx
import matplotlib.pyplot as plt
from networkx.utils import cuthill_mckee_ordering
G = nx.gnm_random_graph(n=30, m=55, seed=1)
rcm = list(cuthill_mckee_ordering(G))

d = {node:rcm.index(node) for node in G}
H = nx.relabel_nodes(G, mapping=d)
H_adj = nx.adjacency_matrix(H,nodelist=range(30))
plt.spy(H_adj)
plt.show()