# Post-Processing Partitions to Identify Domains of Modularity Optimization
## 1 Introduction
Importantly, in each of these approaches for exploring the parameter space, the optimal partitions associated with each \(\gamma\) value are typically computed independently of those at other \(\gamma\) values [and, again, in the multilayer case, \((\gamma,\omega)\)]. Variation in the structure of these partitions and their corresponding modularity can arise from both adjusting the input parameters and importantly, from the stochasticity of the algorithm itself. Often, for close enough values of \(\gamma\), the variation in modularity of identified partitions is driven more by the stochasticity of the algorithm rather than the difference in the value of \(\gamma\). Because of this independent treatment of the results from different \(\gamma\) values, a large amount of information that might be useful for further assessing the quality of the obtained partitions is typically thrown away. We propose a different approach, which we call CHAMP, that uses the union of all computed partitions to identify the Convex Hull of Admissible Modularity Partitions in the parameter space. CHAMP identifies the domains of optimality across a set of partitions by ignoring the \(\gamma\) that was used to compute each partition, finding instead the full domain in \(\gamma\) for which each partition is optimal relative to the rest of the input partitions (hereafter, we always use the word \"optimal\" in this restricted sense relative to the set of partitions at hand). Visualizing the geometry of this identification process, each partition is represented as a line in \((\gamma,Q)\) for single-layer networks, and as a plane in the \((\gamma,\omega,Q)\) space in the multilayer case with a single interlayer coupling parameter \(\omega\). We find the intersection of the half-spaces above the linear subspaces by computing the convex hull of the dual problem. By identifying the convex hull of the dual problem, we prune that set of partitions to the subset wherein each partition has at least some non-empty domain in the parameter space over which it is has the highest modularity. This pruned subset contains all of the partitions admitted through the dual convex hull calculation. Visually, plotting \(Q\) as a function of the parameters, the pruned subset is that which remains in the upper envelope of \(Q\), so that each partition appears along the boundary of the convex space above the envelope in the domain where it provides the optimal \(Q\) relative to the input set. The partitions removed by CHAMP do not provide optimal \(Q\) for any range of parameters. Meanwhile, the partitions that remain in the pruned set are 'admissible' candidates for the true but unknown upper envelope of \(Q\); that is, each of these 'admissible' partitions corresponds to some non-empty parameter domain of optimality relative to the input set of partitions. We propose an algorithm to find this convex intersection of half-spaces for single-layer networks and demonstrate its ability to greatly reduce the number of partitions under consideration. We also propose an algorithm for mapping out the two-dimensional \((\gamma,\omega)\) domains of optimal modularity for multilayer networks in terms of the dual convex hull problem. The rest of this paper is organized as follows. We first define the CHAMP algorithm in Section 2. We then apply CHAMP to example networks in Section 3, including several, single-layer exampleswith resolution parameter \(\gamma\) and a multilayer network with a \((\gamma,\omega)\) parameter space (Section 3.4, with additional figures in the Appendix). We conclude with a brief Discussion (Section 4).