Empirical study of graph spectra and their limitations
View/ Open
Accepted version
Embargoed until: 2025-02-19
Embargoed until: 2025-02-19
Metadata
Show full item recordAbstract
We examine the sensitivity of community-structured graph spectra to graph size, block size and inter-block edge probability. We use the Planted Partition Model because of its transparency. While this generative model may seem simplistic, it allows us to isolate the effects of graph and block size, edge probabilities and, consequently, vertex degree distribution on spectra. These sensitivities to key graph characteristics also generalize beyond Planted Partition Model graphs, because they are based on graph structure. Notably, our results show that eigenvalues converge to those of a complete graph, with increases in graph size or inter-block edge probability. Such convergence severely limits the use of spectral techniques.
Authors
Shestopaloff, A; Miasnikof, P; Bravo, C; Lawryshyn, Y; Eleventh International Conference on Complex Networks and their ApplicationsCollections
- Mathematics [1478]