The best way for clustering an adjacency matrix I've had a hard time interpreting resulting clusters of an adjacency matrix. I have 200 relatively big matrices representing subjects that contains partial correlations (z scores) of time series (neural data). The goal is to cluster those 210 matrices and detect any potential undiscovered communities. So I did another partial correlation calculations resulting in 200x200 adjacency matrix. Whenever I run a community detection algorithm (eg Newmann's) it comes up with hardly interpretable communities.
The question is that what kind of statistical tests that will tell if these communities or clusters are significant at all ? and if so, are there systematic ways to work out the interpretation ?
 A: I have done some work in the past on spectral clustering which might be of use here. The basic idea is that one can use the adjacency matrix to form the so called Laplacian matrix:
$L = I-D^{-1/2}AD^{-1/2}$
You can check for yourself that the lowest eigenvalue of the Laplacian is zero. The first nonzero eigenvalue is often called the algebraic connectivity, and the corresponding eignevector will have positive part and negative part corresponding to two partitions $(B_1,B_2)$ of the underlying graph. Roughly speaking, the magnitude of the first nonzero eignevalue is a measure of the strength of the connections between the two partitions. Perhaps you could employ this approach recursively or consider the first few nonzero eignvalues of the Laplacian.The following Wikipedia article about spectral clustering is a good start. 
A: I am looking at the same problem at the moment. From quick review, it seems like Spectral clustering is the most "natural" way to analyze an Adjacency matrix. See this blog post for more details.
A: Alternatively...  Neural data (real or artificial) is often a highly compressed representation of data, which means the data is very random, which means you won't find any correlations. Which you have!!  Congratulations! :)
