[igraph] MCL integration into igraph (was: Community detection with i-graph)

[Tamas Nepusz]

Hi Stijn,

Integrating MCL into igraph has already been on my (admittedly too long)
to-do list for a while and it would indeed be a very welcome addition.
Currently we only have some glue code in our wiki to call the external
MCL executable from igraph:

http://igraph.wikidot.com/community-detection-in-python

Obviously a better solution would be to merge the relevant parts of
mcl's codebase into igraph's source tree and write some conversion
routines that turn an igraph_t into MCL's internal data structures. This
is the approach we have followed with other external algorithms such as
the BLISS and VF2 algorithms and the walktrap community detection
method. Of course this means that the graph temporarily exists in two
copies in the memory, but the advantage is that it is much easier to
merge patches and updates from upstream. Anyway, if you are willing to
start doing this, let me know and I'll be happy to assist.

The current focus of development is the 0.6-main branch on Launchpad:
https://code.launchpad.net/~igraph/igraph/0.6-main. src/walktrap.cpp is
a good point to start; this file contains a wrapper for the walktrap
method. The actual conversion code from igraph_t to walktrap's Graph
data structure is in src/walktrap_graph.cpp (see
Graph::convert_from_igraph). I think something similar is enough for MCL
as a first approximation.

Best regards,
-- 
Tamas


On 04/07/2011 11:54 AM, Stijn van Dongen wrote:
> 
>       Hi Tamas, list members,
> 
> I think it would be nice if, in addition to the algorithms listed below, it
> is possible to use the MCL cluster algorithm from within igraph.
> Do you have suggestions for a prefered way of doing (coding) this?
> Would someone be willing to assist me?
> 
> regards,
> Stijn
> 
> 
> 
> On Thu, Apr 07, 2011 at 11:07:19AM +0200, Tamas Nepusz wrote:
>> Re-sending my previous message as the list server says that it has not
>> been delivered;
>>
>>
>> ==================8<==================8<================================
>>
>> Try these methods of the Graph class first:
>>
>> http://packages.python.org/python-igraph/igraph.Graph-class.html#community_fastgreedy
>> http://packages.python.org/python-igraph/igraph.Graph-class.html#community_walktrap
>> http://packages.python.org/python-igraph/igraph.Graph-class.html#community_spinglass
>>
>> E.g.:
>>
>> from igraph import Graph
>>
>> # generate a random geometric graph
>> g = Graph.GRG(100, 0.2)
>>
>> # find its communities
>> cl = g.community_fastgreedy()
>>
>> # print the membership vector
>> print cl.membership
>>
>> # print the number of communities
>> print len(cl)
>>
>> # print the members of community zero
>> print cl[0]
>>
>> If your graph contains only a couple of hundreds of vertices, you may
>> also try this one:
>>
>> http://packages.python.org/python-igraph/igraph.Graph-class.html#community_edge_betweenness
>>
>> -- 
>> Tamas
>>
>> On 04/06/2011 05:21 PM, Gino Serpa wrote:
>>> The community detection part
>>> Gino
>>>
>>>
>>>> Since my actual graph has 11,000. vertexes I need to play first with
>>>> finding these communities or clusters in fake smaller graphs. I am
>>>> not sure what to do first? which igraph commands to use (in
>>>> python)? Are there any small examples I could study?
>>> Which part are you interested in? The how-to-generate-fake-graphs part
>>> or the how-to-detect-communities part?
>>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>