3
$\begingroup$

I find the theorem for largest eigenvalue of the adjacency matrix of ER random graph in here https://arxiv.org/pdf/math/0106066.pdf. The adjacency matrix is a symmetric random matrix s.t. diagonal values are all fixed as 0, and all entries above the diagonal are i.i.d. Bernoulli($p$) random variables, for some fixed $p\in[0,1]$.

enter image description here

For a weighted random graph, each edge in the adjacency matrix is represented by decimal in $[0,1]$ drawn from a uniform distribution over $[0,1]$ (or possibly other distribution over $[0,1]$). The adjacency matrix is a symmetric random matrix s.t. diagonal values are all zero, and every entry above the diagonal is drawn uniformly at random from $[0,1]$.

My question is,

Is there similar known result about the largest eigenvalue for weighted random graph?

$\endgroup$

2 Answers 2

3
$\begingroup$

The question is not completely clear. Do you fix a random $G(n,p)$ and then replace the $1$ in the adjacency matrix by a uniform random variable? Or is it as you write at the end, namely you just take a matrix with iid uniform entries (except for the symmetry constraint)?

If $p$ is of order one, or if the second interpretation is correct, then the top eigenvalue concentrates near $n EW$ where $W$ is the edge weight (so $EW=p/2$ in the first model and $EW=1/2$ in the second). See the answer to Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s

If you are dealing with the first model and $p=p(n)\to 0$ but $pn\to\infty$, the situation I believe is similar but requires more work to be proved.

$\endgroup$
1
$\begingroup$

When $p$ is reasonably large, you are basically looking at a random symmetric matrix, so any insight would come from the Tracy-Widom theory.

$\endgroup$
2
  • $\begingroup$ Not quite, there is a shift in mean. $\endgroup$ Commented Jan 16, 2018 at 7:04
  • $\begingroup$ @oferzeitouni Yes, I know, which is why I phrased it in a more cautious way... $\endgroup$
    – Igor Rivin
    Commented Jan 16, 2018 at 13:53

You must log in to answer this question.

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