On spectrum of an adjacencies matrix of almost-complete graph

S. V. Kozlukov

Matematičeskaâ fizika i kompʹûternoe modelirovanie, Tome 20 (2017) no. 4, pp. 18-25.

Résumé

Let $\mathcal{A}_{MN}$ be a $N \times N$ matrix composed of $N^2-M$ unities and $M$ zeroes. Considered as an adjacencies matrix, $\mathcal{A}_{MN}$ corresponds to a complete digraph with loops on $N$ vertices with some $M$ out of $N^2$ edges removed. Someimportant properties of a graph are determined by its spectrum. For example Wang et al. [4] proposed a discrete-time model of viral propagation in a network. In that model a virus will die out or linger on depending on whether the ratio of curing and infection rates is below or above the treshold value. As Wang et al. have shown that treshold value is the spectral radius of the adjacencies matrix of the network graph, i.e. the maximal absolute value of its eigenvalues. More comprehensive description of spectral graph theory and its application is given by Cv`etkovic et al. [3]. This article analyzes spectral properties of such matrices. The matrix $\mathcal{A}_{MN}$ can be represented in the form $\mathcal{A}_{MN}=\mathcal{J}_N-\mathfrak{B}_{MN}$, where $\mathcal{J}_N$ is a $N \times N$ matrix whose all entries are ones and $\mathfrak{B}_{MN}$ has unities exactly at these $M$ places where $\mathcal{A}_{MN}$ has zeroes. The spectrum of $\mathcal{J}_N$ can be easily computed: $\mathcal{J}_N^2=N\mathcal{J}$ , so $\lambda$ is the minimal annihilating polynomial of $\mathcal{J}_N$ and hence the spectrum of $\mathcal{J}_N$ is $\sigma(\mathcal{J}_N)=\{0,N\}$. For small enough $M$ the eigenvalues of $\mathcal{A}_{MN}$ will be “close” to those of $\mathcal{J}_N$. Then The Method of Similar Operators [1; 2] is used, which allows in the case of perturbation of some ideal object (whose properties are known) to find an element of the algebra under consideration similar to the disturbed one yet having “simpler” structure. Via this method the following theorem is proven: Theorem. Let $M\frac{N^2}{16}$, then the spectrum of $\mathcal{A}_{MN}$ can be represented as a disjoint union $\sigma(\mathcal{A}_{MN})=\sigma_1\cup \sigma_2$ of a singletone $\sigma_1=\{\lambda_1\}$ and the set $\sigma_2$, satisfying the following conditions: $$ \sigma_1\subset\{\mu\in\mathbb{R};|\mu-N|4\sqrt{M}\}, $$ $$ \sigma_2\subset\{\mu\in\mathbb{C};|\mu|4\sqrt{M}\}. $$

Détail

Keywords: the method of similar operators, graph spectra, eigenvalues localization, nonlinear equations, contraction theory.
Mots-clés : Jordan normal form

Bibliographie

[1] A. G. Baskakov, Harmonic analysis of linear operators, VGU Publ., Voronezh, 1987, 165 pp. | MR

[2] A. G. Baskakov, “Analysis of Linear Differential Equations by Methods of the Spectral Theory of Difference Operators and Linear Relations”, Russian Mathematical Surveys, 8:1 (2002), 1–16 | MR

[3] D. M. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs: Theory and Applications, 3rd revision, Wiley, N. Y., 1998, 368 pp. | MR

[4] Y. Wang, D. Chakrabarti, C. Wang, C. Faloutsos, “Epidemic Spreading in Real Networks: an Eigenvalue Viewpoint”, 22nd International Symposium on Reliable Distributed Systems (Oct. 2003), 2003, 25–34