Re: [igraph] community detection algorithms

[Tamas Nepusz]

Hi Tony,

> Walktrap and fastgreedy give the same membership results every time I run 
> the algorithms. However, label.propagation.community it gives slightly 
> different groupings each time. I have tried setting initial to a set vector 
> (either all 0 or 0:(length(V(g)$name)-1)) and fixed to a vector of all 
> FALSE values in case the algorithm results vary because of random starting 
> values. However, this has no effect.
Unfortunately the label propagation algorithm is inherently unstable;
even when the starting position is completely specified, there are
internal random decisions within the algorithm (e.g., the order in which
the nodes are visited during a single pass of the algorithm, or the
decision a node takes when two different labels appear in its
neighborhood with equal frequency). These random decisions are necessary
to avoid oscillations in the algorithm when it encounters bipartite or
near-bipartite structures within a graph. Section III B in the original
Phys Rev E paper of Raghavan et al (http://arxiv.org/abs/0709.2938)
deals with the problem of aggregating different results into one
consistent solution, but this is just one possible way of dealing with
the problem and it is not implemented in igraph. There are also some
modifications to the original algorithm that try to reduce the
instability of the algorithm, but these are not (yet) implemented in
igraph:

http://arxiv.org/pdf/0910.1154

If you are looking for one single consistent solution with the existing
tools provided by igraph, try running the label propagation algorithm
many times (say, 1000 times) and select a solution based on some
internal quality measure; for instance, the modularity metric (this can
readily be calculated by igraph).

> Any comments would be most welcome; also any other suggestions on how to 
> extract related clusters from my graph structure.
Tom Gregorovic has sent a patch earlier to this mailing list which
implements a fast hierarchical community detection algorithm by Blondel
et al [1]. I'm in the process of integrating this algorithm to igraph
and it will be available soon (maybe next week) in one of the igraph
nightly builds. Also, a recent review paper of Fortunato et al gives a
fairly detailed overview of different community detection approaches on
graphs.

[1] http://www.iop.org/EJ/article/1742-5468/2008/10/P10008/jstat8_10_p10008.html
[2] http://arxiv.org/pdf/0906.0612

-- 
Tamas