patternMinor
Intuition behind eigenvalues of an adjacency matrix
Viewed 0 times
eigenvaluesbehindadjacencymatrixintuition
Problem
I am currently working to understand the use of the Cheeger bound and of Cheeger's inequality, and their use for spectral partitioning, conductance, expansion, etc, but I still struggle to have a start of an intuition regarding the second eigenvalue of the adjacency matrix.
Usually, in graph theory, most of the concepts we come across of are quite simple to intuit, but in this case, I can't even come up with what kind of graphs would have a second eigenvalue being very low, or very high.
I've been reading similar questions asked here and there on the SE network, but they usually refer to eigenvalues in different fields (multivariate analysis, Euclidian distance matrices, correlation matrices ...).
But nothing about spectral partitioning and graph theory.
Can someone try and share his intuition/experience of this second eigenvalue in the case of graphs and adjacency matrices?
Usually, in graph theory, most of the concepts we come across of are quite simple to intuit, but in this case, I can't even come up with what kind of graphs would have a second eigenvalue being very low, or very high.
I've been reading similar questions asked here and there on the SE network, but they usually refer to eigenvalues in different fields (multivariate analysis, Euclidian distance matrices, correlation matrices ...).
But nothing about spectral partitioning and graph theory.
Can someone try and share his intuition/experience of this second eigenvalue in the case of graphs and adjacency matrices?
Solution
(Disclaimer: This answer is about eigenvalues of graphs in general, not the second eigenvalue in particular. I hope it is helpful nevertheless.)
An interesting way of thinking about the eigenvalues of a graph $G = (V, E)$ is by taking the vector space $\mathbb{R}^n$ where $n = |V|$ and identifying each vector with a function $f\colon V \to \mathbb{R}$ (i.e., a vertex labeling). An eigenvector of the adjacency matrix, then, is an element of $f \in \mathbb{R}^n$ such that there is $\lambda \in \mathbb{R}$ (i.e., an eigenvalue) with $A f = \lambda f$, $A$ being the adjacency matrix of $G$. Note that $A f$ is the vector associated with the map which sends every vertex $v \in V$ to $\sum_{u \in N(v)} f(u)$, $N(v)$ being the set of neighbors (i.e., vertices adjacent to) $u$. Hence, in this setting, the eigenvector property of $f$ corresponds to the property that summing over the function values (under $f$) of the neighbors of a vertex yields the same result as multiplying the function value of the vertex with the constant $\lambda$.
An interesting way of thinking about the eigenvalues of a graph $G = (V, E)$ is by taking the vector space $\mathbb{R}^n$ where $n = |V|$ and identifying each vector with a function $f\colon V \to \mathbb{R}$ (i.e., a vertex labeling). An eigenvector of the adjacency matrix, then, is an element of $f \in \mathbb{R}^n$ such that there is $\lambda \in \mathbb{R}$ (i.e., an eigenvalue) with $A f = \lambda f$, $A$ being the adjacency matrix of $G$. Note that $A f$ is the vector associated with the map which sends every vertex $v \in V$ to $\sum_{u \in N(v)} f(u)$, $N(v)$ being the set of neighbors (i.e., vertices adjacent to) $u$. Hence, in this setting, the eigenvector property of $f$ corresponds to the property that summing over the function values (under $f$) of the neighbors of a vertex yields the same result as multiplying the function value of the vertex with the constant $\lambda$.
Context
StackExchange Computer Science Q#109963, answer score: 7
Revisions (0)
No revisions yet.