Summary of community detection algorithms in igraph 0.6

June 17, 2012
By

(This article was first published on Bommarito Consulting » r, and kindly contributed to R-bloggers)

  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).

 

To leave a comment for the author, please follow the link and comment on his blog: Bommarito Consulting » r.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.