Re: [igraph] Hierarchical community detection for large, dense, directed, weighted graphs

[Tamás Nepusz]

> Does anybody have any tips on how to calculate any kind of hierarchical 
> community structure on a large, dense, directed, weighted graph in a 
> computationally sensible fashion? The graph in question is 4000 nodes and 
> 300,000 links and getting bigger, and edge.betweenness takes a lot more than 
> I can wait for.
I see two principal issues here:

- directedness. How would you define community structure on a directed network? 
This is something for which the research community does not seem to have a 
consensus on yet.

- density. You did not mention how dense your graph is, but since your graph is 
also weighted, you could probably make use of the weights and throw away a 
large fraction of lightweight edges without affecting the principal structure 
of the graph. My standard method in such situations is pretty arbitrary but 
seemed to work well so far. Basically, I find the median weight in the whole 
graph, then I remap the weights using a sigmoid curve such that the median is 
mapped to a weight of 0.5. The steepness of the sigmoid curve requires some 
experimentation -- use your common sense there to avoid throwing away too much 
or too little. When your graph is sufficiently sparse, you can run a weighted 
community detection algorithm on it. If the algorithm is hierarchical, you are 
pretty much done. If not, you can extract the subgraphs of every single 
community and repeat the whole reweighting trick. This will give you a 
recursive decomposition of the communities into subcommunities.

Cheers,
Tamas