Authored by a team from Karlsruhe Institute of Technology, the paper “Parallel graph partitioning for complex networks” presents a parallelized and adapting label propagation technique for partitioning graphs:
The graph partitioning problem is NP-complete ,  and there is no approximation algorithm with a constant ratio factor for general graphs . Hence, heuristic algorithms are used in practice.
A successful heuristic for partitioning large graphs is the multilevel graph partitioning (MGP) approach depicted in Figure 1, where the graph is recursively contracted to achieve smaller graphs which should reflect the same basic structure as the input graph.
Original title and link: Paper: Parallel Graph Partitioning for Complex Networks ( ©myNoSQL)