Noisy random graphs and their laplacians
type: Item
instance of: scholarly article
title: Noisy random graphs and their laplacians
zbMATH Open document ID: 1153.05062
author: Marianna Bolla
published in: Discrete Mathematics
publication date: 2008-09-04T00:00:00Z
review text: This paper deals with the spectra of weighted graphs. Define a Wigner-noise matrix to be an \(n\times n\) matrix \(W\) whose entries \(w_{ij}\) are uniformly bounded random variables with expectations zero and variances bounded by some \({\sigma^2}\), informally, a small noisy perturbation matrix. The eigenvalues of such \(W\) are known to be \` small\'\, with probability tending to 1, in a precise sense, by a result of Füredi and Komlós. The author then considers the effect of replacing a weighted adjacency matrix \(B\) of some \(n\)-vertex graph \(G\) by \(A=W+B\) where \(W\) is a Wigner-noise matrix for certain particular choices of weighted graph \(G\) with \(n\) vertices and weighted adjacency matrix \(B\). At first, \(B\) is a Kronecker-sum of \(n_{i}\times n_{i}\) matrices \(B_{i}\) (where \(\sum_{i=1}^{k}n_{i}=n\)) and each \(B_{i}\) has all off-diagonal entries equal to \(\mu_{i}\) and all diagonal entries equal to \(\nu_{i}\). (Thus \(G\) has \(k\) components, each pair of vertices connected with an edge of the same weight). Somewhat more generally, \(B\) has a so-called pattern matrix: this means that \(V(G)=V_{1}\cup V_{2}\cup \ldots \cup V_{k}\) where \(| V_{i}|=n_{i}\) and all edge weights between a vertex in \(V_{i}\) and one in \(V_{j}\) have weight \(p_{ij}\): here \(P=(p_{ij})\) is the \(k\times k\) pattern matrix. \(B\) is then called a blown-up matrix. For both cases, the author has proven in earlier papers that there are \(k\) \` protruding\'\, eigenvalues of order \(\Theta(n)\) of \(B\) with the others being smaller, provided the so-called growth condition holds, namely that each \(n_{i}\geq Cn\). Section 2 of the paper uses linear algebra methods to give an alternative proof that, under the growth rate condition, all non-zero eigenvalues of the \(n\times n\) blown-up matrix \(B\) are order \(n\) in absolute value. This then leads to the fact that the protruding eigenvalues of \(A\) can be found and the block structure of \(B\) can be read off …
reviewed by: David B. Penman
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A42
zbMATH DE Number: 5321292
zbMATH Keywords: spectra of weighted graphs
zbMATH Keywords: Wigner-noise
zbMATH Keywords: weighted Laplacian
zbMATH Keywords: graph representation
MaRDI profile type: Publication
full work available at URL: j.disc.2007.08.023
OpenAlex ID: W2119262992
cites work: Fast computation of low rank matrix approximations
cites work: On the concentration of eigenvalues of random symmetric matrices
cites work: Q5690490
cites work: Spectra and optimal partitions of weighted graphs
cites work: Distribution of the eigenvalues of random block-matrices.
cites work: Recognizing linear structure in noisy matrices
cites work: Quick approximation to matrices and applications
cites work: The eigenvalues of random symmetric matrices
cites work: Q4736881
cites work: On the distribution of the roots of certain symmetric matrices
DOI: 10.1016/J.DISC.2007.08.023
description: scientific article; zbMATH DE number 5321292