8

I am interested in running Newman's modularity clustering algorithm on a large graph. If you can point me to a library (or R package, etc) that implements it I would be most grateful.

Slow loris
  • 1,045
  • 6
  • 26
laramichaels
  • 1,119
  • 3
  • 12
  • 12
  • sorry for the graphical-techniques tag, but my brand new account doesn't let me tag with 'graph' and 'partitioning' as I intended to. – laramichaels Aug 19 '10 at 16:10

2 Answers2

6

The igraph library implements some algorithms for community structure based on Newman's optimization of modularity. You can consult the reference manual for details and citations.

ars
  • 12,160
  • 1
  • 36
  • 54
6

Use the igraph package for R: http://igraph.sourceforge.net/doc/R/fastgreedy.community.html this implements a fast algorithm for community finding using the newman-girvan modularity maximization method.

your code will look like this:

library(igraph)
# read graph from csv file
G<-read.graph("unipartite_edgelist.txt", format="ncol")
fgreedy<-fastgreedy.community(G,merges=TRUE, modularity=TRUE)
memberships <-community.to.membership(G, fgreedy$merges, steps=which.max(fgreedy$modularity)-1)
print(paste('Number of detected communities=',length(memberships$csize)))
    # Community sizes:
    print(memberships$csize)
# modularity:
max(fgreedy$modularity)
Roja
  • 61
  • 1
  • 1