The first eigenvalue of a graph - what does it reflect? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:02:31Z http://mathoverflow.net/feeds/question/63589 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect The first eigenvalue of a graph - what does it reflect? Seva 2011-05-01T08:22:07Z 2012-10-15T13:40:33Z <p>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 <code>$\lambda_{\max}$</code> satisfies <code>$$\sqrt{\|d_U\|_2\|d_V\|_2} \le \lambda_{\max} \le \sqrt{\|d_U\|_\infty\|d_V\|_\infty};$$</code> in particular, if the graph is <code>$(r_U,r_V)$</code>-regular, then <code>$\lambda_{\max}=\sqrt{r_Ur_V}$</code>. (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,</p> <blockquote> <p>What properties of a (bipartite) graph can be read from its largest eigenvalue?</p> </blockquote> <hr> <h3>A brief summary and common reply to all those who have answered so far.</h3> <ol> <li><p>Thanks for your interest and care!</p></li> <li><p>To make it very clear: I am interested in the <em>usual</em>, not <em>Laplacian</em> eigenvalues.</p></li> <li><p>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.</p></li> <li><p>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. </p></li> <li><p>I still could not find a reference to the displayed inequality above. (@kimball: Lovasz does not have it.) </p></li> </ol> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/63614#63614 Answer by Nilima Nigam for The first eigenvalue of a graph - what does it reflect? Nilima Nigam 2011-05-01T15:48:05Z 2011-05-01T15:48:05Z <p>I fear my answer may not directly address the question, but I like the question! </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/63617#63617 Answer by ght for The first eigenvalue of a graph - what does it reflect? ght 2011-05-01T16:08:49Z 2011-05-01T18:13:34Z <p>Please find <a href="http://mathoverflow.net/questions/59450/boundaries-of-the-eigenvalues-of-a-symmetric-matrix-or-of-its-lapacian/59556#59556" rel="nofollow">here</a> some relations between the eigenvalues of the Laplacian and properties of the graph. You can also take a look at Fan Chung's book <em>"Spectral Graph Theory"</em> where many properties are discussed and the first four chapters are available online <a href="http://www.math.ucsd.edu/~fan/research/revised.html" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/63627#63627 Answer by Chris Godsil for The first eigenvalue of a graph - what does it reflect? Chris Godsil 2011-05-01T18:00:48Z 2011-05-01T18:00:48Z <p>(This is just an overlong comment.)</p> <p>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. </p> <p>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 &amp; A \\ A &amp; 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.)</p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/63628#63628 Answer by Kimball for The first eigenvalue of a graph - what does it reflect? Kimball 2011-05-01T18:04:36Z 2011-05-01T18:04:36Z <p>Lovasz seems to think the largest eigenvalue is not so interesting (if the graph is connected), but the first gap tells you more.</p> <p><a href="http://www.cs.elte.hu/~lovasz/eigenvals-x.pdf" rel="nofollow">www.cs.elte.hu/~lovasz/eigenvals-x.pdf</a></p> <p>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:</p> <p><a href="http://math.uprm.edu/~xryong/SelectedTalks/Summer08-1.pdf" rel="nofollow">math.uprm.edu/~xryong/SelectedTalks/Summer08-1.pdf</a></p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/63695#63695 Answer by Balazs for The first eigenvalue of a graph - what does it reflect? Balazs 2011-05-02T12:10:59Z 2011-05-02T12:10:59Z <p>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 <a href="http://arxiv.org/abs/0705.4503" rel="nofollow">this paper</a> 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. </p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/63702#63702 Answer by ARupinski for The first eigenvalue of a graph - what does it reflect? ARupinski 2011-05-02T14:20:37Z 2011-05-02T14:20:37Z <p>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).</p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/101864#101864 Answer by Mahmoud El Chamie for The first eigenvalue of a graph - what does it reflect? Mahmoud El Chamie 2012-07-10T16:43:35Z 2012-07-10T16:43:35Z <p>The largest eigenvalue $\Lambda (A)$ of the adjacency matrix $A$ of a general graph satisfies the following inequality:</p> <p>$\max \ ( d_{av},\sqrt{d_{max}} ) \le \Lambda (A) \le d_{max}$ , </p> <p>where $d_{av}$ is the average degree of nodes in the graph and $d_{max}$ is the largest degree. </p> <p>The proof of this inequality is found in the small survey I wrote about the most important spectral properties of a graph <a href="http://dl.dropbox.com/u/28417605/spectral.pdf" rel="nofollow">here</a>. You can also check the references in the report for more detailed properties.</p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect/104852#104852 Answer by Dan Stahlke for The first eigenvalue of a graph - what does it reflect? Dan Stahlke 2012-08-16T15:39:42Z 2012-10-15T13:40:33Z <p>Assume the graph is connected.</p> <p>Let $\left| 1 \right>$ be the vector of all 1's (in Dirac notation), and let $A$ be the adjacency matrix. Then $\left&lt;1|A|1\right>$ is the number of edges of the graph (well, actually twice the number of edges). Similarly, $\left&lt;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$.</p> <p>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&lt; 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&lt;1|A^n A A^n|1\right>}{\left&lt;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.</p> <p>Theorem 4 of <a href="http://www.orsc.edu.cn/~mlu/Yulutian%2804laa%29.pdf" rel="nofollow">Yu, Lu, Tian (2004)</a> 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.</p>