Graph model spectrum

[mblohr]

What does the spectrum of an adjacency matrix tell us about a graph model? Or, specifically, an SBM or it's more general case, a random dot product graph model?

[maxcollard]

From my understanding there isn't really an "adjacency matrix" for a graph model (i.e. a collection of graph-valued random variables); you obtain an adjacency matrix from a graph, which is one realization of one graph-valued RV. Perhaps you mean the "edge probability matrix" or whatever we're calling it for a graph RV, i.e. the matrix (Pij) where Pij = Pr{i ~ j} (The probability that nodes i and j are connected for a realization of the RV.) The spectral properties of that matrix would be kind of interesting, actually.

I'm not sure about the spectrum of adjacency matrices of graphs; however, there are lots of interesting properties of the graph Laplacian matrix [1], which is very closely related to adjacency; for example, the multiplicity of the zero eigenvalue tells you how many connected components the graph has. There are lots of other interesting theorems in spectral graph theory, though some of them are of theoretical more than practical value.

[1] http://en.wikipedia.org/wiki/Laplacian_matrix

[mblohr]

Here's an interesting article on graph spectral compressive sensing that also describes the link between adjacency and Laplacian matrices: http://www.ece.mcgill.ca/~mrabba1/pubs/2011/gscs_icassp2012.pdf