Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 19 min ago
PreprintarXiv licencearXiv

Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion

  • Zeru Zhu
  • Marco Gamarra
  • Ji Liu
Open at sourcePDFDOICite

Abstract

This paper studies an open network design problem of constructing graph topologies with maximum algebraic connectivity under fixed numbers of vertices and edges. A density-dependent approach is proposed that decomposes the design task into two stages: a high-quality, low-cost structural backbone construction and a reinforcement learning completion stage. The method selects the backbone based on density, using complete multipartite graphs in dense regimes and Cayley graphs in low-to-intermediate regimes, and then refines the remaining edges through a learning-based procedure. Numerical results show that the proposed method achieves high algebraic connectivity with favorable runtime scalability, outperforming existing methods. These results support a structural-family-first strategy for scalable network design.

Related

  1. Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
    Zeru Zhu, Jinzheng Li, Yuanjie Ren +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  2. Orthogonal completion of algebraic systems
    A. Yu. Golubkov
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. Orthogonal completion of algebraic systems II
    A. Yu. Golubkov
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  4. On the structure of graphs with given odd girth and large algebraic connectivity
    Zhengbo Chen, Chenxing Li, Zhouningxin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Online Autotuning of Algebraic Multigrid via Contextual Bandits and Reinforcement Learning
    Xudong He, Ruiyu Wang, Yilang Ding +2
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv

Cite

BibTeXRIS
BibTeX
@misc{zhu2026toward,
  title = {{Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion}},
  author = {Zeru Zhu and Marco Gamarra and Ji Liu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.12697},
  eprint = {2610.12697},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.12697},
}
RIS
TY  - UNPB
TI  - Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion
AU  - Zeru Zhu
AU  - Marco Gamarra
AU  - Ji Liu
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.12697
UR  - https://arxiv.org/abs/2610.12697
AB  - This paper studies an open network design problem of constructing graph topologies with maximum algebraic connectivity under fixed numbers of vertices and edges. A density-dependent approach is proposed that decomposes the design task into two stages: a high-quality, low-cost structural backbone construction and a reinforcement learning completion stage. The method selects the backbone based on density, using complete multipartite graphs in dense regimes and Cayley graphs in low-to-intermediate regimes, and then refines the remaining edges through a learning-based procedure. Numerical results show that the proposed method achieves high algebraic connectivity with favorable runtime scalability, outperforming existing methods. These results support a structural-family-first strategy for scalable network design.
ER  -