math.OCOct 8, 2026

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

Authors: Zeru Zhu, Marco Gamarra, Ji Liu

Organizations: Department of Applied Mathematics and Statistics at Stony Brook University · Air Force Research Laboratory · Department of Electrical and Computer Engineering at Stony Brook University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Fig. 1: Random connected graphs ( n=32n=32 ); highlighted points are weak-maximal staircase points in (ρ,λ2)(\rho,\lambda_{2}) .
Fig. 2: Complete 2/3/4/5-partite graphs in K36\mathcal{K}_{36} on the (ρ,λ2)(\rho,\lambda_{2}) plane.
Methodn=8n=8n=16n=16n=32n=32n=64n=64n=128n=128
FVG3.34±1.773.34\pm 1.776.72±4.186.72\pm 4.1813.99±8.8113.99\pm 8.8128.87±18.1928.87\pm 18.1959.16±36.8459.16\pm 36.84
MAC−0.47±0.41-0.47\pm 0.41 /0/25−1.27±0.65-1.27\pm 0.65 /1/2−3.03±1.42-3.03\pm 1.42 /0/2−6.62±3.10-6.62\pm 3.10 /0/1−13.72±6.52-13.72\pm 6.52 /0/1
MDMD−0.08±0.35-0.08\pm 0.35 /10/50−0.47±0.40-0.47\pm 0.40 /7/12−1.09±0.73-1.09\pm 0.73 /4/5−2.15±1.49-2.15\pm 1.49 /1/3−3.89±2.49-3.89\pm 2.49 /1/1
WTS0.27±0.360.27\pm 0.36 /50/500.18±0.220.18\pm 0.22 / 83 /12−0.23±0.31-0.23\pm 0.31 /12/2−0.76±0.63-0.76\pm 0.63 /2/2−1.63±1.12-1.63\pm 1.12 /1/1
k-opt0.19±0.290.19\pm 0.29 /45/550.20±0.160.20\pm 0.16 /81/190.13±0.130.13\pm 0.13 / 90 /100.04±0.050.04\pm 0.05 / 80 /200.01±0.020.01\pm 0.02 /58/8
SDP-step0.08±0.570.08\pm 0.57 /30/400.29±0.570.29\pm 0.57 /67/110.39±0.710.39\pm 0.71 /71/4––
TABLE I: Quality summary. FVG: absolute λ2\lambda_{2} (mean ±\pm std). Others: Δλ2\Delta\lambda_{2} mean ±\pm std / win% / match%. Red = best Δλ2\Delta\lambda_{2} ; blue = best win%.
Methodn=8n=8n=16n=16n=32n=32n=64n=64n=128n=128
MAC4.35×10−34.35\times 10^{-3}6.31×10−36.31\times 10^{-3}1.62×10−21.62\times 10^{-2}4.63×10−24.63\times 10^{-2}1.53×10−11.53\times 10^{-1}
MDMD †8.59×10−48.59\times 10^{-4}5.42×10−35.42\times 10^{-3}4.92×10−24.92\times 10^{-2}4.08×10−14.08\times 10^{-1}5.145.14
FVG †1.38×10−31.38\times 10^{-3}7.46×10−37.46\times 10^{-3}1.02×10−11.02\times 10^{-1}9.27×10−19.27\times 10^{-1}24.0624.06
WTS †5.47×10−15.47\times 10^{-1}1.001.002.142.145.535.5319.7819.78
k-opt †5.20×10−25.20\times 10^{-2}4.04×10−14.04\times 10^{-1}2.702.708.608.6038.7838.78
SDP-step †1.48×10−11.48\times 10^{-1}1.421.4224.8824.88––
TABLE II: Mean online runtime (s). Red : faster of matched MAC/BB-RL runs. †\dagger : historical timings. BB-RL completion includes final selection.
Fig. 3: Baseline quality at n=16n=16 .
Fig. 4: Baseline quality at n=64n=64 .
Fig. 5: Envelope, FVG, and EIG at n=60n=60 .
Fig. 6: Envelope, FVG, and EIG at n=512n=512 , ρ>0.9\rho>0.9 .
Fig. 7: Low-intermediate quality at n=64n=64 .
Fig. 8: BB-RL vs FVG at n=64n=64 .
More in this topic

Graph Construction

See all 15 papers

Explore similar work

CardsList

  1. DAGGER: Gradient-Free Construction of Transiently Amplifying Networks under Hard Connectivity Constraints

    May 31, 2026James C. FergusonDynamical SystemsGradient-Free Optimization

    The African Institute for Mathematical Sciences (Muizenberg, South Africa) · the Institute of Science and Technology Austria (Klosterneuburg, Austria)

  2. Graph Learning with Spectral Connectivity Priors for Scarce Data

    Sep 23, 2026Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou +3Graph Signal ProcessingGraph Structure Learning

    Tsinghua University, China · York University, Canada

  3. Cayley Graph Optimization for Scalable Multi-Agent Communication Topologies

    Apr 7, 2026Jingkai Luo, Yulin ShaoCommunication Topology OptimizationMulti-Agent Communication Topology

    Department of Electrical and Computer Engineering, The University of Hong Kong, Hong Kong, China