Estimate graph distance measures using spectral properties

Question

I am interested in estimating graph distance measures such as shortest-path-length, diameter, radius, etc. using the Graph Laplacian spectrum. Is there an online resource (paper, article, blog) for that? If not, can you give hints as to how one can relate these distances with the Laplacian matrix? I understand $A, A^2, \cdots, A^n$ can give connectivity at different hops. So, one can possibly start from there.

Answer 1

$A^\ell_{i,j}$ represent the number of walks from vertex $i$ to vertex $j$ with length $\ell$, if for all $i,j$ for some $\ell$ it holds that $A^\ell_{i,j} \neq 0$ then the graph connected. If you want to measure the diameter of the graph add a self-loop for all the vertices (so if there is a path at length at most $\ell$ there is a path at length exact $\ell$) and find the minimum $\ell$ that satisfied for all $i,j$ it holds that $A^\ell_{i,j} \neq 0$ and that is the diameter of the graph.

Answer 2

It sounds like you're more interested in non-spectral forms of graph distance, which relate more closely with the adjacency matrix. Those theorems that do relate the Laplacian spectrum to diameter and shortest paths provide very poor bounds.

The distance metric most closely associated with the Laplacian matrix is the resistance distance, which is closely related to random walks. The copyleft text Random Walks and Electric Networks, available here, is a great introduction to random walks and spectral notions of distance.

The unfinished monograph Reversible Markov Chains and Random Walks on Graphs provides a few results on the diameter and distance, notably Corollary 4.34 and Section 6.3.1.

If you're willing to spend a little, Fan Chung's Spectral Graph Theory is inexpensive and contains the most relevant results to your question, especially chapters 1, 2, 3, 4, and 6. Two such results are as follows:

The normalized Laplacian of an undirected $G = (V, E)$ is the matrix $\mathcal L = D^{-1/2} L D^{-1/2}$. If $\lambda_1$ denotes the second-smallest eigenvalue of $\mathcal L$ and $\lambda_{n-1}$ the largest, fix $$ \lambda = \frac{\lambda_{n-1} + \lambda_1}{\lambda_{n-1} - \lambda_1}. $$ The diameter of $G$ is bounded above by $$ \DeclareMathOperator{\diam}{diam} \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator{\dist}{dist} \DeclareMathOperator{\vol}{vol} \diam(G) \leq \left\lceil \frac{\arccosh(n-1)}{\arccosh(\lambda)} \right\rceil. $$ Now, for $X, Y \subset V$, define the distance between the sets as $$ \dist(X, Y) = \min\{\dist(x, y): x \in X, y \in Y\}, $$ the volume of a set $\vol(X) = \sum_{x \in X} \deg(x)$, and fix $$ \vartheta = \sqrt{\frac{\vol(\bar X) \vol(\bar Y)}{\vol(X) \vol(Y)}}. $$ If $G$ is not a complete graph and $X \neq \bar Y$, $$ \dist(X, Y) \leq \left\lceil \frac{\arccosh(\vartheta)}{\arccosh(\lambda)} \right\rceil. $$