I am new to graph partitioning, but I think the question I am asking should already have a good answer. I just want to partition a huge network (billions of nodes) into a few sub-graphs. so when using MPI, each sub-graph is processed by different processors. I am currently using the adjacency list representation of the graph. what algorithms can do this? Thank you!
Yes you can do this and there are several open source tools available. The tool I use most frequently is parMETIS.
It is a MPI - based parallel library which provides a variety of functions including graph partitioning. How you use this library is entirely dependent on your application. Generally, I prefer feeding the input graph to parMETIS, obtaining the partition and then feed the partitions as an input to my MPI programs, however you could also call the functions from your application for graphs which change in realtime.