Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality.

What do the second, third, etc. eigenvectors tell us?

Motivation: A standard information retrieval technique (LSI) uses a truncated SVD as a low-rank approximation of a matrix. If we truncate to rank 1, then we essentially have a PageRank algorithm. I was wondering if there are ways of interpreting the corrections introduced by higher eigenvectors.

Something similar to what the moments of a distribution tell us (e.g. first moment gives us the mean, second tells us the variance, third gives us skewness, etc).

share|improve this question
5  
The second smallest eigenvector can be used to partition the graph into clusters, via spectral clustering from wikipedia. It's would be interesting to see the usage of all different eigenvectors –  com Mar 6 '12 at 10:15
5  
My note ---"Spectral Realizations of Graphs" ( daylateanddollarshort.com/math/pdfs/spectral.pdf )--- explains that a matrix whose rows form an orthogonal basis of an eigenspace of a graph's adjacency matrix has columns that serve as the coordinate vectors of a geometric realization for which automorphisms are induced by rigid isometries. That is, eigenvectors construct visual models of a graph's automorphic structure. The exact contribution a particular eigen-model makes to the understanding of that structure isn't necessarily obvious, but the pictures can be pretty cool. :) –  Blue Mar 9 '12 at 0:51
    
Why do you ask about the spectrum of the adjacency as opposed to that of the signed and/or unsigned graph Laplacian matrix, which are the typical objects of study in spectral graph theory? Eg, math.ucsd.edu/~fan/research/cb/ch1.pdf, buzzard.ups.edu/bookreview/eigenspaces-graphs-beezer-review.pdf –  alancalvitti Jul 17 '12 at 1:17

1 Answer 1

The second eigenvalue of a markov chain has meaning, and it affects (for example) the convergence and stability of algorithms that find the equilibrium distribution. See The second eigenvalue of the Google matrix, by Haveliwala and Kamvar for a discussion on how to compute its value.

The second eigenvector, however, has to be something more complex. Given that the PageRank matrix is a reversible markov chain (by construction), it has a unique equilibrium distribution. So the only vector v for which P v = v is the first eigenvector. So, the second eigenvector does not necessarily represent a probability distribution. According to Fluctuation Induced Almost Invariant Sets, by Schwartz and Billings, if a reversible markov chain represents a linear dynamical system the second eigenvector is a good way of finding almost invariant sets, which are subsets of the pages in which the perfect stochastic user would spend a long time "trapped in" before leaving to other parts of the web. The signs of the entries of the second eigenvector (and the third, and maybe others) can be used to find these almost invariant sets.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.