ggen

Quickstart

• brew install uv
• brew install graphviz
• brew install gnuplot
• Clone the repo
• cd into the top-level repo directory
• make
• Check out the Graphviz plots and Gnuplot histograms in the gallery subdirectory as well as the CSV files in the tests subdirectory

Background

• ggen is part of a larger suite of programs for finding induced subgraphs with a prescribed edge count.
• Among other things, ggen can generate three kinds of random graphs: "exponential" (Erdős–Rényi), "power" (scale-free) and "geometric" (in the plane, with no wrap-around).
• It is intended to be used in conjunction with sub_search and is a bit awkward to call directly.
• Moreover, the native graph representation format used by ggen and sub_search — effectively the adjacency lists corresponding to the upper-triangular portion of the adjacency matrix — is non-standard and does not lend itself to visualization or manipulation.
• This standalone repo contains a copy of ggen.c as well as ggen.sh, a friendlier wrapper for a subset of ggen's functionality. Be sure to make ggen before running ggen.sh.
• ggen.sh outputs graphs in the standard DOT format as well as optionally generating Graphviz plots and Gnuplot histograms. make create_gallery will create a bunch of these.
• There are also some additional scripts for producing CSV files suitable for validation, visualization and further processing. make test to see them in action.
• The adjacency matrix $A$ of an undirected graph $G = (V, E)$, $|V| = n$, $|E| = m$ is the $n \times n$ matrix whose $ij^{th}$ entry $a_{ij}$ is $1$ if ${i, j} \in E$ and $0$ otherwise. The degree matrix $D$ of $G$ is a matrix whose $i^{th}$ diagonal entry $d_{ii}$ is the degree $deg(v_i)$ of $v_i \in V$, with the off-diagonal entries being $0$. The Laplacian matrix $L$ of $G$ is defined as $D - A$. Denote the $n$ eigenvalues of $L$ by $\lambda_0, \lambda_1,\dots, \lambda_{n-2}, \lambda_{n-1}$ (there are exactly $n$, up to multiplicity, because $L$ is real and symmetric). We can assume, wlog, that $\lambda_0 \le \lambda_1 \le \dots \le \lambda_{n-2} \le \lambda_{n-1}$. $L$ has the following remarkable properties:
  • The smallest eigenvalue $\lambda_0$ is $0$, with eigenvector $[1, 1, \dots, 1]^\mathrm{T}$. The multiplicity of $\lambda_0$ equals the number of connected components of $G$.
  • Since $\lambda_0$ is $0$, the "spectral gap" $\lambda_1 - \lambda_0$ is just $\lambda_1$, also known as the Fiedler value. Note that $G$ is connected iff $\lambda_1 > 0$.
  • $\lambda_1$ is inversely proportional to the mixing time of $G$, with the Cheeger inequality providing a more precise formulation. Expander graphs have a large spectral gap, so that random walks on them mix rapidly. Check out Chapter 3 of the following lecture notes for more info.
  • matrix2eigs.py uses these properties to determine the number of connected components of $G$ and compute the spectral gap. It also optionally verifies that the off-diagonal entries of $L$ sum to $\sum\limits_{i}deg(v_i) = 2 \cdot m$ as well as the fact that $tr(L) = \sum\limits_{i}\lambda_i = 2 \cdot m$.