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}?$

$\endgroup$
  • 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 Jul 21 '14 at 17:32
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."

$\endgroup$
  • $\begingroup$ OK, thanks! This is indeed a part of the answer. $\endgroup$ – Olivier Leveque Jul 22 '14 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.

$\endgroup$
  • $\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. Apr 19 '18 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 Apr 19 '18 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. Apr 19 '18 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 Apr 19 '18 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.