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.

When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

Here are some things you can learn from eigenvalues.

If there are $d$ distinct eigenvalues, then the diameter of the graph is at least $d+1$.

If a graph is $k$-regular, then the multiplicity of $k$ as an eigenvalue gives you the number of connected components in the graph. In general, if a graph is connected, then the largest eigenvalue must have multiplicity 1.

For strongly regular graphs, you can use information about the eigenvalues and their multiplicities to determine if certain parameter values are even possible. That is, if we have a strongly regular graph with parameters (n, k, a, c), then there exists one eigenvalue of multiplicity 1 and two other eigenvalues, $\theta$ and $\tau$. These eigenvalues have multiplicities:

$m_\theta = \frac{1}{2} \left( (n-1) - \frac{2k+(n-1)(a-c)}{\sqrt{\Delta}}\right)$

and

$m_\tau = \frac{1}{2} \left( (n-1) + \frac{2k+(n-1)(a-c)}{\sqrt{\Delta}}\right)$

where $\Delta = (a - c)^2 + 4(k - c)$. Since these represent eigenvalue multiplicities, they must be integers. Therefore, any parameter values (n, k, a, c) which do not give integer values for these multiplicities, are not possible.

See Algebraic Graph Theory by Godsil and Royle, chapter 10, for more on this.

If you are interested in learning about the connection between eigenvalues and graphs, then read a book. You already know the term spectral analysis. Read Spectra of Graphs, for instance:

http://homepages.cwi.nl/~aeb/math/ipm/ipm.pdf

P14 of this book gives the first result I gave, plus the proof.

share|improve this answer
    
The first eigenvalue also bounds the Cheeger constant of the graph, which gives you information about whether it has any bottlenecks. –  Neal Mar 13 '12 at 17:42
    
But how can you connect notion of eigen values and graph theory?i'm not getting this point –  user997704 Mar 13 '12 at 17:43
    
@user997704 The diameter is a notion of graph theory. I explained one connection between graphs and their eigenvalues, which involves the diameter. I'm not sure what you mean? I'm not saying my answer gives you a complete picture. I'm giving you a bit of information. –  Graphth Mar 13 '12 at 17:44
    
I got wht u r saying but is there any proof for this statement?How did u come to this statement?Please post some mathematical proof –  user997704 Mar 13 '12 at 17:46
    
@user997704 See Algebraic Graph Theory by Biggs. It has the proof in it. –  Graphth Mar 13 '12 at 17:48

The dominant (largest) eigenvalue can be used to tell you which node(s) are the most connected. Since the matrix is symmetric, it is diagonalizable (in fact, orthogonally diagonalizable, but diagonalizable is enough for what follows).

So all $n$-vectors can be written as a linear combination of eigenvectors. Say $$\vec{x}=\sum_{i=1}^nc_i\vec{v}_i$$ where $\vec{v}_i$ is an eigenvector for $\lambda_i$ and $\lambda_1$ is the dominant eigenvalue.

In particular, apply this to the columns of the matrix $\vec{a_j}$: $$\vec{a_j}=\sum_{i=1}^nc_{ij}\vec{v}_i$$

I assume you understand that $A^n$ shows you how many paths there are of length $n$ from each vertex $i$ to each vertex $j$. But $$A^n=A^{n-1}A=\begin{bmatrix}A^{n-1}\vec{a}_j\end{bmatrix}=\begin{bmatrix}\sum_{i=1}^nc_{ij}\lambda_i^{n-1}\vec{v}_i\end{bmatrix}$$ For large $n$, $\lambda_1^{n-1}$ is relatively much larger than all other such terms. So $$A^n\approx\begin{bmatrix}c_{1j}\lambda_1^{n-1}\vec{v}_1\end{bmatrix}$$ where the $\approx$ comparison is made entry by entry and compares entires by looking for ratios close to $1$. (I'm being informal, for ease of reading).

Thus the columns of $A^n$ are proportional to $\vec{v}_1$, so for each column of $A^n$, the entries of $\vec{v}_1$ tell you which entries are largest, which in turn tells you which nodes have the most paths of length $n$ to each of the other nodes. As $n$ gets larger, this feature of $A^n$'s columns won't change. So in a nice sense, you will understand which nodes are the most connected to other nodes through paths of long-enough lengths.

share|improve this answer
    
Seems reasonable.Can I get more material regarding spectra of graphs apart from homepages.cwi.nl/~aeb/math/ipm.pdf ,this seems good book but i'm looking for quick material.... –  user997704 Mar 13 '12 at 18:08
    
@user997704 Read chapter 1. That's not that complicated and that would be quick and you'd learn a lot. –  Graphth Mar 13 '12 at 18:15

The ratio between the largest and smallest eigenvalue can be used to estimate the chromatic number: $$ \chi(G)\ge1+\frac{\lambda_{\min}}{\lambda_\max}. $$ A proof can be found here (Theorem 2.4).

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.