Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397

Issue N8 2024 year

DOI: 10.17587/prin.15.402-410
Generation and Analysis of a Dataset of Optimal Double-Loop Circulant Networks
E. A. Monakhova, Leading Scientist, Associate Professor, O. G. Monakhov, Leading Scientist, Senior Researcher, monakhov@rav.sscc.ru, Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk, 630090, Russian Federation
Corresponding author: Emilia A. Monakhova, Leading Scientist, Associate Professor, Institute of Computational Mathematics and Mathematical Geophysics of Siberian Branch of Russian Academy of Sciences, Novosibirsk, 630090, Russian Federation E-mail: emilia@rav.sscc.ru
Received on June 07, 2024
Accepted on June 25, 2024

Optimal circulant networks are of practical interest as graph models of reliable communication networks for supercomputer systems and networks on a chip. A large dataset of parameters of optimal double-loop circulant networks with a number of nodes of up to 50,000 and 451,000 points has been constructed. The dataset contains, for each number of vertices, all generators corresponding to optimal or suboptimal (in the absence of optimal) descriptions of the graph. This made it possible to find analytical dependencies of the parameters that define families of optimal graphs. Based on the analysis of the constructed dataset, the solution to the problem of determining optimal two-dimensional circulant networks is studied. A process is automated for determining analytical, parametric descriptions of the families of optimal double-loop networks, described polynomials of diameter. Having applied the methods of integrating differential evolution and reduced local search to the analysis of the generated dataset, we rediscovered a number of previously known families and found more than 200 new, different from all those known in literature, families of optimal double-loop networks with generators of linear and quadratic types of polynomials. Our new ap­proach can be applied to studing datasets of other promising classes of graphs and networks.

