I have an undirected graph G=(V, E) where each vertex represents a segment in a large road network map. Each edge represents a road segment from one place to another place. Therefore, all edges have the same weight. I wish to partition this road network into k different sets clusters.
Motivations: The idea is to divide the edges into k-sets of partition, such that each partition can be replicated into n-number of machines. Each machine will perform the distance approximation algorithm.
Is there any graph partitioning technique, that is easy to understand and implement? The graph I am trying to partition consists of 25000 nodes.