Comparing Spectra of Graph Shift Operator Matrices

Autor:	Johannes F. Lutzeyer, Andrew T. Walden
Rok vydání:	2019
Předmět:	Discrete mathematics Matrix (mathematics) Eigengap Degree (graph theory) Stochastic block model Spectrum (functional analysis) Adjacency matrix Shift operator Eigenvalues and eigenvectors Mathematics
Zdroj:	Complex Networks and Their Applications VIII ISBN: 9783030366827 COMPLEX NETWORKS (2)
Popis:	Typically network structures are represented by one of three different graph shift operator matrices: the adjacency matrix and unnormalised and normalised Laplacian matrices. To enable a sensible comparison of their spectral (eigenvalue) properties, an affine transform is first applied to one of them, which preserves eigengaps. Bounds, which depend on the minimum and maximum degree of the network, are given on the resulting eigenvalue differences. The monotonicity of the bounds and the structure of networks are related. Bounds, which again depend on the minimum and maximum degree of the network, are also given for normalised eigengap differences, used in spectral clustering. Results are illustrated on the karate dataset and a stochastic block model. If the degree extreme difference is large, different choices of graph shift operator matrix may give rise to disparate inference drawn from network analysis; contrariwise, smaller degree extreme difference results in consistent inference.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d081515b010ad6e05dd6d1a7f57ef3fa https://doi.org/10.1007/978-3-030-36683-4_16 Zobrazit plný text záznamu