Noisy random graphs and their laplacians. (English) Zbl 1153.05062

Bolla, Marianna

Discrete Math. 308, No. 18, 4221-4230 (2008).

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 from the eigenvectors of \(A\).
The author also considers weighted Laplacians \(L^{\prime}(A)\), (recall the Laplacian is \(D-A\) where \(D\) is a diagonal matrix with diagonal entries the degrees of the vertices: then \(L^{\prime}(A)=I_{n}-D(A)^{-1/2}AD(A)^{-1/2}\) (if no vertex is isolated). She shows that, under the growth rate condition, there are \(k\) eigenvalues of \(L^{\prime}(B)\) which are not equal to 1 and they are located in the union of intervals \([0,1-\delta]\cup [1+\delta,2]\) for a constant \(\delta\in (0,1)\): the proof is again linear algebra. Again this leads to the statement of a similar result for \(L^{\prime}(A)\), which it is said will be proved in a later paper. Again eigenvectors of \(A\) will reveal the block structure in \(B\).
The author closes by discussing links with the Szemerédi Regularity Lemma briefly.

Reviewer: David B. Penman (Colchester)

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
15A42	Inequalities involving eigenvalues and eigenvectors

Keywords:

spectra of weighted graphs; Wigner-noise; weighted Laplacian; graph representation

References:

[1]	Achlioptas, D.; McSherry, F., Fast computation of low rank matrix approximations, (), 611-618 · Zbl 1311.94032
[2]	Alon, N.; Krivelevich, M.; Vu, V.H., On the concentration of eigenvalues of random symmetric matrices, Israel J. math., 131, 259-267, (2002) · Zbl 1014.15016
[3]	Bhatia, R., Matrix analysis, graduate texts in mathematics, vol. 169, (1996), Springer New York
[4]	Bolla, M.; Tusnády, G., Spectra and optimal partitions of weighted graphs, Discrete math., 128, 1-20, (1994) · Zbl 0796.05066
[5]	Bolla, M., Distribution of the eigenvalues of random block-matrices, Linear algebra appl., 377, 219-240, (2004) · Zbl 1042.15014
[6]	Bolla, M., Recognizing linear structure in noisy matrices, Linear algebra appl., 402, 228-244, (2005) · Zbl 1077.15019
[7]	Frieze, A.; Kannan, R., Quick approximation to matrices and applications, Combinatorica, 19, 2, 175-220, (1999) · Zbl 0933.68061
[8]	Füredi, Z.; Komlós, J., The eigenvalues of random symmetric matrices, Combinatorica, 1, 3, 233-241, (1981) · Zbl 0494.15010
[9]	Granovetter, M.S., The strength of weak ties, Amer. J. sociol., 78, 1360-1380, (1973)
[10]	J. Komlós, A. Shokoufanden, M. Simonovits, E. Szemerédi, Szemerédi’s Regularity Lemma and its Applications in Graph Theory, Lecture Notes in Computer Science, vol. 2292, Springer, Berlin, 2002, pp. 84-112.
[11]	Wigner, E.P., On the distribution of the roots of certain symmetric matrices, Ann. math., 62, 325-327, (1958) · Zbl 0085.13203