Are there implementations of algorithms for commun

问题:

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.

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

回答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?

回答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.

回答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.