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]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

  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 their blog: Bommarito Consulting » r.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.



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.

Search R-bloggers

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)