8
$\begingroup$

Let $G$ be an Erdos-Renyi random graph (i.e. an edge ($ij$) exists with probability $0 < p < 1$ and all edges are independent). Let $L$ be the Laplacian matrix of this graph (i.e $L=D-A$, where $A$ is the adjacency matrix of the graph and $D$ is diagonal with $D_{ii} = $ degree of node $i$). Let finally $0 = \lambda_0 \leq \lambda_1 \leq \lambda_2 \leq \cdots$ be the eigenvalues of $L$. Is an analytic expression known for the limiting empirical distribution of these eigenvalues, i.e. for

$\lim_{n \to \infty} \frac{1}{n} \#\{ 1 \leq j \leq n : \lambda_j \leq t \}, t \in \mathbb{R}?$

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I should add that I performed some simulations for this and obtained a deformed semi-circle law centered around $np$, with standard deviation of order $\sqrt{n}$, but it is definitely not a semi-circle law, as it has visible tails on each side. Plus, the shape of the limiting distribution changes significantly for $p$ close to either $0$ or $1$. $\endgroup$
    – Olivier Leveque
    Commented Jul 21, 2014 at 17:32

2 Answers 2

Reset to default
4
$\begingroup$

Maybe relevant:

"Lifshitz tails for spectra of Erdős–Rényi random graphs"

Oleksiy Khorunzhiy, Werner Kirsch, and Peter Müller

"We consider the discrete Laplace operator (the graph Laplacian) on Erdos–Rényi random graphs and show in Theorem 2.5 that the asymptotic behavior of its limiting integrated density of states at the lower spectral edge is given by a Lifshitz tail with Lifshitz exponent 1/2."

Improve this answer
$\endgroup$
1
  • $\begingroup$ OK, thanks! This is indeed a part of the answer. $\endgroup$
    – Olivier Leveque
    Commented Jul 22, 2014 at 12:23
3
$\begingroup$

As far as I know, the spectra of Laplacian of a graph follows a distribution that is the free additive convolution of a Gaussian and the semicircle law.

Take a look, for example at the article:

"Spectra of random graphs with arbitrary expected degrees" Raj Rao Nadakuditi, M. E. J. Newman

https://arxiv.org/abs/1208.1275

In your case the arbitrary expected degree is constant, therefore the computation should result simpler than in the more general case.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This paper does computations with the configuration model of random graphs. Is it easy to adapt those to the Erdős–Rényi model? $\endgroup$
    – j.c.
    Commented Apr 19, 2018 at 13:21
  • $\begingroup$ If you set $k_i= (n-1)p$ I think yes! Take a look where in the paper they compute the spectral density for a network with only two different degrees(section 5). The whole computation for the laplacian is not done though. $\endgroup$
    – linello
    Commented Apr 19, 2018 at 13:39
  • $\begingroup$ OK, I missed that they refer to the Erdős–Rényi random graph as the Poisson random graph. For the normalized Laplacian specifically, they cite a paper of Chung and Vu pnas.org/content/100/11/6313#sec-4 $\endgroup$
    – j.c.
    Commented Apr 19, 2018 at 13:55
  • $\begingroup$ Not being a mathematician but a physicist. I prefer the approach of Newman in terms of clarity and direct result. The Chung and Lu paper is more hard. Also take a look at Rao and Edelman software tool (reference 33,34 in the Newman's paper). $\endgroup$
    – linello
    Commented Apr 19, 2018 at 14:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .