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 the 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 compare very favourably with graphs representing common interconnect topologies: hypercube, 3D and 5D tori, TOFU and dragony. This lead us to consider MOD and arrested MOD graphs as interesting candidats for effective supercomputer interconnects. In Part II, at each iterative step we successively remove triangular shapes from adjacency matrix. This iterative process leads to the nal 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. Keywords: supercomputer interconnects, big data, exascale computing, graph theory, topology of graphs, classes of graphs, graph generation.Discovery of Optimal Network Topologies By Using Graph Theor