The first eigenvalue of a graph - what does it reflect? - MathOverflow

The first eigenvalue of a graph - what does it reflect?

2011-05-01T08:22:07Z

A big-picture question: what "physical properties" of a graph, and in particular of a bipartite graph, are encoded by its largest eigenvalue? If $U$ and $V$ are the partite sets of the graph, with the corresponding degree sequences $d_U$ and $d_V$, then it is easy to see that the largest eigenvalue $\lambda_{\max}$ satisfies $$ \sqrt{\|d_U\|_2\|d_V\|_2} \le \lambda_{\max} \le \sqrt{\|d_U\|_\infty\|d_V\|_\infty}; $$ in particular, if the graph is $(r_U,r_V)$ -regular, then $\lambda_{\max}=\sqrt{r_Ur_V}$ . (A reference, particularly for the double inequality above, will be appreciated.) In the general case, the largest eigenvalue also reflects in some way the "average degree" of a vertex - but is anything more specific known about it? To put it simply,

What properties of a (bipartite) graph can be read from its largest eigenvalue?

A brief summary and common reply to all those who have answered so far.

Thanks for your interest and care!
To make it very clear: I am interested in the usual, not Laplacian eigenvalues.
Although the largest eigenvalue is related to the average degree, for non-regular graphs this does not tell much; hence, I believe, understanding the meaning of the largest eigenvalue in terms of the "standard" properties of the graph is of certain interest.
It is true that different bipartite graphs (as $K_{1,ab}$ and $K_{a,b}$) may have the same largest eigenvalue, but, I believe, this does not mean that the largest eigenvalue cannot be suitably interpreted.
I still could not find a reference to the displayed inequality above. (@kimball: Lovasz does not have it.)

Answer by Nilima Nigam for The first eigenvalue of a graph - what does it reflect?

2011-05-01T15:48:05Z

I fear my answer may not directly address the question, but I like the question!

Suppose we wish to numerically approximate solutions of the Poisson problem on a given domain. One strategy is to 'mesh' the region by simplices, and seek information on the nodes. One can approximate the Laplacian either strongly (finite differences) or weakly (finite elements) on the resultant graphs. The resultant matrices are symmetric and positive definite. Their largest eigenvalue reflect their condition number, which usually scales as $1/h^2$ as the length of edges $h \rightarrow 0.$ This condition number $\kappa:=|\lambda_{max}|/|\lambda_{min}|$ tells us how sensitive the computed solution will be to small errors in data, eg. due to rounding. Were I to change the data locally on one of the simplices, for example by marginally changing the location of one node, $\kappa$ predicts the worst amount by which computed solutions may change.

I conjecture there is a similar result in graph theory: given a graph, its largest eigenvalue provides a measure of how small changes to the graph structure influence flows on the graph. But I don't know enough about graph theory to even frame the conjecture precisely.

Answer by ght for The first eigenvalue of a graph - what does it reflect?

2011-05-01T16:08:49Z

Please find here some relations between the eigenvalues of the Laplacian and properties of the graph. You can also take a look at Fan Chung's book "Spectral Graph Theory" where many properties are discussed and the first four chapters are available online here.

Answer by Chris Godsil for The first eigenvalue of a graph - what does it reflect?

2011-05-01T18:00:48Z

(This is just an overlong comment.)

A basic problem is that the complete bipartite graphs $K_{1,ab}$ and $K_{a,b}$ have the same spectral radius, and these graphs would not usually be viewed as similar. And, of course, all $k$-regular bipartite graphs have the same spectral radius.

Also if $A$ is the adjacency matrix of some graph, then the spectral radius of the bipartite graph with adjacency matrix $$\left( \begin{array}{cc} 0 & A \\ A & 0 \end{array} \right)$$ is the square of the spectral radius of $A$. So the question as to what properties of a graph are determined by its spectral radius is a subcase of your question. (I am not arguing that the two problems are equivalent.)

Answer by Kimball for The first eigenvalue of a graph - what does it reflect?

2011-05-01T18:04:36Z

