The graph Laplacian of a finite connected undirected edge-weighted graph \(G \) is the symmetric matrix \(A\) whose off-diagonal entries \( a_{ij} \) are the edge-weights and whose diagonal entries are \( a_{ii} = - \sum_{j \ne i} a_{ij} \). The matrix \(A\) has leading eigenvalue \( 0 \) and second eigenvalue \( - \lambda_2 \), where this spectral gap \( \lambda_2 \) can be interpreted as a measure of connectivity.
Consider a given graph as above, which we now call \(G(\infty) \), and write gap(\(G(\infty)\)) for the spectral gap. For reasons indicated below we are interested in the process of random graphs \(( G(t), 0 \le t < \infty) \) constructed in two stages as follows. For each edge \(e = ij\) construct independently a Poisson counting process \(( N_{ij}(t), 0 \le t < \infty) \) of rate \( a_{ij} \). Conditional on these counts, let the edge-weights \( a_{ij}(t) \) of \( G(t) \) be independent with probability density functions $$ s \to t^{-1} p(N_{ij}(t); st) $$ where \(p(k; \lambda) \) denotes the Poisson( \(\lambda \)) probability function.
This is set up so that \( G(t) \to G(\infty) \) as \( t \to \infty \) but \( G(0) \) is independent of \(G(\infty) \); the edge-weights of \( G(0) \) are independent Exponential(1) random variables.
Problem: What can you say about the (real-valued, random) process
\( (\mbox{ gap }(G(t)), \ 0 \le t < \infty )\) ?
In particular:
(i) is the distribution of \(\mbox{ gap }(G(t)) \) concentrated near its expectation
(under weak assumptions, and for large graphs)?
(ii) How large must \(t\) be in order that \(\mbox{ gap }(G(t)) \) is close to \(\mbox{ gap }(G(\infty)) \) ?
This arises implicitly in Aldous-Li (2018) as a (very naive) Bayesian version of an "imperfectly observed network" model. In the frequentist version (discussed in that paper) the edge-weights are unknown constants and only the Poisson counts are observed; in the Bayes version one could put a flat prior on the edge-weights, and then \( G(t) \) is the posterior distribution on weighted graphs. We would like to compare frequentist and Bayesian estimates of the spectral gap.
Back to Open Problem list