“Just as astronomers use stellar spectra to determine the make-up of distant stars… [we aim] to deduce the properties and structure of [networks] from its spectrum.”
-Chapter 1, Spectral Graph Theory by F.R.K. Chung

## Laplacian and eigenvalues

• $x^T\mathcal{L}x=\frac{1}{2}\sum w_{ij}(x_i-x_j)^2$
• $\mathcal{L}\times \mathbf{1} = \mathbf{0}$ 即0肯定为Laplacian的一个特征值
• $0=\lambda_1 \lt \lambda_2 \le …\lambda_n$

Laplacian可以被看作是一种函数空间上函数的一种操作，该空间中的函数$g:V(G)\rightarrow\mathbb{R}$将每个节点都映射到一个数上去。这种操作满足：