Skip to Main content Skip to Navigation
Journal articles

The Laplacian Spectrum of Large Graphs Sampled from Graphons

Renato Vizuete 1, 2 Federica Garin 2 Paolo Frasca 2
2 DANCE - Dynamics and Control of Networks
Inria Grenoble - Rhône-Alpes, GIPSA-PAD - GIPSA Pôle Automatique et Diagnostic
Abstract : This paper studies the Laplacian spectrum and the average effective resistance of (large) graphs that are sampled from graphons. Broadly speaking, our main finding is that the Laplacian eigenvalues of a large dense graph can be effectively approximated by using the degree function of the corresponding graphon. More specifically, we show how to approximate the distribution of the Laplacian eigenvalues and the average effective resistance (Kirchhoff index) of the graph. For all cases, we provide explicit bounds on the approximation errors and derive the asymptotic rates at which the errors go to zero when the number of nodes goes to infinity. Our main results are proved under the conditions that the graphon is piecewise Lipschitz and bounded away from zero.
Complete list of metadata

https://hal-centralesupelec.archives-ouvertes.fr/hal-03197046
Contributor : Renato Sebastian Vizuete Haro Connect in order to contact the contributor
Submitted on : Tuesday, April 13, 2021 - 2:26:17 PM
Last modification on : Tuesday, October 19, 2021 - 11:18:17 AM
Long-term archiving on: : Wednesday, July 14, 2021 - 6:37:37 PM

File

The Laplacian Spectrum of Larg...
Files produced by the author(s)

Identifiers

`

Citation

Renato Vizuete, Federica Garin, Paolo Frasca. The Laplacian Spectrum of Large Graphs Sampled from Graphons. IEEE Transactions on Network Science and Engineering, IEEE, 2021, 8 (2), pp.1711-1721. ⟨10.1109/TNSE.2021.3069675⟩. ⟨hal-03197046⟩

Share

Metrics

Record views

122

Files downloads

149