# Rooted spectral measure of a graph

written by [@marc_lelarge](https://twitter.com/marc_lelarge)

For a graph $G$ with $n$ vertices, with symmetric adjacency matrix $A\in \mathbb{R}^{n\times n}$. For $i\in [n]$, we denote by $\lambda_i$ its eigenvalues and by $\psi_i$ its associated eigenvectors.

The empirical measure of $G$ is defined as:
\begin{align*}
\mu_G = \frac{1}{n}\sum_{i=1}^n \delta_{\lambda_i}
\end{align*}

The rooted spectral measure of $G$ at vertex $v\in [n]$ is defined by:
\begin{align*}
\mu_{(G,v)} = \sum_{i=1}^n \langle \psi_i, e_v\rangle^2\delta_{\lambda_i}
\end{align*}

We have the fundamental relation:
\begin{align*}
\mu_G = \frac{1}{n}\sum_{v=1}^n \mu_{(G,v)}
\end{align*}

The animation below shows the measure $\frac{1}{n}\sum_{v\leq k} \mu_{(G,v)}$ when $k\to \infty$.

$\mu_{(G,v)}$ can be interpreted as a local contribution of $v$ to the graph spectral measure $\mu_G$. For example, we have:
\begin{align*}
\int x^k d\mu_{(G,v)}(x) = \left(A^k\right)_{v,v} = \text{number of returning walks of length } k \text{ starting at }v.
\end{align*}

All the plots are done for an Erdős–Rényi random graph with 1000 nodes and average degree 3.

**For extensions to infinite graphs:**
- [Spectrum of random graphs](http://www.i2m.univ-amu.fr/perso/charles.bordenave/_media/courssrg.pdf) by Charles Bordenave

###### tags: `public` `math` `graph`