Processing math: 100%

Motivation

Finding the symmetries in structures is useful for a number of reasons including model reduction, robustness with redundancy, cluster synchronization patterns, and some classification applications. In particular, graphs are an abstract framework with which many structures can be represented, and so understanding the symmetries that arise in graphs is extremely important. Fortunately, the symmetries in graphs, known collectively as the automorphism group of a graph, can be computed relatively easily using specialized software. What is less known is how symmetries arise in graphs in the first place. This inspired my advisor and I to determine the set of rules, following which, one may construct a graph with desired symmetries.

Quotient Graphs

The key part of the algorithm is the ability to 'store' a graph's symmetries in a structure called a quotient graph, Q=(C,n,s,F,f) where

  • C is the set of quotient nodes, CiC, i=1,,p,
  • nZp is the strictly positive integer vector that represents the population each quotient node represents,
  • sZp is the non-negative integer vector that represents the intra-cluster degree of each quotient node,
  • FC×C is the set of q undirected quotient edges between the quotient nodes,
  • fZq×2 is the matrix of quotient edge weights such that each edge has two weights associated with each direction.
To be more concrete, let Fi=(Cj,Ck) be a quotient edge, then the ith row of f contains values fjk and fkj which represent the inter-cluster degree from cluster Cj to cluster Ck and vice versa, respectively. For the quotient graph to be feasible, some constraints must be satisfied.
  • There must be enough nodes in Ci so that each node can have intra-cluster degree si and the total number of intra-cluster edges, sini/2 must be a whole number so, nisi+1andmod(nisi,2)=0
  • Let Fi=(Cj,Ck) be a quotient edge. The number of edges passing between clusters Cj and Ck must be consistent and there must be enough nodes in either cluster to satisfy the demands of the other. njfjk=nkfkjandnjfkjandnkfjk
  • A quotient graph Q with all the fields listed above that satisfy the constraints also listed above is called a feasible quotient graph.

Creating Feasible Quotient Graphs

By the constraints listed above, clearly any quotient graph Q may not be a feasible quotient graph. The constraints also prevent one from freely designing a quotient graph except under the most restrictive circumstances. Here we present two methods by which one may partially define a quotient graph, and then determine the missing component so that the result is a completely defined feasible quotient graph.

Missing Quotient Edge Weights

Let us assume we have defined a quotient Q with a set of quotient nodes C, quotient node populations n, quotient node intra-cluster degree s, and undirected quotient edges F. We are left to find f ensuring the final quotient graph is feasible. From the quotient edge weight consistency requirement, we have the relation, njnk=fkjfjk Let us define c=gcd(nj,nk) as the greatest common divisor of the two nodal populations. Let d be any integer factor of c. We then may choose fkj=njdandfjk=nkd for any factor of c, d. Different choices of d will lead to more or less sparse graphs.

Missing Quotient Node Populations

Let us assume we have defined a quotient graph Q with a set of quotient nodes C, quotient node intra-cluster degrees s, undirected quotient edges F, and quotient edge weights f. We are left to find the quotient node populations n to ensure the resulting quotient graph Q is feasible. To do this, we construct a matrix ˆAZq×p where the ith row of ˆA corresponds to the ith quotient edge, Fi=(Cj,Ck) such that, Ai={fjk=jfkj=k0j,k To handle the constraint mod(nisi,2)=0, we define new variables xi, i=1,,p, where ni=(mod(si,2)+1)xi which can be written as a matrix equation, n=Sx so that S is a diagonal matrix with elements Sii=mod(si,2)+1. Now, the quotient edge consistency constraint can be written in matrix form, ˆAn=ˆASx=Ax=0 where A=ˆAS. Some useful properties of the matrix A are discussed in detail in the paper "Generating Graphs with Symmetry".
The final step is ensuring that nj is large enough njmax{max(Cj,Ck)F{fkj},sj+1}=nLj where nLj is the lower limit. To convert to xj, let xLj=(mod(sj,2)+1)nLj.
Putting together the constraints, we have constructed a set of diophantine equations, which can be solved using an integer linear program (ILP). mincTxs.t.Ax=0xjxLjxjZ