MATLAB function to partition very large graphs very fast. This function implements a graph partitioning algorithm based on spectral factorization. This algorithm is described in the following technical report:



Joã o Hespanha. An efficient MATLAB Algorithm for Graph Partitioning. Technical Report, University of California, Oct. 2004. Available at http://www.ece.ucsb.edu/~hespanha/techrep.html.



This algorithm was extensively used in this paper:



C. Lim, S. Bohacek, J. Hespanha, K. Obraczka. Hierarchical Max-Flow Routing. In Proc. of the IEEE GLOBECOM, Nov. 2005.