Scalability of Markov Clustering I want to do graph clustering on a large dataset (A graph with 600,000 Nodes and tens of millions of edges). I read about Markov clustering. I saw this algorithm involved the calculation of a stochastic matrix and its powers. Therefore, I was wondering whether it could be used here? Otherwise, what algorithm do you suggest?
 A: You'll want to look into graph analytics software that scales to cluster computers--something running over MPI or Hadoop, is your best bet. The two out there that I've used are GraphLab, which runs over MPI, and Intel's Data Platform Analytics Toolkit, which runs over Hadoop. Once you solve the scaling problem, there are a variety of clustering algorithms you can use. I'd recommend starting with something simple, like k-means. Giraph, which is incorporated into Intel's software, has an implementation of k-means. Example code can be found here.
A: You might want to look at the Chou Liu algorithm. The gRapHD pack in R has this in the minForest function. You might also look at glasso and the huge packages in R if you want to have sparsity constraints and go beyond forests to general graphs. 
These R packages don't scale beyond a single computer but can still handle tens of thousands of nodes, maybe more which you can do on a Amazon EC2 instance with sufficient memory. 
A: The implementation at micans.org/mcl uses sparse matrices, and the process computed by the Markov Cluster (mcl) algorithm lends itself well to keeping matrices sparse. This makes the algorithm very scalable. The implementation has been used to cluster graphs with more than 5 million nodes and over a billion edges. The best thing is to give it a try (without implementing it yourself). Of course, it helps if you have access to good hardware, preferably with multiple CPUs (use the mcl '-t' option to make it run in parallelised mode).
