- #1

Master1022

- 611

- 117

- Homework Statement
- For an undirected graph with affinity matrix (i.e. weighted adjacency matrix) ##A##, how can we determine a good cluster using eigenvalues and eigenvectors.

- Relevant Equations
- Eigenvectors and eigenvalues

Hi,

I was reading through some slides about graph clustering. In the slides was a very short discussion about 'eigenvectors and segmentation'. I don't quite understand where one of the formulae comes from.

It then says: "The element associated with the cluster should have large values connecting one another in the affinity matrix." and then quotes the following formula:

[tex] \mathbf{w}_n ^T A \mathbf{w} [/tex]

where it defines ##\mathbf{w}_{n} ^ T ##

I was reading through some slides about graph clustering. In the slides was a very short discussion about 'eigenvectors and segmentation'. I don't quite understand where one of the formulae comes from.

**Context:**We have some undirected graph with an affinity matrix (i.e. weighted adjacency matrix) ##A##. The slide poses the question:*What is a good cluster?*It then says: "The element associated with the cluster should have large values connecting one another in the affinity matrix." and then quotes the following formula:

[tex] \mathbf{w}_n ^T A \mathbf{w} [/tex]

where it defines ##\mathbf{w}_{n} ^ T ##

*= association of element ##i## to cluster ##n##.*

It then says we can impose a scaling requirement such that ## \mathbf{w}_n ^T \mathbf{w}_n = 1 ##. Putting these two equations together yields the familiar eigenvalue equation.

It then says we can impose a scaling requirement such that ## \mathbf{w}_n ^T \mathbf{w}_n = 1 ##. Putting these two equations together yields the familiar eigenvalue equation.

**Question:**Where does this first formula come from: ## \mathbf{w}_n ^T A \mathbf{w} ##? As much as I think about it, it doesn't really make much sense to me. I can understand the latter parts of the slide, so if I just move past my misunderstanding, then the rest falls into place. However, I am keen to understand what that 'score' is really calculating.