{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T02:53:28Z","timestamp":1764212008220,"version":"build-2065373602"},"reference-count":59,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2017,8,19]],"date-time":"2017-08-19T00:00:00Z","timestamp":1503100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2014i.e., the parameter-space domain where it has the largest modularity relative to the input set\u2014discarding partitions with empty domains to obtain the subset of partitions that are \u201cadmissible\u201d 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.<\/jats:p>","DOI":"10.3390\/a10030093","type":"journal-article","created":{"date-parts":[[2017,8,21]],"date-time":"2017-08-21T11:10:51Z","timestamp":1503313851000},"page":"93","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":40,"title":["Post-Processing Partitions to Identify Domains of Modularity Optimization"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7159-1990","authenticated-orcid":false,"given":"William","family":"Weir","sequence":"first","affiliation":[{"name":"Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina, Chapel Hill, NC 27599, USA"},{"name":"Curriculum in Bioinformatics and Computational Biology, University of North Carolina, Chapel Hill, NC 27599, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7946-7046","authenticated-orcid":false,"given":"Scott","family":"Emmons","sequence":"additional","affiliation":[{"name":"Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina, Chapel Hill, NC 27599, USA"}]},{"given":"Ryan","family":"Gibson","sequence":"additional","affiliation":[{"name":"Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina, Chapel Hill, NC 27599, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1851-3309","authenticated-orcid":false,"given":"Dane","family":"Taylor","sequence":"additional","affiliation":[{"name":"Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina, Chapel Hill, NC 27599, USA"}]},{"given":"Peter","family":"Mucha","sequence":"additional","affiliation":[{"name":"Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina, Chapel Hill, NC 27599, USA"},{"name":"Curriculum in Bioinformatics and Computational Biology, University of North Carolina, Chapel Hill, NC 27599, USA"}]}],"member":"1968","published-online":{"date-parts":[[2017,8,19]]},"reference":[{"key":"ref_1","first-page":"1082","article-title":"Communities in networks","volume":"56","author":"Porter","year":"2009","journal-title":"Not. AMS"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys. Rep."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","article-title":"Community detection in networks: A user guide","volume":"659","author":"Fortunato","year":"2016","journal-title":"Phys. Rep."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Abbe, E. (arXiv, 2017). Community detection and stochastic block models: Recent developments, arXiv.","DOI":"10.1561\/9781680834772"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Schaub, M.T., Delvenne, J.C., Rosvall, M., and Lambiotte, R. (2017). The many facets of community detection in complex networks. Appl. Netw. Sci., 2.","DOI":"10.1007\/s41109-017-0023-6"},{"key":"ref_6","unstructured":"Shai, S., Stanley, N., Granell, C., Taylor, D., and Mucha, P.J. (arXiv, 2017). Case studies in network community detection, arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"016110","DOI":"10.1103\/PhysRevE.74.016110","article-title":"Statistical mechanics of community detection","volume":"74","author":"Reichardt","year":"2006","journal-title":"Phys. Rev. E"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1073\/pnas.0605965104","article-title":"Resolution limit in community detection","volume":"104","author":"Fortunato","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"053039","DOI":"10.1088\/1367-2630\/10\/5\/053039","article-title":"Analysis of the structure of complex networks at different resolution levels","volume":"10","author":"Arenas","year":"2008","journal-title":"New J. Phys."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"016102","DOI":"10.1063\/1.3560932","article-title":"Mesoscopic analysis of networks: Applications to exploratory analysis and data clustering","volume":"21","author":"Granell","year":"2011","journal-title":"Chaos"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"118703","DOI":"10.1103\/PhysRevLett.100.118703","article-title":"Community Structure in Directed Networks","volume":"100","author":"Leicht","year":"2008","journal-title":"Phys. Rev. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"066102","DOI":"10.1103\/PhysRevE.76.066102","article-title":"Modularity and community detection in bipartite networks","volume":"76","author":"Barber","year":"2007","journal-title":"Phys. Rev. E"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"016114","DOI":"10.1103\/PhysRevE.80.016114","article-title":"Analysis of community structure in networks of correlated data","volume":"80","author":"Gomez","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"036115","DOI":"10.1103\/PhysRevE.80.036115","article-title":"Community detection in networks with positive and negative links","volume":"80","author":"Traag","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1126\/science.1184819","article-title":"Community structure in time-dependent, multiscale, and multiplex networks","volume":"328","author":"Mucha","year":"2010","journal-title":"Science"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","article-title":"On modularity clustering","volume":"20","author":"Brandes","year":"2008","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"046106","DOI":"10.1103\/PhysRevE.81.046106","article-title":"Performance of modularity maximization in practical contexts","volume":"81","author":"Good","year":"2010","journal-title":"Phys. Rev. E"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1093\/comnet\/cnu016","article-title":"Multilayer networks","volume":"2","author":"Arenas","year":"2014","journal-title":"J. Complex Netw."},{"key":"ref_20","first-page":"011027","article-title":"Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems","volume":"5","author":"Lancichinetti","year":"2015","journal-title":"Phys. Rev. X"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1073\/pnas.0706851105","article-title":"Maps of random walks on complex networks reveal community structure","volume":"105","author":"Rosvall","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_22","unstructured":"Han, Q., Xu, K.S., and Airoldi, E.M. (2015, January 6\u201311). Consistent Estimation of Dynamic and Multi-layer Block Models. Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37, Lille, France."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1109\/TNSE.2016.2537545","article-title":"Clustering Network Layers with the Strata Multilayer Stochastic Block Model","volume":"3","author":"Stanley","year":"2016","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"228301","DOI":"10.1103\/PhysRevLett.116.228301","article-title":"Enhanced Detectability of Community Structure in Multilayer Networks through Layer Aggregation","volume":"116","author":"Taylor","year":"2016","journal-title":"Phys. Rev. Lett."},{"key":"ref_25","unstructured":"(2017, August 16). Detecting communities (Pajek and PajekXXL). Available online: http:\/\/mrvar.fdv.uni-lj.si\/pajek\/community\/CommunityDrawExample.htm."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"033119","DOI":"10.1063\/1.3184538","article-title":"Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007\u20132008 credit crisis","volume":"19","author":"Fenn","year":"2009","journal-title":"Chaos"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1493","DOI":"10.1080\/14697688.2012.668288","article-title":"Dynamical clustering of exchange rates","volume":"12","author":"Fenn","year":"2012","journal-title":"Quant. Finance"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/j.physa.2011.06.030","article-title":"Community structure in the United Nations General Assembly","volume":"391","author":"Macon","year":"2012","journal-title":"Phys. A"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2930","DOI":"10.1038\/srep02930","article-title":"Significant Scales in Community Structure","volume":"3","author":"Traag","year":"2013","journal-title":"Sci. Rep."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Lewis, A.C., Jones, N.S., Porter, M.A., and Deane, C.M. (2010). The function of communities in protein interaction networks at multiple scales. BMC Syst. Biol., 4.","DOI":"10.1186\/1752-0509-4-100"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1137\/080734315","article-title":"Comparing Community Structure to Characteristics in Online Collegiate Social Networks","volume":"53","author":"Traud","year":"2011","journal-title":"SIAM Rev."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/j.jmva.2006.11.013","article-title":"Comparing clusterings\u2014An information based distance","volume":"98","year":"2007","journal-title":"J. Multivar. Anal."},{"key":"ref_33","unstructured":"Fred, A.L.N., and Jain, A.K. (2003, January 18\u201320). Robust data clustering. Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Madison, WI, USA."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"013142","DOI":"10.1063\/1.4790830","article-title":"Robust detection of dynamic community structure in networks","volume":"23","author":"Bassett","year":"2013","journal-title":"Chaos"},{"key":"ref_35","first-page":"187","article-title":"An ensemble learning strategy for graph clustering","volume":"588","year":"2012","journal-title":"Contemp. Math."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1038\/srep00336","article-title":"Consensus clustering in complex networks","volume":"2","author":"Lancichinetti","year":"2012","journal-title":"Sci. Rep."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Evans, T.S. (2010). Clique graphs and overlapping communities. J. Stat. Mech. Theory Exp., 2010.","DOI":"10.1088\/1742-5468\/2010\/12\/P12037"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_39","first-page":"041022","article-title":"Mathematical Formulation of Multilayer Networks","volume":"3","author":"Cozzo","year":"2013","journal-title":"Phys. Rev. X"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/15M1009615","article-title":"Community Detection in Temporal Multilayer Networks, with an Application to Correlation Networks","volume":"14","author":"Bazzi","year":"2016","journal-title":"Multiscale Modeling Simul."},{"key":"ref_41","unstructured":"Jeub, L.G.S., Bazzi, M., Jutla, I.S., and Mucha, P.J. (2017, August 16). A generalized Louvain method for community detection implemented in MATLAB. Available online: http:\/\/netwiki.amath.unc.edu\/GenLouvain."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","article-title":"Fast unfolding of communities in large networks","volume":"2008","author":"Blondel","year":"2008","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_43","unstructured":"(2017, August 16). Qhull. Available online: http:\/\/www.qhull.org\/."},{"key":"ref_44","unstructured":"(2017, August 16). Pyhull. Available online: http:\/\/pythonhosted.org\/pyhull\/."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/235815.235821","article-title":"The Quickhull Algorithm for Convex Hulls","volume":"22","author":"Barber","year":"1996","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_46","unstructured":"Weir, W., Gibson, R., and Mucha, P.J. (2017, August 16). CHAMP package: Convex Hull of Admissible Modularity Partitions in Python and MATLAB. Available online: https:\/\/github.com\/wweir827\/CHAMP."},{"key":"ref_47","unstructured":"Traag, V. (2017, August 16). Louvain igraph. Available online: http:\/\/github.com\/vtraag\/louvain-igraph."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Vinh, N.X., Epps, J., and Bailey, J. (2009, January 14\u201318). Information Theoretic Measures for Clusterings Comparison: Is a Correction for Chance Necessary?. Proceedings of the 26th Annual International Conference on Machine Learning, Montreal, QC, Canada.","DOI":"10.1145\/1553374.1553511"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01908075","article-title":"Comparing partitions","volume":"2","author":"Hubert","year":"1985","journal-title":"J. Classif."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Sch\u00f6lkopf, B., and Warmuth, M.K. Comparing Clusterings by the Variation of Information. Proceedings of the 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT\/Kernel 2003, Learning Theory and Kernel Machine, Washington, DC, USA, 24\u201327 August 2003.","DOI":"10.1007\/b12006"},{"key":"ref_51","unstructured":"Rijsbergen, C.J.V. (1979). Information Retrieval, Butterworth-Heinemann. [2nd ed.]."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Jacomy, M., Venturini, T., Heymann, S., and Bastian, M. (2014). ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software. PLoS ONE, 9.","DOI":"10.1371\/journal.pone.0098679"},{"key":"ref_53","unstructured":"Peixoto, T.P. (2017, August 16). The graph-tool python library. Available online: http:\/\/figshare.com\/articles\/graph_tool\/1164194."},{"key":"ref_54","first-page":"D428","article-title":"Reactome: A knowledgebase of biological pathways","volume":"33","author":"Gillespie","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013). KONECT: The Koblenz Network Collection, ACM. The Koblenz Network Collection.","DOI":"10.1145\/2487788.2488173"},{"key":"ref_56","unstructured":"Waugh, A.S., Pei, L., Fowler, J.H., Mucha, P.J., and Porter, M.A. (arXiv, 2009). Party Polarization in Congress: A Network Science Approach, arXiv."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"041108","DOI":"10.1063\/1.3518696","article-title":"Communities in multislice voting networks","volume":"20","author":"Mucha","year":"2010","journal-title":"Chaos"},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/978-3-642-25591-5_45","article-title":"Asymptotic modularity of some graph classes","volume":"7074","author":"Soto","year":"2011","journal-title":"Int. Symp. Algorithms Comput."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"066118","DOI":"10.1103\/PhysRevE.85.066118","article-title":"Communities and bottlenecks: Trees and treelike networks have high modularity","volume":"85","author":"Bagrow","year":"2012","journal-title":"Phys. Rev. E"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/93\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:42:48Z","timestamp":1760208168000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/3\/93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,19]]},"references-count":59,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2017,9]]}},"alternative-id":["a10030093"],"URL":"https:\/\/doi.org\/10.3390\/a10030093","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2017,8,19]]}}}