Blog

Summary of community detection algorithms in igraph 0.6

  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

  In my mind, modularity is  more of a framework than just a simple function over a graph.  I don’t know how Mark feels, but the amount of work based on this idea, implicitly (~87,000) or explicitly (~1000), is staggering given the short six years since.

  That said, modularity is just a framework, and, like all frameworks, has its shortcomings.  If you are going to talk about modularity in a quantitative way, there are two must-read ideas on the topic:

  TL;DR: The plateau of the  modularity surface we care about most behaves poorly in real networks, and, depending on |V| and |E| in absolute and relative terms, we might not see “smaller” clusters.

If you’re still going to calculate the optimal modularity configuration, here are the details:

  • New to version 0.6: TRUE
  • Directed edges: FALSE
  • Weighted edges: FALSE
  • Handles multiple components: TRUE
  • Runtime: B^(|V|^2)

Edge-Betweenness

OK, time to get less verbose.  I’ll stick to the primary reference and igraph characteristics going forward:

Leading Eigenvector

Fast-Greedy

Multi-Level

  • Fast unfolding of communities in large networks
    Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
  • New to version 0.6: TRUE
  • Directed edges: FALSE
  • Weighted edges: TRUE
  • Handles multiple components: TRUE
  • Runtime: “linear” when |V| approx |E|; (a quick glance at the algorithm suggests this would be quadratic for fully-connected graphs)

Walktrap

Label Propagation

InfoMAP

  • The map equation
    M. Rosvall, D. Axelsson, C. T. Bergstrom
  • New to version 0.6: TRUE
  • Directed edges: TRUE
  • Weighted edges: TRUE
  • Weighted nodes: TRUE
  • Handles multiple components: FALSE
  • Runtime: none given; looks worst case like |V|(|V| + |E|) based on quick reading.
  Stay tuned for more on the upcoming igraph release.  Please feel free to comment and let me know which topic you’d like to see covered next – layout/visualization algorithms, spectral coarse graining, or acyclid digraphs (DAGs).

 

Leave a Comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>