如何利用NetworkX识别图节点的对称等价组及生成置换映射？

结论：ISMAGS.analyze_symmetry完全满足你的需求 #

ISMAGS模块专门用于计算图的自同构群——也就是能让图在结构和节点属性上完全不变的节点置换集合，正好对应你要的“置换后得到完全相同的图”的对称映射，同时能输出节点的对称等价组（自同构轨道）。

具体实现步骤与代码示例 #

1. 构建带颜色属性的无向图

先创建一个示例图，给节点添加color属性：

import networkx as nx

# 创建无向图
G = nx.Graph()
# 添加节点及颜色属性
nodes = [
    (1, {"color": "red"}),
    (2, {"color": "blue"}),
    (3, {"color": "blue"}),
    (4, {"color": "green"}),
    (5, {"color": "red"}),
    (6, {"color": "red"})
]
G.add_nodes_from(nodes)
# 添加边
edges = [(1,2), (1,3), (4,5), (4,6), (2,4), (3,4)]
G.add_edges_from(edges)

2. 初始化ISMAGS匹配器并分析对称

通过指定节点属性匹配规则，确保只有同颜色的节点才能被置换：

from networkx.algorithms.isomorphism import ISMAGS

# 定义节点匹配规则：颜色相同则匹配
node_match = lambda n1, n2: n1["color"] == n2["color"]
# 初始化ISMAGS对象
ismags = ISMAGS(G, node_match=node_match)
# 分析对称，获取自同构群信息
symmetry_info = ismags.analyze_symmetry()

3. 提取对称等价组与映射

• 对称等价组（轨道）：symmetry_info["orbits"]会返回按等价关系分组的节点列表，同一组内的节点可以互相置换而不改变图：

  print("对称等价组:", symmetry_info["orbits"])
  # 示例输出可能是: [[1], [2, 3], [4], [5, 6]]
  

• 对称映射（自同构生成元）：symmetry_info["generators"]会返回生成自同构群的基础置换映射，比如你提到的{2:3}、{5:6}这类：

  print("对称映射生成元:", symmetry_info["generators"])
  # 示例输出可能是: [{2: 3, 3: 2}, {5: 6, 6: 5}]
  

  所有可能的对称映射都是这些生成元的组合（比如同时置换2↔3和5↔6）。

4. 用置换生成新图

使用nx.relabel_nodes函数，传入目标置换映射即可生成新图：

# 比如用置换{2:3, 3:2}生成新图
perm = {2:3, 3:2}
G_permuted = nx.relabel_nodes(G, perm, copy=True)

# 验证新图与原图完全一致（结构+属性）
print(nx.is_isomorphic(G, G_permuted, node_match=node_match))  # 输出True

关键说明 #

• ISMAGS的analyze_symmetry会自动考虑你定义的节点属性匹配规则，只有属性（颜色）相同的节点才会被纳入同一等价组或置换映射中。
• 自同构群的生成元是最小的置换集合，通过组合这些生成元可以得到所有可能的对称映射。

内容的提问来源于stack exchange，提问作者S R Maiti