To dynamically map nodes for locality and balance, computer implemented methods, systems, and computer readable media, in an embodiment, may compute histograms for nodes in a first partition. Histograms may be computed for nodes in a second partition. The second partition may be selected as a candidate partition for a set of nodes in the first partition based on the histograms for the nodes in the first partition. The first partition may be selected as a candidate partition for a set of nodes in the second partition based on the histograms for the nodes in the second partition. At least a portion of the set of nodes in the first partition may be mapped to the second partition and at least a portion of the set of nodes in the second partition may be mapped to the first partition based on load balancing.