Re: [igraph] community detection analysis using python

[Tamas Nepusz]

Dear Simone,

> I was wondering if the analysis detection is also implemented in the python
> igraph version because from the documentation it looks like it doesn't.
Yes, it's implemented, but it might be a little bit flaky. The
following methods of the Graph object apply to you:

Graph.community_edge_betweenness() - Girvan-Newman hierarchical method
Graph.community_fastgreedy() - Clauset-Newman-Moore hierarchical
method (a.k.a. fast greedy modularity optimization)
Graph.community_leading_eigenvector() - Newman's leading eigenvector method

The C core of igraph also features some other methods (like the
walktrap community detection or the spinglass clustering of Reichardt
& Bornholdt), but these don't have a Python interface (yet). The
reason why they are not included in the online documentation is that I
forgot to update it :) So thanks for pointing that out, the Python
documentation will soon be regenerated and updated!

A small example:

>> g=Graph.GRG(100, 0.2)
>> cl=g.community_fastgreedy()
>> print cl.membership
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1,
2, 2, 3, 1, 1, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 3, 2, 2, 3, 2, 3,
2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 3, 2, 3, 2, 2]

One last note: the leading eigenvector and the edge betweenness
methods are a bit slower than the fast greedy optimization. This is
because the VertexDendrogram objects returned by these methods
calculate the modularity of the resulting partitions at all levels of
the dendrogram in order to select the best split that is returned
afterwards by the membership attribute of the VertexDendrogram object.
The modularity calculation can be speeded up a lot, but I did not have
time to do that yet. This problem does not arise with the
Clauset-Newman-Moore method, because that one calculates the
modularities on the fly. If you want to use the edge betweenness
method or the leading eigenvector method, a workaround for this
problem is to call their low-level equivalents in the GraphBase class,
this will not calculate the modularities. Example:

>> g=Graph.GRG(100, 0.2)
>> merges=GraphBase.community_edge_betweenness(g)

The result is the same merge matrix that's returned by the C interface
(see the documentation of the C interface about how to interpret
that).

Best regards,
-- 
Tamas