Generating Graphs with Symmetry [INCOMPLETE]

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.

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

• $\mathcal{C}$ is the set of quotient nodes, $\mathcal{C}_i \in \mathcal{C}$, $i = 1,\ldots,p$,
• $\textbf{n} \in \mathbb{Z}^p$ is the strictly positive integer vector that represents the population each quotient node represents,
• $\textbf{s} \in \mathbb{Z}^p$ is the non-negative integer vector that represents the intra-cluster degree of each quotient node,
• $\mathcal{F} \subset \mathcal{C} \times \mathcal{C}$ is the set of $q$ undirected quotient edges between the quotient nodes,
• $\textbf{f} \in \mathbb{Z}^{q \times 2}$ is the matrix of quotient edge weights such that each edge has two weights associated with each direction.

• There must be enough nodes in $\mathcal{C}_i$ so that each node can have intra-cluster degree $s_i$ and the total number of intra-cluster edges, $s_in_i/2$ must be a whole number so, $$ n_i \geq s_i + 1 \quad \text{and} \quad \bmod(n_is_i,2) = 0 $$
• Let $\mathcal{F}_i = (\mathcal{C}_j,\mathcal{C}_k)$ be a quotient edge. The number of edges passing between clusters $\mathcal{C}_j$ and $\mathcal{C}_k$ must be consistent and there must be enough nodes in either cluster to satisfy the demands of the other. $$ n_j f_{jk} = n_k f_{kj} \quad \text{and} \quad n_j \geq f_{kj} \quad \text{and} \quad n_k \geq f_{jk} $$
A quotient graph $\mathcal{Q}$ with all the fields listed above that satisfy the constraints also listed above is called a feasible quotient graph.

By the constraints listed above, clearly any quotient graph $\mathcal{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.

Let us assume we have defined a quotient $\mathcal{Q}$ with a set of quotient nodes $\mathcal{C}$, quotient node populations $\textbf{n}$, quotient node intra-cluster degree $\textbf{s}$, and undirected quotient edges $\mathcal{F}$. We are left to find $\textbf{f}$ ensuring the final quotient graph is feasible. From the quotient edge weight consistency requirement, we have the relation, $$ \frac{n_j}{n_k} = \frac{f_{kj}}{f_{jk}} $$ Let us define $c = \text{gcd}(n_j,n_k)$ as the greatest common divisor of the two nodal populations. Let $d$ be any integer factor of $c$. We then may choose $$ f_{kj} = \frac{n_j}{d} \quad \text{and} \quad f_{jk} = \frac{n_k}{d} $$ for any factor of $c$, $d$. Different choices of $d$ will lead to more or less sparse graphs.

Let us assume we have defined a quotient graph $\mathcal{Q}$ with a set of quotient nodes $\mathcal{C}$, quotient node intra-cluster degrees $\textbf{s}$, undirected quotient edges $\mathcal{F}$, and quotient edge weights $\textbf{f}$. We are left to find the quotient node populations $\textbf{n}$ to ensure the resulting quotient graph $\mathcal{Q}$ is feasible. To do this, we construct a matrix $\hat{A} \in \mathbb{Z}^{q \times p}$ where the $i$th row of $\hat{A}$ corresponds to the $i$th quotient edge, $\mathcal{F}_i = (\mathcal{C}_j,\mathcal{C}_k)$ such that, $$ A_{i\ell} = \left\{ \begin{array}{ll} f_{jk} & \ell = j\\ -f_{kj} & \ell = k\\ 0 & \ell \neq j,k \end{array}\right. $$ To handle the constraint $\bmod(n_is_i,2) = 0$, we define new variables $x_i$, $i = 1,\ldots,p$, where $$ n_i = (\bmod(s_i,2) + 1) x_i $$ which can be written as a matrix equation, $$ \textbf{n} = S \textbf{x} $$ so that $S$ is a diagonal matrix with elements $S_{ii} = \bmod(s_i,2) + 1$. Now, the quotient edge consistency constraint can be written in matrix form, $$ \hat{A} \textbf{n} = \hat{A} S \textbf{x} = A \textbf{x} = \boldsymbol{0} $$ where $A = \hat{A} S$. Some useful properties of the matrix $A$ are discussed in detail in the paper "Generating Graphs with Symmetry".
The final step is ensuring that $n_j$ is large enough $$ n_j \geq \max \left\{ \max\limits_{(\mathcal{C}_j,\mathcal{C}_k) \in \mathcal{F}} \left\{f_{kj}\right\},s_j+1\right\} = n_j^L $$ where $n_j^L$ is the lower limit. To convert to $x_j$, let $x_j^L = (\bmod(s_j,2)+1)n_j^L$.
Putting together the constraints, we have constructed a set of diophantine equations, which can be solved using an integer linear program (ILP). $$ \begin{array}{ll} \min & \textbf{c}^T \textbf{x}\\ \text{s.t.} & A \textbf{x} = \boldsymbol{0}\\ & x_j \geq x_j^L\\ & x_j \in \mathbb{Z} \end{array} $$

Hello, my name is Isaac Klickstein, currently living in Albuquerque, New Mexico. I am working on my PhD in the mechanical engineering department at the University of New Mexico. My research involves optimal control, network science, and regular graphs. I will be graduating in December, 2019 and moving to New England in January, 2020.

• iklick@unm.edu
• Department of Mechanical Engineering MSC01 1150
  1 University of New Mexico
  Albuquerque, NM 87131