Re: [igraph] New community detection algorithm for igraph

[Tamas Nepusz]

Dear Tom,

> I have implemented new community detection algorithm from article
> "Fast unfolding of communities in large networks" by Vincent D.
> Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
> (http://arxiv.org/abs/0803.0476).
Thanks, that's great! I'll take a look at your patch and integrate it  
into the trunk during the next few days; you can subscribe to the  
following issue in our bugtracker to keep you updated:

https://bugs.launchpad.net/igraph/+bug/406421

> The first (in igraph_i_multilevel_community_links function) was lack
> of some sorted array or tree structure with log n addition and search
> time complexity. I have solved this by using regular c dynamic array,
> quicksort and merge of same items at the end.
That should be fine; as the array is created once, sorted in-place and  
then destroyed within the same function, I think this is the best  
solution (both in terms of simplicity and performance).

> The second issue was very slow graph simplification - even my naive
> algorithm in igraph_simplify_multiple, which is n log n complex, is
> more than ten times faster. I haven't found where the pitfall is.
There's one key difference: your function destroys the graph and  
creates a new one at the very same memory address, while the original  
igraph_simplify erases the extra edges by calling igraph_delete_edges 
(). I will profile both implementations and try to find out where the  
bottleneck is.

--
Tamas