Re: [igraph] Building a graph from a genetic distance matrix and finding community structure

[Tamás Nepusz]

> 1) A (mostly) complete graph with genetic distances between all populations 
> (a small number of the distances are 0) clusters much differently than a 
> graph with a reduced edge set. Does anyone know if techniques exist to 
> identify an optimal cutoff distance value for reducing the number of edges?

I don’t think that there is a generally accepted (standard, out-of-the-box) 
method for that. You can try looking at the distribution of weights; if it 
shows two distinct peaks (one larger peak for small weights and one smaller 
peak for large weights), then the cutoff can be selected halfway between the 
mode of the two peaks. A somewhat more formal method that I sometimes use is to 
calculate the median weight and drop weights smaller than the median minus two 
or three standard deviations. (Using the median instead of the mean should give 
you some protection against the effect of outliers).

> 2) There are a large number of modularity metrics in igraph.
There is only one modularity metric, but there are multiple methods that try to 
optimize modularity.
  
> I have experimented with both the leading.eigenvector.community and the 
> fast.greedy.community and they seem to give fairly similar results. Are these 
> appropriate metrics for my particular problem?

Probably yes. Since your graph is pretty small, I would also try 
optimal.modularity since it is guaranteed to find the partition with the 
largest possible modularity (although it is clearly unsuitable for any graph 
that has more than a handful of vertices). The only catch is that 
optimal.modularity does not support weights in older versions of igraph and I 
don’t remember whether we have released a version that supports weights already 
or whether it is still in the development version. If you have the most recent 
version of igraph and it does not support a weights=… argument for 
optimal.modularity, you could try installing one of the nightly builds from 
http://igraph.org/nightly.

All the best,
T.