Lovasz seems to think the largest eigenvalue is not so interesting (if the graph is connected), but the first gap tells you more.

www.cs.elte.hu/~lovasz/eigenvals-x.pdf

I believe this contains the double inequality you mentioned also. I also found some slides that give some motivation for looking at the largest eigenvalues:

math.uprm.edu/~xryong/SelectedTalks/Summer08-1.pdf

Answer by Balazs for The first eigenvalue of a graph - what does it reflect?

2011-05-02T12:10:59Z

I am not at all an expert on this, but I believe that the largest eigenvalue plays a role in several graph processes that people working in "network science" are interested in. A google search for "largest eigenvalue network" brought up this paper whose abstract begins "The largest eigenvalue of the adjacency matrix of a network plays an important role in several network processes (e.g., synchronization of oscillators, percolation on directed networks, linear stability of equilibria of network coupled systems, etc.)"; see references in the first paragraph of the paper to substantiate this claim.

Answer by ARupinski for The first eigenvalue of a graph - what does it reflect?

2011-05-02T14:20:37Z

The few times I have ever worked with eigenvalues of graphs, it has been in relation to the path algebra of the graph; each path in the graph is an element of this algebra. At any rate, the characteristic polynomial of the graph gives exact recurrences for calculating the number of paths of a given length and in particular the largest eigenvalue will give the asymptotic growth rate of the number of paths of different lengths. This asymptotic growth is true if the largest eigenvalue has modulus larger than all other eigenvalues of the graph. If there are multiple eigenvalues of maximum modulus then the asymptotics of the path-growth function will change although offhand I don't know if having multiple eigenvalues of the same maximal modulus is actually possible (perhaps someone who does more graph theory than I would care to comment on this).

Answer by Mahmoud El Chamie for The first eigenvalue of a graph - what does it reflect?

2012-07-10T16:43:35Z

The largest eigenvalue $\Lambda (A)$ of the adjacency matrix $A$ of a general graph satisfies the following inequality:

$\max \ ( d_{av},\sqrt{d_{max}} ) \le \Lambda (A) \le d_{max}$ ,

where $d_{av}$ is the average degree of nodes in the graph and $d_{max}$ is the largest degree.

The proof of this inequality is found in the small survey I wrote about the most important spectral properties of a graph here. You can also check the references in the report for more detailed properties.

Answer by Dan Stahlke for The first eigenvalue of a graph - what does it reflect?

2012-08-16T15:39:42Z

Assume the graph is connected.

Let $\left| 1 \right>$ be the vector of all 1's (in Dirac notation), and let $A$ be the adjacency matrix. Then $\left<1|A|1\right>$ is the number of edges of the graph (well, actually twice the number of edges). Similarly, $\left<1|A^n|1\right>$ is the number of paths of length $n$, where a path is a sequence of vertices with consecutive vertices connected, repetitions allowed in the case of loops. Call this $P_n$.

Since the graph is connected, its adjacency matrix is irreducible and by the Perron-Frobenius theorem the first eigenvalue is simple and the eigenvector $\left| v \right>$ has positive components. Therefore, $\left< v | 1 \right> > 0$, allowing use of the power iteration method. As $n \to \infty$, $A^n\left|1\right>$ approaches the first eigenvector of $A$ (aside from normalization). So, $$ \lim_{n \to \infty} \frac{P_{n+1}}{P_n} = \lim_{n \to \infty} \frac{P_{2n+1}}{P_{2n}} = \lim_{n \to \infty} \frac{\left<1|A^n A A^n|1\right>}{\left<1|A^n A^n|1\right>} = \lambda_{\textrm{max}}. $$ The largest eigenvalue then tells how the number of paths of length $n$ grows, as $n$ grows (keeping in mind that I used a nonstandard definition for "path"). Furthermore, the limit written above approaches $\lambda_\textrm{max}$ from below.

Theorem 4 of Yu, Lu, Tian (2004) is equivalent to $\lambda_\textrm{max} \ge \sqrt{P_4 / P_2}$, but is expressed in terms of the degrees and 2-degrees of the vertices.