igraph-help
[Top][All Lists]

## Re: [igraph] community detection algorithms

 From: Larson, TR Subject: Re: [igraph] community detection algorithms Date: Wed, 28 Oct 2009 17:32:41 +0000 User-agent: Thunderbird 2.0.0.23 (Windows/20090812)

```Dear Tamas,
```
Thanks for your excellent advice and the references! I will await eagerly to try Blondel's algorithm in R.
```
```
For now, I will try multiple runs of the label propagation algorithm (10000 with my data set only takes a few s), and choose a solution based on the modularity score. Which do you think would be the most appropriate solution - the highest modularity score or the most frequent one? I would think the latter should, by definition, be the most "stable"?
```
thanks
Tony

Tamas Nepusz wrote:
```
```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

```
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

```
```

```