当前位置：文江博客话题详情

消除图形的对称性

发布于 2024-10-17 22:45:18 字数 1226 浏览 2 评论 0原文

我有一个算法问题，其中我导出了许多状态之间的转移矩阵。下一步是对其求幂，但它非常大，所以我需要对其进行一些缩减。具体来说，它包含很多对称性。下面是一些关于通过简单观察可以消除多少个节点的示例。

我的问题是是否有一种算法可以有效消除有向图中的对称性，类似于我在下面手动完成的方式。

在所有情况下，所有节点的初始向量具有相同的值。

在第一个示例中，我们看到 b、c、d 和 e 都从 a 接收值 并且彼此之一。因此它们总是包含相同的值，我们可以合并它们。

有向图 A Digraph B

在此示例中，我们很快发现，从 a、<代码>b、<代码>c和<代码>d。同样对于它们各自的侧节点来说，它附加到哪个内部节点并不重要。因此我们可以将图减少到只有两种状态。

有向图 C Digraph D

更新： 有些人很合理，不太确定“状态转移”是什么意思矩阵”。这里的想法是，您可以将组合问题拆分为递归中每个 n 的多个状态类型。然后，矩阵会告诉您如何从 n-1 到 n。

通常你只对其中一个状态的值感兴趣，但你也需要计算其他状态，这样你总是可以进入下一个级别。然而，在某些情况下，多个状态是对称的，这意味着它们始终具有相同的值。显然，计算所有这些是相当浪费的，因此我们希望缩小图，直到所有节点都是“唯一”的。

下面是示例 1 中简化图的传输矩阵的示例。

[S_a(n)]   [1  1  1] [S_a(n-1)]
[S_f(n)] = [1  0  0]*[S_f(n-1)]
[S_B(n)]   [4  0  1] [S_B(n-1)]

如有任何建议或论文参考，我们将不胜感激。

原文

I have an algorithmic problem in which I have derived a transfer matrix between a lot of states. The next step is to exponentiate it, but it is very large, so I need to do some reductions on it. Specifically it contains a lot of symmetry. Below are some examples on how many nodes can be eliminated by simple observations.

My question is whether there is an algorithm to efficiently eliminate symmetry in digraphs, similarly to the way I've done it manually below.

In all cases the initial vector has the same value for all nodes.

In the first example we see that b, c, d and e all receive values from a and one of each other. Hence they will always contain an identical value, and we can merge them.

Digraph A
Digraph B

In this example we quickly spot, that the graph is identical from the point of view of a, b, c and d. Also for their respective sidenodes, it doesn't matter to which inner node it is attached. Hence we can reduce the graph down to only two states.

Digraph C
Digraph D

Update: Some people were reasonable enough not quite sure what was meant by "State transfer matrix". The idea here is, that you can split a combinatorial problem up into a number of state types for each n in your recurrence. The matrix then tell you how to get from n-1 to n.

Usually you are only interested about the value of one of your states, but you need to calculate the others as well, so you can always get to the next level. In some cases however, multiple states are symmetrical, meaning they will always have the same value. Obviously it's quite a waste to calculate all of these, so we want to reduce the graph until all nodes are "unique".

Below is an example of the transfer matrix for the reduced graph in example 1.

[S_a(n)]   [1  1  1] [S_a(n-1)]
[S_f(n)] = [1  0  0]*[S_f(n-1)]
[S_B(n)]   [4  0  1] [S_B(n-1)]

Any suggestions or references to papers are appreciated.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

叶落知秋 2024-10-24 22:45:18

布伦丹·麦凯的 nauty ( http://cs.anu.edu.au/~bdm/nauty/ ）是我所知道的计算图自同构的最好工具。计算图的整个自同构组可能成本太高，但您也许可以重用 McKay 的论文“实用图同构”（从 nauty 页面链接）中描述的一些算法。

回复收藏 0 原文

南巷近海 2024-10-24 22:45:18

如果其他人感兴趣的话，我将根据 userOVER9000 建议添加一个额外的答案。
以下是通过 dreadnaut 工具在示例 2 上使用 nauty 的示例。

$ ./dreadnaut 
Dreadnaut version 2.4 (64 bits).
> n=8 d g                                     -- Starting a new 8-node digraph
 0 : 1 3 4;                                   -- Entering edge data
 1 : 0 2 5;
 2 : 3 1 6;
 3 : 0 2 7;
 4 : 0;
 5 : 1;
 6 : 2;
 7 : 3;
> cx                                          -- Calling nauty
(1 3)(5 7)
level 2:  6 orbits; 5 fixed; index 2
(0 1)(2 3)(4 5)(6 7)
level 1:  2 orbits; 4 fixed; index 4
2 orbits; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
> o                                           -- Output "orbits"
 0:3; 4:7;

请注意，它建议连接示例 2 中的节点 0:3（即 a:d）和 4:7（即 e:h< /代码>。

nauty 算法没有详细记录，但作者将其描述为指数最坏情况，n^2 平均值。

I'll just add an extra answer building on what userOVER9000 suggested, if anybody else are interested.
The below is an example of using nauty on Example 2, through the dreadnaut tool.

$ ./dreadnaut 
Dreadnaut version 2.4 (64 bits).
> n=8 d g                                     -- Starting a new 8-node digraph
 0 : 1 3 4;                                   -- Entering edge data
 1 : 0 2 5;
 2 : 3 1 6;
 3 : 0 2 7;
 4 : 0;
 5 : 1;
 6 : 2;
 7 : 3;
> cx                                          -- Calling nauty
(1 3)(5 7)
level 2:  6 orbits; 5 fixed; index 2
(0 1)(2 3)(4 5)(6 7)
level 1:  2 orbits; 4 fixed; index 4
2 orbits; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
> o                                           -- Output "orbits"
 0:3; 4:7;

Notice it suggests joining nodes 0:3 which are a:d in Example 2 and 4:7 which are e:h.

The nauty algorithm is not well documented, but the authors describe it as exponential worst case, n^2 average.

回复收藏 0 原文

清欢 2024-10-24 22:45:18

计算对称性似乎是一个二阶问题。在第二张图中只取 a、b、c 和 d，就必须表达对称性

a(b,c,d) = b(a,d,c)

及其所有排列，或类似的排列。考虑添加第二个子图 a'、b'、c'、d'。同样，我们有对称性，但参数化不同。

对于计算人员（而不是数学人员）来说，我们可以这样表达问题吗？

每个图形节点都包含一组字母。在每次迭代中，每个节点中的所有字母都通过箭头复制到其邻居（某些箭头需要多次迭代，可以将其视为匿名节点的管道）。
我们正在努力寻找有效的方法来确定诸如
* N次迭代后每个集合/节点包含哪些字母。
* 对于每个节点，N 之后其集合不再更改。
* 哪些节点集最终包含相同的字母集（等价类）

？

Computing symmetries seems to be a bit of a second order problem. Taking just a,b,c and d in your second graph, the symmetry would have to be expressed

a(b,c,d) = b(a,d,c)

and all its permutations, or some such. Consider a second subgraph a', b', c', d' added to it. Again, we have the symmetries, but parameterised differently.

For computing people (rather than math people), could we express the problem like so?

Each graph node contains a set of letters. At each iteration, all of the letters in each node are copied to its neighbours by the arrows (some arrows take more than one iteration and can be treated as a pipe of anonymous nodes).
We are trying to find efficient ways of determining things such as
* what letters each set/node contains after N iterations.
* for each node the N after which its set no longer changes.
* what sets of nodes wind up containing the same sets of letters (equivalence class)

回复收藏 0 原文

~没有更多了~