Are there implementations of algorithms for community detection in graphs?

Question

I am looking for implementations of community detection algorithms, such as the Girvan-Newman algorithm (2002). I have visited the websites of several researchers in this field (Newman, Santo, etc.) but was unable to find any code. I imagine someone out there published implementations of these algorithms (maybe even a toolkit?), but I can't seem to find it.

Solution 1

Community detection algorithms are sometimes part of a library (such as JUNG for java) or a tool (see Gephi). When authors publish a new method, they do sometimes make their code available. For example, the Louvain and Infomap methods.

Side note: Girvan-Newman algorithm is sometimes still used, but it has mostly been replaced by faster and more accurate methods. For a good overview of the topic, I recommend Community detection algorithms: a comparative analysis or the longer Community detection in graphs (103 pages).

Solution 2

You should have a look at the igraph library:

• 7 community detection algorithms (including those mentionned above):
  • Edgebetweenness (Girvan-Newman link centrality-based approach),
  • Walktrap (Pons-Latapy random walk-based approach),
  • Leading Eigenvectors (Newman's spectral approach),
  • Fast Greedy (Clauset et. al modularity optimization),
  • Label Propagation (Raghavan et. al),
  • Louvain (Blondel et. al, modularity optimization),
  • Spinglass (Reichardt-Bornholdt, modularity optimization),
  • InfoMap (Rosvall-Bergstrom, compression-based approach).
• Other related functions: process modularity, deal with hierarchical structures, etc.
• Available in R, C and Python
• Open source

To my opinion, the most complete tool for community detection. For more details, also check: What are the differences between community detection algorithms in igraph?

Solution 3

You can try the SNAP library (Stanford Network Analysis Platform, http://snap.stanford.edu/), which includes Modularity, Girvan-Newman and Clauset-Newman-Moore algorithms. It's written in C++, and is under the BSD licence. As a number of papers have used it (see, http://snap.stanford.edu/papers.html), it should be good.

Solution 4

We have recently implemented our algorithm, which is based on Constant Potts Model, fast Louvain optimization, and reliable map equation of InfoMap for weighted and signed networks. Here is the open source java project + an executable jar.

View more solutions

Comments

[glerYbo]

See: matlab-networks-toolbox

[Szabolcs]

It's also available in Mathematica now: github.com/szhorvat/IGraphM All community detection functions are covered.

[pinkdawn]

this helps, many thanks! but still one small question, why your partion output is the sorted index? The expected will be a 2d array, like [[1,2,3],[4,8]] which indicates 1,2,3 is a community

[Esmailian]

We used "node_id group_id" instead of "group_id node_id1,...", this is an easier representation for automated processing