Tighter spectral bounds for the cut size, based on Laplacian eigenvectors

Tighter spectral bounds for the cut size, based on Laplacian eigenvectors

Devriendt, K.L.T. (TU Delft Network Architectures and Services)
Van Mieghem, P.F.A. (TU Delft Network Architectures and Services)

2019

The cut-set ∂V in a graph is defined as the set of all links between a set of nodes V and all other nodes in that graph. Finding bounds for the size of a cut-set |∂V| is an important problem, and is related to mixing times, connectedness and spreading processes on networks. A standard way to bound the number of links in a cut-set |∂V| relies on Laplacian eigenvalues, which approximate the largest and smallest possible cut-sets for a given size of the set V. In this article, we extend the standard spectral approximations by including information about the Laplacian eigenvectors. This additional information leads to provably tighter bounds compared to the standard spectral bounds. We apply our new method to find improved spectral bounds for the well-known Cheeger constant, the Max Cut problem and the expander mixing lemma. We also apply our bounds to study cut sizes in the hypercube graph, and describe an application related to the spreading of epidemics on networks. We further illustrate the performance of our new bounds using simulations, revealing that a significant improvement over the standard bounds is possible.

Cheeger inequality
Graph cut
Laplacian matrix
Network epidemics
Spectral graph theory

http://resolver.tudelft.nl/uuid:19e46ea7-ec92-4b4c-a728-13e9ea35dfbc

https://doi.org/10.1016/j.laa.2019.02.025

2021-03-13

0024-3795

Linear Algebra and Its Applications, 572, 68-91

Accepted author manuscript

Institutional Repository

journal article

© 2019 K.L.T. Devriendt, P.F.A. Van Mieghem