Asymptotic Spectra of Large (Grid) Graphs with a Uniform Local Structure (Part I): Theory
- PDF / 1,753,808 Bytes
- 46 Pages / 547.087 x 737.008 pts Page_size
- 85 Downloads / 136 Views
ilan Journal of Mathematics
Asymptotic Spectra of Large (Grid) Graphs with a Uniform Local Structure (Part I): Theory Andrea Adriani, Davide Bianchi and Stefano Serra-Capizzano Abstract. We are mainly concerned with sequences of graphs having a grid geometry, with a uniform local structure in a bounded domain Ω ⊂ Rd , d ≥ 1. When Ω = [0, 1], such graphs include the standard Toeplitz graphs and, for Ω = [0, 1]d , the considered class includes d-level Toeplitz graphs. In the general case, the underlying sequence of adjacency matrices has a canonical eigenvalue distribution, in the Weyl sense, and we show that we can associate to it a symbol f. The knowledge of the symbol and of its basic analytical features provides many information on the eigenvalue structure, of localization, spectral gap, clustering, and distribution type. Few generalizations are also considered in connection with the notion of generalized locally Toeplitz sequences and applications are discussed, stemming e.g. from the approximation of differential operators via numerical schemes. Nevertheless, more applications can be taken into account, since the results presented here can be applied as well to study the spectral properties of adjacency matrices and Laplacian operators of general large graphs and networks. Mathematics Subject Classification (2010). 05C50; 05C22; 34B45; 65N22. Keywords. Large graphs and networks; eigenvalues distribution; graph-Laplacian.
1. Introduction Spectral properties of the adjacency matrix and the Laplacian operator of graphs provide valuable insights regarding a large number of key features such as the Shannon capacity, Chromatic number, diameter, maximum cut, just to cite few of them, see [6, 35], which often play a central role in many applied real-world problems e.g. in physics and chemistry problems, see as references [15, 21, 34] and [12, Chapter 8]. In particular, graphs typically describe approximations of physical domains related The authors are supported by INdAM-GNCS Gruppo Nazionale per il Calcolo Scientifico.
2
A. Adriani, Bianchi S. Serra-Capizzano A. Adriani, D. D. Bianchi andand S. Serra-Capizzano
to self-adjoint second order linear differential operators: for example, the discretization of the Laplace differential operator with Dirichlet boundary conditions over a membrane Ω ∈ Rd produces the Laplacian matrix of a (possibly infinite) graph with its eigenvalues corresponding to the characteristic frequencies of the membrane, [12, p.256]. In the last few years there has been a rising interest over this topic, especially concerning spectral convergence of the graph-Laplacian towards the spectrum of its continuous counterpart, see the seminal work of D. Burago and coauthors [8] and applications in inverse problems regularization and machine learning, refer to [43, 44, 45]. Therefore, having a way to analytically measure the eigenvalue distribution of the adjacency matrix and the graph-Laplacian can be as precious as crucial in many applications. In this work we are interested in defining and studying a
Data Loading...
