Geodesic
On the spectra of general random graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider random graphs such that each edge is determined by an independent random variable, where the probability of each edge is not assumed to be equal. We use a Chernoff inequality for matrices to show that the eigenvalues of the adjacency matrix and the normalized Laplacian of such a random graph can be approximated by those of the weighted expectation graph, with error bounds dependent upon the minimum and maximum expected degrees. In particular, we use these results to bound the spectra of random graphs with given expected degree sequences, including random power law graphs. Moreover, we prove a similar result giving concentration of the spectrum of a matrix martingale on its expectation.
DOI : 10.37236/702
Classification : 05C80
Mots-clés : Chernoff inequality for matrices 
@article{10_37236_702,
     author = {Fan Chung and Mary Radcliffe},
     title = {On the spectra of general random graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/702},
     zbl = {1229.05248},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/702/}
}
TY  - JOUR
AU  - Fan Chung
AU  - Mary Radcliffe
TI  - On the spectra of general random graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/702/
DO  - 10.37236/702
ID  - 10_37236_702
ER  - 
%0 Journal Article
%A Fan Chung
%A Mary Radcliffe
%T On the spectra of general random graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/702/
%R 10.37236/702
%F 10_37236_702
Fan Chung; Mary Radcliffe. On the spectra of general random graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/702

Cité par Sources :