I use spectral graph algorithms for finding community structures, specifically the Leading Eigenvector Method (http://arxiv.org/abs/physics/0605087).
I try analyzing the performance of these algorithms on several graphs generated according to the following methods: Watts-Strogatz, Erdos-Renyl, Stochastic Block Model.
Currently i see some major differences which i can't explain:
- Watts-Strogatz uses less cache memory and more RAM memory regardless of data edge density.
- Erdos-Renyl and Stochastic Block Model use more cache memory and less RAM memory regardless of data edge density.
The algorithm uses the Power method or Lanczos method to calculate the leading eigenvector, and this is affected by the matrix properties, which are related to the graph topography.
I'd appreciate any intuitive analysis and ideas for performance differences.