You can look into random walks. Short random walks have proven to reliably find clusters with low conductance (i.e. many edges inside, few edges outside). (look here for a start: http://smallstats.blogspot.de/2014/04/from-random-walks-to-personalized.html)

I'm not sure if it works for you or not:

If you have some criteria on which you could consider your graph a set of multi-dimentional objects, then you can use the clustering algorithms to devide the graph to several clusers.

K-means Algorithm then can be used to devide to k subgraphs if you want.

Other clustering techniques can also be used to divide it to several sub-graphs based on the density of the points (not distance), like DBScan.

These algorithms work for single (separated) objects of course. If you want to consider the relationships (edges) between the nodes, then you may utilize some of the above-mentioned algorithms.

I think it can be useful: http://micans.org/mcl/index.html

Also we implemented several hierarchical graph partitioning algorithms in our independent solver  an look for application data - may be we can cooperate:)

Use the concept of least community; see the following paper

Jiang B. and Ma D. (2015), Defining least community as a homogeneous group in complex networks, Physica A: Statistical Mechanics and its Applications, 428, 154-160, Preprint: http://arxiv.org/ftp/arxiv/papers/1502/1502.00284.pdf

https://github.com/digmaa/HeadTailCommunityDetection

if you are looking forward for distributed graph partitioning, the following paper may help:

A Scalable Distributed Graph Partitioner  http://www.vldb.org/pvldb/vol8/p1478-margo.pdf 

Streaming graph partitioning for large distributed graphs  http://www.cs.berkeley.edu/~isabelle/papers/kdd325-stanton.pdf