Discovery of analytical dependences of parameters of optimal chordal ring networks based on data analysis

The structure of chordal ring networks is being intensively studied for the construction of communication networks in various practical applications. The introduction of additional chords increases the reliability of the ring structure and reduces its diameter, which in turn reduces delays and increases the performance of the entire communication system. In this paper, we study the class of chordal ring networks of degree three, which are studied in many works as a possible topology of communication networks of infocommunication systems. A chordal ring graph with the smallest possible diameter for a given order of the graph is called optimal. Diameter minimization optimizes a number of important characteristics of the communication network topology, such as the reliability of the communication structure in case of element failures, structural delays in data transmission, communication speed, etc. Therefore, the fundamental problem of synthesizing optimal topologies in different classes of regular graphs is to find graphs with a minimum diameter among graphs with a given degree and number of vertices. For the class of graphs under consideration, structural properties were previously investigated, including the calculation of the diameter and finding the shortest paths. In this paper, we study the problem of finding optimal graphs in the class of chordal ring networks as a search for descriptions of families of graphs with a minimum diameter for given orders and degrees of graphs. The main methods used to construct optimal regular structure networks are local search, breadth-first search, enumeration and heuristic algorithms. Earlier, for the class of chordal ring graphs, a family of extremal optimal graphs with a maximum order for any diameter was obtained. The problem of minimizing the diameter for a given order is more difficult to solve than obtaining extremal graphs, since the diameter does not always increase monotonically with increasing order. In the literature, only six families of graphs with the smallest possible diameter were known, obtained by the method of dense tessellation on the plane of triangles corresponding to chordal ring graphs. A method that would allow one to massively obtain descriptions of families of optimal graphs in an analytical form was not known. Progress in this direction is made in the present work. For the first time, we have built a large dataset of parameters of optimal chordal ring graphs with the number of vertices reaching 60 thousand and with an enumeration of all generators for optimal graphs, and we have proposed a metaheuristic approach for dataset mining. Using it, we found new patterns in the emergence of families of optimal graphs and, on their basis, generalized and expanded the list of families of optimal chordal rings, constructing more than 170 new analytically defined families of optimal graphs.