[igraph] New community detection algorithm for igraph

[Tom Gregorovic]

Hi,
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). Its time complexity is near linear
time and it is faster than fast greedy method, while performing
similar final modularity.

To imagine its performance, I have tried it on one real life social
network (300k vertices, 800k edges) and it finishes within 1 minute
with modularity 0.57.

I have come across two implementation issues:
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.

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.

I think that it can be even more improved with better knowledge of igraph and C.

I have one wish, if you could add it also into R-interface and build
an igraph binary release for R win platfrom.

Regards,
Tom Gregorovic

multilevel.c
Description: Text Data