  We consider two new problems regarding the impact of edge addition or removal
on the modularity of partitions (or community structures) in a network. The
first problem seeks to add edges to enforce that a desired partition is the
partition that maximizes modularity. The second problem seeks to find the
sparsest representation of a network that has the same partition with maximum
modularity as the original network. We present integer programming
formulations, a row generation algorithm, and heuristic algorithms to solve
these problems. Further, we demonstrate a counter-intuitive behavior of
modularity that make the development of heuristics for general networks
difficult. We then present results on a selection of social and illicit
networks from the literature.
