Optimizing edge sets in networks to produce ground truth communities based on modularity. Issue 2 (1st December 2021) - Kosmas, Daniel; Mitchell, John E.; Sharkey, Thomas C.; Szymanski, Boleslaw K.
Abstract: 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 one 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 makes the development of heuristics for general networks difficult. We then present results on a selection of social and illicit networks from the literature.