Creating interconnect topologies by algorithmic edge removal: MOD and SMOD graphs

We introduce a method of constructing classes of graphs by algorithmic removal of entire groups of edges. Our approach to creating new classes of graphs is to focus entirely on the structure and properties of an adjacency matrix. At an initialisation step of the algorithm we start with a complete fully connected graph. In Part I we present MOD and arrested MOD graphs resulting from removal of square blocks of edges at each iteration and substitution of removed blocks with a diagonal matrix with one extra pivotal element along the main diagonal. The MOD graphs possess unique and useful properties. All important graph measures are easily expressed in analytical form and are presented in the paper. Several important properties of MOD graphs are compared very favourably with graphs representing common interconnect topologies: hypercube, 3D and 5D tori, TOFU and dragonfly. This lead us to consider MOD and arrested MOD graphs as interesting candidates for effective supercomputer interconnects. In Part II, at each iterative step we successively remove triangular shapes from the adjacency matrix. This iterative process leads to the final matrix which has two Sierpinski gaskets aligned along the main diagonal. It will be shown below that this new class of graphs is not a Sierpinski graph, since it is the adjacency matrix which has a structure of a Sierpinski gasket, and not a graph described by this matrix. We call this new class of graphs Sierpinski-Michalewicz-Or lowski-Deng SMOD graphs. The most remarkable property of the SMOD class of graphs, is that irrespective of the graph order, the diameter is constant and equals 2. The size of the graph, or the total number of edges, is about 10% of the size of a complete graph of the same order. We analyse important graph theoretic characteristics related to the topology such as diameter as a function of graph order, size, mean path length, ratio of the graph size to the size of a complete graph of the same order, and some spectral properties.