Поиск семейств субоптимальных циркулянтных сетей с помощью больших языковых моделей

Поиск семейств субоптимальных циркулянтных сетей с помощью больших языковых моделей

Монахова Э. А., Монахов О. Г.
Дискретный анализ и исследование операций, 33, 2, 64-81 (2026)
Скачать статью

УДК 519.176+519.8+519.7 
DOI: 10.33048/daio.2026.33.859

Аннотация:

На основе анализа разработанного авторами датасета двумерных кольцевых циркулянтных сетей решается задача поиска семейств субоптимальных по диаметру циркулянтных сетей. Субоптимальные двумерные кольцевые циркулянты — это графы с минимально возможным диаметром для данного числа вершин, превышающим на единицу точную нижнюю границу диаметра циркулянтов. Представлена новая оригинальная визуализация на плоскости точек датасета, соответствующих субоптимальным циркулянтам. С помощью обнаруженной визуальной регулярности открыты последовательности аналитических описаний субоптимальных циркулянтов. Применение больших языковых моделей в качестве ИИ-ассистента при разработке программ позволило найти новые семейства субоптимальных графов, составляющие в общей сложности 75% субоптимальных точек датасета. Теоретически доказана масштабируемость найденных семейств графов при росте их диаметров, при доказательствах теорем использовалась большая языковая модель. Найденные аналитически задаваемые семейства циркулянтов представляют интерес как топологии сетей на кристалле и коммуникационных систем. 

Табл. 3, ил. 3, библиогр. 16.

Литература:
  1. Bermond J.-C., Comellas F., Hsu D. F. Distributed loop computer networks: A survey // J. Parallel Distrib. Comput. 1995. V. 24. P. 2–10.
     
  2. Hwang F. K. A survey on multi-loop networks // Theor. Comput. Sci. 2003. V. 299, No. 1–3. P. 107–121.
     
  3. Monakhova E. A. A survey on undirected circulant graphs // Discrete Math. Algorithms Appl. 2012. V. 4, No. 1. Article ID 1250002. 30 p.
     
  4. Lewis R. R. Analysis and construction of extremal circulant and other Abelian Cayley graphs: PhD Thesis. London, 2021. 390 p.
     
  5. Huang X., Ramos A. F., Deng Y. Optimal circulant graphs as low-latency network topologies // J. Supercomput. 2022. V. 78, No. 11. P. 13491–13510. DOI: 10.1007/s11227-022-04396-5.
     
  6. Liu H., Li X., Wang S. Construction of dual optimal bidirectional doubleloop networks for optimal routing // Mathematics. 2022. V. 10. Article ID 4016. 17 p.
     
  7. Монахов О. Г., Монахова Э. А. Масштабируемый подход к кодизайну топологий и алгоритмов маршрутизации для семейств оптимальных циркулянтных сетей степени четыре // Дискрет. анализ и исслед. операций. 2025. Т. 32, № 2. С. 88–106.
     
  8. Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families // Networks. 1991. V. 21, No. 4. P. 387–415.
     
  9. Monakhova E. A., Monakhov O. G. Double-loop-networks. Datasets of optimal double loop networks or optimal circulant graphs (N; 1, s). 2024. https://github.com/mila0411/Double-loop-networks (accessed: 1.08.2026).
     
  10. Монахова Э. А., Монахов О. Г. Анализ базы данных оптимальных двухконтурных кольцевых сетей // Прикл. дискрет. математика. 2024. № 64. C. 56–71.
     
  11. Du D.-Z., Hsu D. F., Li Q., Xu J. A combinatorial problem related to distributed loop networks // Networks. 1990. V. 20. P. 173–180.
     
  12. Bermond J.-C., Tzvieli D. Minimal diameter double-loop networks: Dense optimal families // Networks. 1991. V. 21. P. 1–9.
     
  13. Tzvieli D. Double-loop interconnection networks with minimal transmission delay: PhD Thesis. Baton Rouge, LA, 1988. 156 p.
     
  14. Chen B.-X., Meng J.-X., Xiao W.-J. Some new optimal and suboptimal infinite families of undirected double-loop networks // Discrete Math. Theor. Comput. Sci. 2006. V. 8. P. 299–312.
     
  15. Монахов О. Г., Монахова Э. А. Программа вычисления характеристик регулярных графов с параметрическим описанием. Свид. . . . № 2013619128. М.: Фед. сл. по интеллект. собств., патентам и товар. знакам, 2013.
     
  16. Chen B.-X., Meng J.-X., Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // Mobile ad-hoc and sensor networks. Proc. 1st Int. Conf. (Wuhan, China, Dec. 13–15, 2005). Heidelberg: Springer, 2005. P. 308–316. (Lect. Notes Comput. Sci.; V. 3794).