Keywords: dataset of optimal networks, undirected double-loop circulant networks, families of optimal circulant graphs, diameter, differential evolution, local search
pp. 402—410
For citation:
Monakhova E. A., Monakhov O. G. Generation and Analysis of a Dataset of Optimal Double-Loop Circulant Networks, Programmnaya Ingeneria, 2024, vol. 15, no. 8, pp. 402—410. DOI: 10.17587/prin.15.402-410. (in Russian).
References:
  1. Bermond J.-C., Comellas F., Hsu D. F. Distributed loop computer networks: a survey, J. Parallel Distributed Comput., 1995, vol. 24, no. 1, pp. 2—10. DOI: 10.1006/jpdc.1995.1002.
  2. Hwang F. K. A survey on multi-loop networks, Theoretical Computer Science, 2003, vol. 299, pp. 107—121. DOI: 10.1016/S0304-3975(01)00341-3.
  3. Monakhova E. A. Structural and communicative properties of circulant networks, Prikladnaya diskretnaya matematika, 2011, no. 3, pp. 92—115 (in Russian).
  4. Huang X., Ramos A. F., Deng Y. Optimal Circulant Graphs As Low-latency Network Topologies, J. Supercomput., 2022, vol. 78, pp. 13491—3510. DOI: 10.1007/s11227-022-04396-5.
  5. Perez-Roses H., Bras-Amoros M., Seradilla-Merinero J. M. Greedy Routing in Circulant Networks, Graphs Combinatorics, 2022, vol. 38, no. 3. DOI: 10.1007/s00373-022-02489-9.
  6. Monakhov O. G., Monakhova E. A., Romanov A. Y., Sukhov A. M., Lezhnev E. V. Adaptive Dynamic Shortest Path Search Algorithm in Networks-on-Chip Based on Circulant Topologies, IEEE Access, 2021, vol. 9. pp. 160836—160846. DOI: 10.1109/ACCESS.2021.3131635.
  7. Lewis R. R. Analysis and Construction of Extremal Circulant and Other Abelian Cayley Graphs, Ph.D thesis, The Open University, London, UK, 2021. DOI: 10.21954/ou.ro.00013612.
  8. Hoffmann R., Deserable D., Seredynski F. Cellular automata rules solving the wireless sensor network coverage problem, Natural Computing, 2022, vol. 21. pp. 417—447. DOI: 10.1007/s11047-022-09888-0.
  9. Fei J., Lu C. Adaptive sliding mode control of dynamic systems using double loop recurrent neural network structure, IEEE Trans. Neural Netw. Learn. Syst., 2018, vol. 29, no. 4, pp. 1275—1286. DOI: 10.1109/TNNLS.2017.2672998.
  10. Du D.-Z., Hsu D. F., Li Q., Xu J. A combinatorial problem related to distributed loop networks, Networks, 1990, vol. 20, pp. 173—180.
  11. Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families, Networks, 1991, vol. 21, pp. 387—415.
  12. Chen B.-X., Xiao W.-J., Parhami B. Diameter formulas for a class of undirected double-loop networks, J. Interconnection Networks, 2005, vol. 6, no. 1, pp. 1—15. DOI: 10.1142/S0219265905001289.
  13. Chen B.-X., Meng J.-X., Xiao W.-J. Some new optimal and suboptimal infinite families of undirected double-loop networks, DMTCS, 2006, vol. 8, pp. 299—312. DOI: 10.46298/dmtcs.377.
  14. Jha P. K., Tight-optimal circulants vis-a-vis twisted tori, Discrete Appl. Math., 2014, vol. 175. pp. 24—34. DOI: 10.1016/j.dam.2014.05.021.
  15. Li Y., Chen Y., Tai W., Wang R. The minimum distance diagram and diameter of undirected double-loop networks, Proceedings of the 3rd Inter. Conf. On Materials Engineering, Manufacturing Technology and Cotrol (ICMEMTC 2016), 2016, pp. 1682—1687. DOI: 10.2991/ic-memtc-16.2016.319.
  16. Liu H., Li X., Wang S. Construction of Dual Optimal Bidirectional Double-Loop Networks for Optimal Routing, Mathematics, 2022, vol. 10, no. 21, pp. 4016. DOI: 10.3390/math10214016.
  17. Loudiki L., Kchikech M., Essaky E. H. A New Approach for Computing the Distance and the Diameter in Circulant Graphs, arXiv 2210.11116. Oct 2022. DOI: 10.48550/arXiv.2210.11116.
  18. Pai K.-J., Yang J.-S., Chen G.-Y., Chang J.-M. Configuring Protection Routing via Completely Independent Spanning Trees in Dense Gaussian on-Chip Networks, IEEE Trans. Netw. Sci. Eng., 2022, vol. 9, no. 2, pp. 932—946. DOI: 10.1109/TNSE.2022.3140329.
  19. Korneev V. V. Computing systems, Gelios ARV, 2004, 512 p. (in Russian).
  20. Monakhova E. A. On analytical representation of optimal two-dimensional Diophantine structures of homogeneous computer systems, Vychislitel'nye Sistemy, 1981, no. 90, pp. 81—91 (in Russian).
  21. Boesch F., Wang J.-F. Reliable circulant networks with minimum transmission delay, IEEE Trans. Circuits Syst., 1985, vol. 32, no. 12, pp. 1286—1291.
  22. Martinez C., Beivide R., Stafford E. et al. Modeling toroidal networks with the Gaussian integers, IEEE Trans. Comput., 2008, vol. 57, no. 8, pp. 1046—1056. DOI: 10.1109/TC.2008.57.
  23. Monakhova E. A., Monakhov O. G., Romanov A. Y. Routing Algorithms in Optimal Degree Four Circulant Networks Based on Relative Addressing: Comparative Analysis for Networks-on-Chip, IEEE Trans. Netw. Sci. Eng., 2023, vol. 10, no. 1, pp. 413—425. DOI: 10.1109/TNSE.2022.3211985.
  24. Monakhova E. A., Romanov A. Y., Lezhnev E. V. Shortest Path Search Algorithm in Optimal Two-dimensional Circulant Networks: Implementation for Networks-on-Chip, IEEE Access, 2020, vol. 8, pp. 215010—215019. DOI: 10.1109/ACCESS.2020.3040323.
  25. Monakhova E. A. Synthesis of optimal Diophantine structures, Vychislitel'nye Sistemy, 1979, no. 80, pp. 18—35 (in Russian).
  26. Jha P. K. Dimension-order routing algorithms for a family of minimal-diameter circulants, J. Interconnection Networks, 2013, vol. 14, no. 1, pp. 1350002 (24 p.). DOI: 10.1142/S0219265913500023.
  27. Chen B.-X., Meng J.-X., Xiao W.-J. A Constant Time Optimal Routing Algorithm for Undirected Double-Loop Networks, Proceedings of the First Int. Conf. Mobile Ad-hoc and Sensor Networks. MSN 2005, 2005, pp. 309—316. DOI: 10.1007/11599463_31.
  28. Jha P. K. Dense bipartite circulants and their routing via rectangular twisted torus, Discrete Appl. Math., 2014, vol. 166, pp. 141—158. DOI: 10.1016/j.dam.2013.09.021.
  29. Jha P. K., Smith J. D. Cycle Kronecker products that are representable as optimal circulants, Discrete Appl. Math., 2015, vol. 181, pp. 130—138. DOI: 10.1016/j.dam.2014.08.027.
  30. Liu H., Yang Y., Hu M. Tight optimal infinite families of undirected double-loop networks, Systems Engineering Theory and Practice, 2002, vol. 1, pp. 75—79.
  31. Monakhova E. A., Monakhov O. G. Evolutionary synthesis of families of optimal two-dimensional circulant networks, Vestnik SibGUTI, 2014, no 2, pp. 72—81 (in Russian).
  32. Romanov A. The Dataset for Optimal Circulant Topologies, Big Data Cogn. Comput., 2023, vol. 7, no. 2, article 80. DOI: 10.3390/ bdcc7020080.
  33. Karpenko A. P. Modern search engine optimization algorithms. Algorithms inspired by nature, Moscow, Izdatel'stvo MGTU im. N. E. Baumana, 2014, 446 p. (in Russian).
  34. Zaheer H., Pant M., Kumar S., Monakhov O., Monakhova E., Deep K. A new guiding force strategy for differential evolution, International Journal of System Assurance Engineering and Management, 2017, vol. 8, suppl. 4, pp. 2170—2183. DOI: 10.1007/s13198-014-0322-6