Just had a great visit in KTH University in Sweden. I learned there on a very interesting work about a new algorithm for graph partitioning from Fatemeh Rahimian who won the best paper award at SASO 2013. The paper uses a simulated annealing based local search to improve the partitioning.
I got the following clarification from Fatemeh:
Please find attached the two papers that we have, one is for edge-cut partitioning (JabeJa) and the other is for vertex-cut partitioning (JabeJa-vc), which is inspired by the first algorithm, as its name suggest.
Our algorithm, JabeJa, can be executed with different data distribution models: (i) in a completely distributed environment (like a p2p network, where each peer is actually a graph node), we call this model one-host-one node model; or (ii) in an environment where a machine can host a part of the graph, we call this model the one-host-multiple-nodes.
The implementation of JabeJa on GraphChi consists of the following files:
1. JabeJa.java: the main algorithm of JabeJa.
2. JabeJaWeighted.java: this is JabeJa for weighted graphs.
3. MessageRelay.java: this is the file that implements the "mail" API, i.e., "send" and "get".
4. PartitionAnalysis.java: this file writes the final partitions into different output files.
We are working on adding this code contribution to GraphChi Java code, in the meantime anyone who is interested in welcome to email Fatemeh directly.
Another interesting fact is that a new Data Intensive Computing course at KTH is teaching about GraphLab, among other systems. The slides are available for everyone on the web.