Исследование выполнено за счёт Российского научного фонда (проект № 25–11–00248, https://rscf.ru/en/project/25-11-00248). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Монахова Эмилия Анатольевна
  1. Национальный исследовательский университет «Высшая школа экономики», 
    ул. Мясницкая, 20, 101000 Москва, Россия
  2. Институт вычислительной математики и математической геофизики, 
    пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия

E-mail: emilia@rav.sscc.ru 

Монахов Олег Геннадьевич
  1. Институт вычислительной математики и математической геофизики, 
    пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия

E-mail: monakhov@rav.sscc.ru 

Статья поступила 18 марта 2026 г.
После доработки — 5 апреля 2026 г.
Принята к публикации 22 апреля 2026 г.

Abstract:

Based on the analysis of a dataset of two-dimensional ring circulant networks, a solution to the problem of finding families of suboptimal circulant networks with suboptimal diameters is investigated. Suboptimal two-dimensional ring circulants are graphs with the minimum possible diameter for a given number of vertices, exceeding by one the known exact lower bound on the circulant diameter. A new original plane visualization of dataset points corresponding to suboptimal circulants is presented. Using the discovered visual regularity of suboptimal circulant description sequences and large language models as an AI assistant for program development, new families of suboptimal graphs are found, comprising a total of 75% of the suboptimal dataset points. The scalability of the discovered graph families with increasing diameters is theoretically proven, while a large language model is used in proving the theorems. The analytically defined families of two-dimensional ring circulants found are of interest as topologies of communication networks for networks on a chip and communication systems.

Tab. 3, illustr. 3, bibliogr. 16.

References:
  1. J.-C. Bermond, F. Comellas, and D. F. Hsu, Distributed loop computer networks: A survey, J. Parallel Distrib. Comput. 24, 2–10 (1995).
     
  2. F. K. Hwang, A survey on multi-loop networks, Theor. Comput. Sci. 299 (1–3), 107–121 (2003).
     
  3. E. A. Monakhova, A survey on undirected circulant graphs, Discrete Math. Algorithms Appl. 4 (1), ID 1250002 (2012).
     
  4. R. R. Lewis, Analysis and construction of extremal circulant and other Abelian Cayley graphs, PhD Thesis (London, 2021).
     
  5. X. Huang, A. F. Ramos, and Y. Deng, Optimal circulant graphs as lowlatency network topologies, J. Supercomput. 78 (11), 13491–13510 (2022), DOI: 10.1007/s11227-022-04396-5.
     
  6. H. Liu, X. Li, and S. Wang, Construction of dual optimal bidirectional double-loop networks for optimal routing, Mathematics 10, ID 4016 (2022).
     
  7. O. G. Monakhov and E. A. Monakhova, A scalable approach to co-design of topologies and routing algorithms for families of optimal degree-four circulant networks, Diskretn. Anal. Issled. Oper. 32 (2), 88–106 (2025) [Russian] [J. Appl. Ind. Math. 19 (2), 291–301 (2025), DOI: 10.1134/S1990478925020085].
     
  8. D. Tzvieli, Minimal diameter double-loop networks. 1. Large infinite optimal families, Networks 21 (4), 387–415 (1991).
     
  9. E. A. Monakhova and O. G. Monakhov, Double-loop-networks. Datasets of optimal double loop networks or optimal circulant graphs (N; 1, s). 2024. https://github.com/mila0411/Double-loop-networks (accessed: 1.08.2026).
     
  10. E. A. Monakhova and O. G. Monakhov, Database analysis of optimal double-loop networks, Prikl. Diskretn. Mat., No. 64, 56–71 (2024) [Russian].
     
  11. D.-Z. Du, D. F. Hsu, Q. Li, and J. Xu, A combinatorial problem related to distributed loop networks, Networks 20, 173–180 (1990).
     
  12. J.-C. Bermond and D. Tzvieli, Minimal diameter double-loop networks: Dense optimal families, Networks 21, 1–9 (1991).
     
  13. D. Tzvieli, Double-loop interconnection networks with minimal transmission delay, PhD Thesis (Baton Rouge, LA, 1988).
     
  14. B.-X. Chen, J.-X. Meng, and W.-J. Xiao, Some new optimal and suboptimal infinite families of undirected double-loop networks, Discrete Math. Theor. Comput. Sci. 8, 299–312 (2006).
     
  15. O. G. Monakhov and E. A. Monakhova, A program for calculating characteristics of regular graphs with a parametric description. Certif. . . . No. 2013619128 (Fed. Serv. Intellect. Prop. Pat. Trademarks, Moscow, 2013) [Russian].
     
  16. B.-X. Chen, J.-X. Meng, and W.-J. Xiao, A constant time optimal routing algorithm for undirected double-loop networks, in Mobile ad-hoc and sensor networks, Proc. 1st Int. Conf. (Wuhan, China, Dec. 13–15, 2005) (Springer, Heidelberg, 2005), pp. 308–316 (Lect. Notes Comput. Sci., Vol. 3794).