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:

  1. Watts-Strogatz uses less cache memory and more RAM memory regardless of data edge density.
  2. 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.

  • $\begingroup$ I don't know about the effect on memory usage, but the WS and ER models are not supposed to produce graphs possessing a community structure. So why use them to test community detection methods? Why not a model such as LFR (arxiv.org/abs/0805.4770) instead? $\endgroup$ – Vincent Labatut Jan 7 '15 at 21:18
  • $\begingroup$ The datasets are currently given to me, and not chosen by me. I'm trying to understand how the algorithms themselves work in means of memory consumption, and performance. $\endgroup$ – user3370773 Jan 8 '15 at 7:18
  • $\begingroup$ When people use community detection methods, it's generally because they suppose there is a community structure in the data they're treating (and they want to identify it). Are you doing the opposite? I mean: are you studying the behavior of these algorithms specifically on community-less data? If not, then I'm just questionning the relevance of your test data. $\endgroup$ – Vincent Labatut Jan 8 '15 at 13:09
  • $\begingroup$ I'm assuming the test data includes various types of graph topologies. Some with stronger/weaker distinct communities, sparseness, etc. My main goal is to try and understand how these different topologies affect the runtime, memory consumption, space consumption of different algorithms. Currently i'm trying to figure out these affects on the Leading Eigenvector Method. I disagree that the graph models presented are community-less, both Watts-Strogatz and Stochastic Block Model show distinct communities. $\endgroup$ – user3370773 Jan 8 '15 at 14:09
  • $\begingroup$ The ER graphs do not have a community structure. For WS, all I can say is the model is not designed to produce a community structure (just mimic the small world effect), so it does not allow to control it. I didn't say BM are community-less: they are, by construction. $\endgroup$ – Vincent Labatut Jan 8 '15 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.