Based on Launchpad traffic and mailing list responses, Gabor and Tamas will soon be releasing igraph 0.6. In celebration, I'll be publishing a number of helpful lists and tables I've put together to organize information about igraph.
In this post, we'll cover the community detection algorithms (i.e., clustering, partitioning, segmenting) available in 0.6 and their characteristics, such as their worst-case runtime performance and whether they support directed or weighted edges. Much of the information below is gleaned from the igraph C documentation, source algorithm publications, and three years of tracking the 0.6 trunk.
Optimal Modularity — Modularity is more of a framework than just a simple function over a graph. The amount of work based on this idea, implicitly or explicitly, is staggering given the short six years since. That said, modularity is just a framework, and, like all frameworks, has its shortcomings. The performance of modularity maximization in practical contexts behaves poorly in real networks, and, depending on |V| and |E|, we might not see "smaller" clusters. Details: New to 0.6, undirected only, unweighted only, handles multiple components, runtime B^(|V|^2).
Edge-Betweenness — Community structure in social and biological networks (Girvan and Newman). Supports directed edges, weighted edges, handles multiple components, runtime |V||E|^2.
Leading Eigenvector — Finding community structure in networks using the eigenvectors of matrices (Newman, 2006). Undirected only, unweighted only, handles multiple components, runtime c|V|^2 + |E|.
Fast-Greedy — Finding community structure in very large networks (Clauset, Newman, Moore). Undirected only, supports weighted edges, handles multiple components, runtime |V||E| log |V|.
Multi-Level — Fast unfolding of communities in large networks (Blondel, Guillaume, Lambiotte, Lefebvre). New to 0.6, undirected only, supports weighted edges, handles multiple components, "linear" runtime when |V| ≈ |E|.
Walktrap — Computing communities in large networks using random walks (Pons, Latapy). Undirected only, supports weighted edges, does not handle multiple components, runtime |E||V|^2.
Label Propagation — Near linear time algorithm to detect community structures in large-scale networks (Raghavan, Albert, Kumara, 2007). New to 0.6, undirected only, supports weighted edges, does not handle multiple components, runtime |V| + |E|.
InfoMAP — The map equation (Rosvall, Axelsson, Bergstrom). New to 0.6, supports directed edges, supports weighted edges and nodes, does not handle multiple components, estimated runtime |V|(|V| + |E|).