Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks

Using methods from algebraic graph theory and convex optimization, we study the relationship between local structural features of a network and the eigenvalues of its Laplacian matrix. In particular, we propose a series of semidefinite programs to find new bounds on the spectral radius and the spectral gap of the Laplacian matrix in terms of a collection of local structural features of the network. Our analysis shows that the Laplacian spectral radius is strongly constrained by local structural features. On the other hand, we illustrate how local structural features are usually insufficient to accurately estimate the Laplacian spectral gap. As a consequence, random graph models in which only local structural features are prescribed are, in general, inadequate to faithfully model Laplacian spectral properties of a network.