I'm not a mathematician, but a geographer trying to get a grasp on some network analysis I'm experimenting with. I have a few questions related to spectral graph theory that a mathematician could help me with:
I'm generating random graphs of 50 nodes and density 0.17 that have particular average path length, modularity, etc. Each of these graphs produce spectra (distribution of eigenvalue) resembling this:
From a novice point of view, I am tempted to tell that a semi-circle shape, if weak, is forming between eigenvalues 0.6 and 1.55.
- What would that mean? Is this related to the typical semi-circle seen in random graphs?
- What about the peak at eigenvalue 0.4? Could it be the second eigenvalue, which is often related to algebraic connectivity?
- Are the values close to zero typical of anything?
To broaden the question, how much can one conclude, in terms of graph structure, from looking at the spectrum of a graph (laplacian or otherwise)? This may seem naive, but can one ever use a graph spectra (perhaps averaged over many graphs) as a structural signature?
It is known that the spectrum of random graphs obeys a semicircular law. Since your graphs are random, your observations do not seem surprising. The form of the eigenvalue density function is largely controlled by the number of closed walks in the graph with length $k$, for small values of $k$. This means that plots like yours will expose information about these walks, giving you information about average valency, average huber of triangles on a vertex, and so on. In general the spectrum does not determine the graph. For example, the probability that a tree on $n$ vertices is determined by its spectrum goes to zero as $n\to\infty$. It is conjectured that the probability that a random graph is determined by its spectrum goes to 1 as the number of vertices increases.