# Post-Processing Partitions to Identify Domains of Modularity Optimization
## 2 The CHAMP Algorithm (Convex Hull of Admissible Modularity Partitions)
### MultiLayer Networks and Qhull
For each partition \(\sigma\), we again define the scalar quantities \(\hat{A}_{\sigma}\) and \(\hat{P}_{\sigma}\) to be the within-community sums over the adjacency matrix and null model, respectively, and now include a similar sum over the interlayer connections, \(\hat{\mathcal{C}}_{\sigma}\):  
\[\hat{A}_{\sigma}=\sum_{i,j}A_{ij}\delta(c_{i\sigma},c_{j\sigma})\,,\qquad\hat {P}_{\sigma}=\sum_{i,j}P_{ij}\delta(c_{i\sigma},c_{j\sigma})\,,\qquad\hat{ \mathcal{C}}_{\sigma}=\sum_{i,j}C_{ij}\delta(c_{i\sigma},c_{j\sigma})\,. \tag{6}\]  
In this notation, the multilayer modularity of partition \(\sigma\) becomes simply  
\[Q_{\sigma}(\gamma,\omega)=\hat{A}_{\sigma}-\gamma\hat{P}_{\sigma}+\omega\hat{ \mathcal{C}}_{\sigma}\,. \tag{7}\]  
Thus, the partition \(\sigma\) is represented by the plane \(Q_{\sigma}\) in \((\gamma,\omega,Q)\). Analogous to the single-layer case, each point in the two-dimensional \((\gamma,\omega)\) parameter space admits an optimal \(Q_{\sigma^{*}}\). Given a set of partitions \(\{\sigma\}\), CHAMP calculates the coefficients of the \(Q_{\sigma}(\gamma,\omega)\) planes in Equation (7) and solves a convex hull problem to find the convex intersection of the half-spaces above these partition-representing planes. That is, each partition is represented by a plane dividing \((\gamma,\omega,Q)\) in two, thereby defining a half-space. The intersection of the half-spaces above all of these planes is the convex space of \(Q(\gamma,\omega)\) values greater or equal to all observed quality values, with the boundary specifying the maximum modularity surface of the set. In single-layer networks, we considered ordered \(\gamma\geq 0\) and iteratively identified the next intersection and associated partition for increasing \(\gamma\). In the presence of multiple parameter dimensions here, we instead apply the Qhull implementation [43; 44] of Quickhull [45] to solve the dual convex hull problem. In practice, multiple partitions of the network can be identified in parallel, calculating and saving each set of \(\hat{A}\), \(\hat{P}\), and \(\hat{C}\) coefficients. These coefficients defining the planes are then input into Qhull. CHAMP thereby prunes \(\{\sigma\}\) to the subset admitted to the convex hull and identifies the convex polygonal domain in \((\gamma,\omega)\) where each partition is optimal (relative to \(\{\sigma\}\)). We note that in practice the runtime for finding the pruned subset of admissible partitions and associated domains of optimality is typically insignificant compared to that of identifying the input set of partitions in the first place. In particular, computing the scalar coefficients of the linear subspace of each partition is a direct \(O(M)\) calculation for \(M\) edges in the network. Meanwhile, the subsequent convex hull problem has no explicit dependence on the network size, depending instead on the number of partitions in the input set. While we assume here that there is a single interlayer coupling parameter \(\omega\), we emphasize again that we do not restrict ourselves here to a particular form of the interlayer coupling, which might connect nearest-neighbor layers, all-to-all layers, connect only some nodes in one layer to those in another, and might have multiple different weights along different interlayer edges. Rather, we only require here that there is some selected interlayer coupling tensor \(C\) that is multiplied by \(\omega\). Even more complicated interlayer couplings with multiple parameters (e.g., data that is both multiplex and temporal with the freedom to vary the relative weights between these couplings) can in principle be treated analogous to the above in the appropriate higher-dimensional space.