The is closely related to the .

## Two Clusters

Given a vector $\mathbf a$,

$$\mathbf a[u] = \begin{cases} \sqrt{ \frac{ \lvert \bar{\mathcal A} \rvert }{ \lvert \mathcal A \rvert } }, & u\in \mathcal A \\ -\sqrt{ \frac{ \lvert \mathcal A \rvert } { \lvert \bar{\mathcal A} \rvert }}, & u\in \bar{\mathcal A} \end{cases}.$$

We have

• $\sum_{u\in\mathcal V} \mathbf a[u] = 0$, and
• $\lVert{\mathbf a}\rVert = \lvert \mathcal V \rvert$.

Using $\mathbf a$, we have1

$$\mathbf a^T \mathbf L \mathbf a = \lvert \mathcal V \rvert \operatorname{RatioCut}(\mathcal A, \bar{\mathcal A}).$$

This result is useful as the Rayleigh-Ritz theorem tells us that $\mathbf a$ is the second smallest eigenvector of $\mathbf L$.

We can assign nodes to different groups based on $\mathbf a$.

• If $\mathbf a[u] \geq 0$, we know $u\in\mathcal A$;
• If $\mathbf a[u] \lt 0$, we know $u\in\bar{\mathcal A}$.

## Multiple Clusters

Refer to chapter 2 of Hamilton20201.

Planted: by ;

L Ma (2021). 'Graphs Spectral Methods', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/wiki/graph/basics/graph-spectral-methods/.