Noisy random graphs and their Laplacians |
| |
Authors: | Marianna Bolla |
| |
Institution: | Institute of Mathematics, Budapest University of Technology and Economics, P.O. Box 91. Bldg. H. V/7, 1521 Budapest, Hungary |
| |
Abstract: | Spectra and representations of some special weighted graphs are investigated with weight matrices consisting of homogeneous blocks. It is proved that a random perturbation of the weight matrix or that of the weighted Laplacian with a “Wigner-noise” will not have an effect on the order of the protruding eigenvalues and the representatives of the vertices will unveil the underlying block-structure.Such random graphs adequately describe some biological and social networks, the vertices of which belong either to loosely connected strata or to clusters with homogeneous edge-densities between any two of them, like the structure guaranteed by the Regularity Lemma of Szemerédi. |
| |
Keywords: | 05C50 15A42 |
本文献已被 ScienceDirect 等数据库收录! |
|