# Post-Processing Partitions to Identify Domains of Modularity Optimization
## 2 The CHAMP Algorithm (Convex Hull of Admissible Modularity Partitions)  
Consider a set of \(\Sigma>0\) unique network partitions encoded by the node community assignments \(\{c_{i\sigma}\}\) with \(\sigma\in\{1,\ldots,\Sigma\}\). By construction, \(\delta(c_{i\sigma},c_{i\sigma})=1\) if nodes \(i\) and \(j\) are in the same community in partition \(\sigma\) (i.e., \(c_{i\sigma}=c_{i\sigma}\)), and \(0\) otherwise. Let \(Q_{\sigma}(\gamma)\) denote the value of Equation (1) for given \(\gamma\) under partition \(\sigma\). Ignoring the constant multiplicative factor in front of the summation (alternatively, absorbing that factor into the normalization of \(A_{ij}\) and \(P_{ij}\)), Equation (1) can be written as  
\[Q_{\sigma}(\gamma) = \sum_{i,j}\left(A_{ij}-\gamma P_{ij}\right)\delta(c_{i\sigma},c_{ j\sigma}) \tag{2}\] \[= \sum_{i,j}A_{ij}\delta(c_{i\sigma},c_{j\sigma})-\gamma\sum_{i,j} P_{ij}\delta(c_{i\sigma},c_{j\sigma})\] \[= \hat{A}_{\sigma}-\gamma\hat{P}_{\sigma}\]  
where the quantities \(\hat{A}_{\sigma}\) and \(\hat{P}_{\sigma}\) are the respective within-community sums over \(A_{ij}\) and \(P_{ij}\) for partition \(\sigma\). Importantly, \(\hat{A}_{\sigma}\) and \(\hat{P}_{\sigma}\) are scalars that depend only on the network data (i.e., \(A\)), null model (i.e., \(P\)), and partition \(\sigma\). Thus, for a given partition \(\sigma\), Equation (2) is a linear function of \(\gamma\), which can be visualized as a line in the \((\gamma,Q)\) plane. (See Figure 1B in Section 3.1 for an illustration of lines \(\{Q_{\sigma}(\gamma)\}\) for several partitions of the 2000 NCAA Division I-A college football network [37; 38].) We now compare the partitions' modularity lines \(\{Q_{\sigma}(\gamma)\}\), seeking to identify the optimal partitions that yield the largest modularity values across the \(\gamma\) values--that is, the upper-envelope boundary \(\{Q_{\sigma}(\gamma)\}\) for the set. We will additionally obtain \(\gamma\)-domains over which a given partition is optimal (discarding partitions that are never optimal). Given a finite set of partitions \(\{\sigma\}\), the coefficients \(\hat{A}_{\sigma}\) and \(\hat{P}_{\sigma}\) can be computed individually, independent of how those partitions were obtained. Therefore, a given value of \(\gamma\) admits an optimal partition \(\sigma^{*}\) corresponding to the maximum \(Q_{\sigma^{*}}(\gamma)\geq Q_{\sigma}(\gamma)\) from the given set of partitions \(\{\sigma\}\). At most values of \(\gamma\), only a single partition provides the maximum (i.e., \"dominant\") modularity. When two partitions \(\sigma\) and \(\sigma^{\prime}\) correspond to identical modularity values [i.e., \(Q_{\sigma}(\gamma)=Q_{\sigma^{\prime}}(\gamma)\)], it is typically because this is the unique intersection of the two corresponding lines. (It is possible to have the case where two different partitions have identical \(\hat{A}_{\sigma}\) and \(\hat{P}_{\sigma}\) coefficients, and thus have equal \(Q_{\sigma}(\gamma)\) for all \(\gamma\); but in practice we have not observed this situation in our examples. We hereafter ignore this possibility; but if it were to occur in practice, it merely indicates two partitions of equal merit, in the sense of modularity, across all scales.) For a pair of partitions \(\sigma\) and \(\sigma^{\prime}\), the intersection point \((\gamma_{\sigma\sigma^{\prime}},Q_{\sigma\sigma^{\prime}})\) indicates the resolution \(\gamma_{\sigma\sigma^{\prime}}\) at which one partition becomes more (less) optimal over the other with increasing (decreasing) \(\gamma\). That is, one partition dominates when \(\gamma<\gamma_{\sigma\sigma^{\prime}}\), while the other dominates when \(\gamma>\gamma_{\sigma\sigma^{\prime}}\). It immediately follows that the \(\gamma\)-domain of optimality for a partition must be simply connected. (We note that in higher dimensions, such as for signed or multilayer networks, the same linearity requires that domains of optimality must be convex [16].)