SPECTRAL GAP ESTIMATES FOR PERTURBED GRAPH LAPLACIANS ON NON-UNIFORM NETWORKS

The algebraic connectivity of a graph, the second-smallest eigenvalue of its Laplacian, governs how fast information mixes and how resilient a network stays when edges are added or dropped. Most classical perturbation bounds, built around Weyl's inequality, assume near-regular degree sequences, which is precisely the assumption real networks tend to break. This paper asks a narrower and more testable question: how does the spectral gap actually move under controlled edge rewiring once a network stops being uniform, and how tight is the standard operator-norm bound when it does? Four network families of matched size, an Erdos-Renyi baseline, a Barabasi-Albert scale-free graph, a Watts-Strogatz small-world graph, and a heavy-tailed configuration model, were generated at three node scales and subjected to rewiring at five intensities. The Laplacian spectrum was recomputed at every step and the observed change in the gap was checked against the Weyl bound derived from the spectral norm of the perturbation matrix. Heterogeneous, high-variance degree sequences absorbed rewiring with a shrinking gap and a bound that stayed loose, ratios below 0.01 in the heavy-tailed case, while near-regular structures tracked the bound far more closely. A regression of gap sensitivity on degree coefficient of variation returned a correlation of -0.68, indicating that heterogeneity itself, not merely network size, predicts how conservative the classical estimate becomes. The results argue for heterogeneity-aware correction terms in spectral stability theory rather than uniform worst-case bounds applied indiscriminately across network types.