[igraph] "reasonable" size graphs for community detection

[Ross Gayler]

Hi,

I may have to do some social network analysis (with no background to
speak of in SNA) and I am currently looking for potential tools to
use.  I have some modest familiarity with R, so am looking to see
whether igraph might be suitable.  At this stage I have no details on
the data, so I am forced to ask correspondingly vague questions.

I want to find communities in a graph of ~1M vertices and will be
running the software on a desktop PC with 16GB RAM and running 64-bit
linux.  Is it reasonable to expect I could perform that kind of
analysis on that kind of hardware?  What order of magnitude run-time
should I expect (seconds, hours, days, weeks)?

The above case of one big graph is probably the worst case scenario.
I suspect that the edge density is rather low and that the 1M vertices
can probably be partitioned into thousands of totally disjoint
subgraphs (which may consitute a reasonable definition of communities
- but I want to allow for the possibility that there may be
communities within large, but loosely connected subgraphs).  Would
that partitioning have a large impact on the runtime of community
detection?

Thanks for any assistance you can offer.

Ross