Post-Processing Partitions to Identify Domains of Modularity Optimization

Abstract

We introduce the Convex Hull of Admissible Modularity Partitions (CHAMP) algorithm to prune and prioritize different network community structures identified across multiple runs of possibly various computational heuristics. Given a set of partitions, CHAMP identifies the domain of modularity optimization for each partition-i.e., the parameter-space domain where it has the largest modularity relative to the input set-discarding partitions with empty domains to obtain the subset of partitions that are "admissible" candidate community structures that remain potentially optimal over indicated parameter domains. Importantly, CHAMP can be used for multi-dimensional parameter spaces, such as those for multilayer networks where one includes a resolution parameter and interlayer coupling. Using the results from CHAMP, a user can more appropriately select robust community structures by observing the sizes of domains of optimization and the pairwise comparisons between partitions in the admissible subset. We demonstrate the utility of CHAMP with several example networks. In these examples, CHAMP focuses attention onto pruned subsets of admissible partitions that are 20-to-1785 times smaller than the sets of unique partitions obtained by community detection heuristics that were input into CHAMP.

Keywords: community detection; modularity; multilayer networks; networks; resolution parameter.

Figure A1

Visualizations of partitions labeled in white in Figure 6A, with Senators grouped according to their state. The listed AMI is the average over layers of the AMI in each layer (Congress) between the communities and political party affiliations for that Congress. Partitions are labeled “X.Y” with X the number of communities with ≥ 5 nodes and Y the rank of the domain area for that number of communities

Figure A2

Visualizations of partitions labeled in white in Figure 6A, with Senators sorted by their most frequent community label (with the labels sorted by last appearance in time), and within communities by first appearance. The listed AMI is the average over layers of the AMI in each layer (Congress) between the communities and political party affiliations in that Congress.

Figure 1

(A) Modularity Q(γ) given by Equation (1) versus resolution parameter γ for 50, 000 runs (10% of results displayed here) of the Louvain algorithm [42,47] at different γ on the unweighted NCAA Division I-A (2000) college football network [37,38]. Grey triangles indicate the number of communities that include ≥ 5 nodes in each run, while the green step function shows the number in the optimal partition in each domain; (B) Graphical depiction of CHAMP algorithm (see Section 2). Each line indicates Q_σ(γ) given by Equation (2) for a particular partition σ. Both panels show the convex hull of these lines as the dashed green piecewise-linear curve, with the transition values represented by downward triangles.

Figure 2

(A) ForceAtlas2 [52] layout, created with [53], of the unweighted NCAA Division I-A (2000) college football network. Nodes are colored according to the dominant 12-community partition with the widest γ-domain γ ∈ [1.45, 3.89], with node shapes and border indicating their conference labels; (B) Pairwise adjusted mutual information (N = AMI) between all partitions in the admissible subset identified by CHAMP, arranged by their corresponding γ-domains of optimality. Dashed lines indicate the transition values of γ identified by CHAMP.

Figure 3

(A) Modularity Q(γ) given by Equation (1) v. resolution parameter γ for 20, 000 runs (25% of results shown) of Louvain [42,47] on the Human Protein Reactome network [54]. Small, grey triangles indicate the number of communities that include ≥ 5 nodes in each run, while the dark green step function shows the number in the optimal partition in each domain. The dashed green curve is the piecewise-linear modularity function for the optimal partitions, with the transition values marked by blue triangles; (B) Pairwise AMI between all partitions in the admissible subset identified by CHAMP, arranged by their corresponding γ-domains of optimality.

Figure 4

ForceAtlas2 layout [52], created with [53], of the Human Reactome Network (edges downsampled to 50,000), colored according to the partitions with the two widest γ-domains of optimization identified by CHAMP from 20, 000 runs of Louvain.

Figure 5

(A) Modularity Q(γ) v. γ for 100, 000 runs (5% of results shown) of Louvain [42,47] on the Caltech Facebook network [31]. Orange triangles indicate the number of communities that include ≥ 5 nodes in each run, while the red step function shows the number in the optimal partition in each domain. The dashed green curve is the piecewise-linear modularity function for the optimal partitions, with the transition values marked by blue triangles. The condensed layout of communities (created with [53]) here visualizes the optimal partition found for γ ∈ [0.908, 1.09], with each pie-chart corresponding to a community, fractionally colored according to the House membership of the nodes in the community. The AMI between this partition and House labels (including the missing label) is 0.513; (B) Pairwise AMI between all partitions in the admissible subset identified by CHAMP, arranged by their corresponding γ-domains of optimality.

Figure 6

(A) Domains of optimization for the pruned set of partitions, colored by the number of communities within each partition. The set of partitions was generated from 240, 000 runs of GenLouvain [41] on a 600 × 400 uniform grid over [0.3, 2] × [0, 2] in (γ,ω). The largest partitions are labeled “X.Y” with X the number of communities with ≥ 5 nodes and Y the rank of the domain area (that is, in terms of size) for that given number of communities (e.g., “5.2” is the second-largest domain corresponding to 5-community partitions). The partitions of each labeled domain are visualized in Appendix A; (B) Weighted-average AMI of each partition with its neighboring domains’ partitions, weighted by the length of the borders between neighboring domains.

Figure 7

Time-varying community structure for the U.S. Senate from 1789 to 2008 according to the (A,B) 5-community and (C,D) 8-community partitions with widest domains of optimality (see labels 5.1 and 8.1 in Figure 6A); (A,C) The vertical axis indicates individual Senators, sorted by community label and time. The AMI reported here is the average over layers (Congresses) of the AMIs in each layer between the identified communities in that layer and political party labels. (This layer-averaged AMI is shown for all partitions in the convex hull over the originally searched parameter range in Figure 8.) (B,D) The vertical axis indicates the state of a Senator, sorted according to geographic region, and the horizontal axis represents time (two-year Congresses).

Figure 8

The domains of optimality for the time-varying U.S. Senate roll-call similarity network (as in Figure 6), colored by the layer-averaged AMI between the political-party affiliations of Senators and the community labels {c_iσ} for that layer.