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 underlyingsequence of adjacency matrices has a canonical eigenvalue distribution, inthe Weyl sense, and we show that we can associate to it a symbol f. The knowledgeof the symbol and of its basic analytical features provides many information onthe eigenvalue structure, of localization, spectral gap, clustering, and distributiontype. Few generalizations are also considered in connection with the notion of generalizedlocally 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 presentedhere can be applied as well to study the spectral properties of adjacency matricesand Laplacian operators of general large graphs and networks.

Asymptotic Spectra of Large (Grid) Graphs with a Uniform Local Structure (Part I): Theory

Serra Capizzano S.
2020-01-01

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 underlyingsequence of adjacency matrices has a canonical eigenvalue distribution, inthe Weyl sense, and we show that we can associate to it a symbol f. The knowledgeof the symbol and of its basic analytical features provides many information onthe eigenvalue structure, of localization, spectral gap, clustering, and distributiontype. Few generalizations are also considered in connection with the notion of generalizedlocally 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 presentedhere can be applied as well to study the spectral properties of adjacency matricesand Laplacian operators of general large graphs and networks.
2020
eigenvalues distribution; graph-Laplacian; Large graphs and networks
Adriani, A.; Bianchi, D.; Serra Capizzano, S.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2119495
 Attenzione

L'Ateneo sottopone a validazione solo i file PDF allegati

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact