16

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.

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114
  • 2
    +1 for good examples and nice graphs – schnaader Feb 17 '11 at 20:15
  • 1
    Pardon my ignorance, but I'm not sure what "values" you are referring to in your first example (i.e.: "receive values from A", "contain an identical value"). – mhum Feb 17 '11 at 20:29
  • If I understand it correctly, you are looking for special sub-graph (cycles, lines, complete subgraphs, ...) with special characteristics (node degrees, connectivity between them, ...) Probably these sub-graphs have some meaning in your original problem. Maybe it is good to define sub-graphs of interest and find them with appropriate algorithms. Problem is maybe recursive, same simplification can be done on result graph. – Ante Feb 18 '11 at 12:43
  • Ante: I've added a clarification. I'm not quite sure if you can consider the reduced graphs "subgraphs", since you don't throw away nodes, but rather join equivalent ones together. – Thomas Ahle Feb 18 '11 at 14:05

3 Answers3

6

Brendan McKay's nauty ( http://cs.anu.edu.au/~bdm/nauty/) is the best tool I know of for computing automorphisms of graphs. It may be too expensive to compute the whole automorphism group of your graph, but you might be able to reuse some of the algorithms described in McKay's paper "Practical Graph Isomorphism" (linked from the nauty page).

userOVER9000
  • 260
  • 1
  • 3
  • Great. I tried using their dreadnaut tool, and it outputs exactly the expected results. In example one it says node b:d forms an "orbit" and in example two it gives a:d, e:h. , It doesn't give the increased vertices values though, but they should be trivial to calculate once the reduction is known. – Thomas Ahle Feb 18 '11 at 14:33
  • 1
    Very interesting! For your reference, two vertices u and v are in the same orbit if there is a graph automorphism f -- namely, some permutation f of all the vertices that preserves edges (i.e.: if there is an edge from u to v, then there is an edge from f(u) to f(v)) -- that maps u to v (i.e.: f(u) = v). – mhum Feb 19 '11 at 01:54
  • Interesting indeed. However I must admit that for my actual purpose I ended up with a simple probabilistic approach. Instead of trying to calculate the orbits, I simply checked witch groups of nodes shared values consecutively. I guess that worked well, because my numbers grow very quickly. – Thomas Ahle Feb 19 '11 at 02:33
0

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)

?

PaulMurrayCbr
  • 1,167
  • 12
  • 16
0

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.

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114