3 ms·

Fourier & Friends are excellent analytical tools for the nature of patterns, regardless of where they occur! In EE-land we think too much about real and complex

by qppo 6y ago

Fourier & Friends are excellent analytical tools for the nature of patterns, regardless of where they occur! In EE-land we think too much about real and complex numbers, where Fourier analysis is more concrete. But spectral graph theory makes a lot of sense when you think of Fourier analysis as a way of decomposing patterns into their constituent parts, it just looks a bit funny when those patterns aren't numbers.

pmiller2 6y ago
Indeed. By using tools of linear algebra on the adjacency matrices of a graph, you can tell a lot about the structure of the graph. For instance, if A is the adjacency matrix of a graph G, with n vertices (we say 'vertices' in the math department almost exclusively -- rarely do we say 'nodes'), and k edges, denoting the trace of A by Tr(A), we can find the number of triangles in A by computing Tr(A^3)/6. We can also tell if G is connected by computing A^n. [0] OTOH, the spectrum doesn't tell you nearly everything you'd want to know about a graph. There are many examples of non-isomorphic graphs that are nonetheless cospectral. For instance, one of my professors from grad school wrote a landmark paper in spectral graph theory in 1973, showing that almost all trees are cospectral. [1] --- [0]: Of course, you'd probably never actually do this, because it's horribly inefficient, but here's how it goes. First, you prove easily by induction that A^c_{i,j} is the number of paths of length c starting at vertex i and ending at vertex j. With that in mind, we see that if there is a row of all nonzero numbers in any matrix A^c for c <= n, then G is connected. With a little more work, you can even extract all the connected components of G, by looking at submatrices of A^c. [1]: Unsurprisingly, the paper is titled "Almost all trees are cospectral". See: https://www.semanticscholar.org/paper/Almost-all-trees-are-cospectral-Schwenk/dc8911f3ebd968a107cdd04379245263994c0e86#paper-header https://www.semanticscholar.org/paper/Almost-all-trees-are-c...

by qppo 6y ago

pmiller2 6y ago

Indeed. By using tools of linear algebra on the adjacency matrices of a graph, you can tell a lot about the structure of the graph. For instance, if A is the adjacency matrix of a graph G, with n vertices (we say 'vertices' in the math department almost exclusively -- rarely do we say 'nodes'), and k edges, denoting the trace of A by Tr(A), we can find the number of triangles in A by computing Tr(A^3)/6. We can also tell if G is connected by computing A^n. [0] OTOH, the spectrum doesn't tell you nearly everything you'd want to know about a graph. There are many examples of non-isomorphic graphs that are nonetheless cospectral. For instance, one of my professors from grad school wrote a landmark paper in spectral graph theory in 1973, showing that almost all trees are cospectral. [1] --- [0]: Of course, you'd probably never actually do this, because it's horribly inefficient, but here's how it goes. First, you prove easily by induction that A^c_{i,j} is the number of paths of length c starting at vertex i and ending at vertex j. With that in mind, we see that if there is a row of all nonzero numbers in any matrix A^c for c <= n, then G is connected. With a little more work, you can even extract all the connected components of G, by looking at submatrices of A^c. [1]: Unsurprisingly, the paper is titled "Almost all trees are cospectral". See: https://www.semanticscholar.org/paper/Almost-all-trees-are-cospectral-Schwenk/dc8911f3ebd968a107cdd04379245263994c0e86#paper-header https://www.semanticscholar.org/paper/Almost-all-trees-are-c...