Optimizing edge sets in networks to produce ground truth communities based on modularity. Issue 2 (1st December 2021)

• Record Type: Journal Article
• Authors: Kosmas, Daniel; Mitchell, John E.; Sharkey, Thomas C.; Szymanski, Boleslaw K.
• Is Part Of: Networks. Volume 80:Issue 2(2022)
• Page Start: 152
• Page End: 177
• Publication Date: 2021-12-01
• Subjects: community detection -- illicit networks -- integer programming -- modularity maximization -- network optimization -- social networks; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22084
• Languages: English
• ISSNs: 0028-3045

Abstract

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.