{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,23]],"date-time":"2025-11-23T15:03:41Z","timestamp":1763910221627,"version":"3.41.2"},"reference-count":52,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Mitacs-Accelerate","award":["IT05806"],"award-info":[{"award-number":["IT05806"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We introduce graph clustering quality measures based on comparisons of global, intra- and inter-cluster densities, an accompanying statistical significance test and a step-by-step routine for clustering quality assessment. Our work is centred on the idea that well-clustered graphs will display a mean intra-cluster density that is higher than global density and mean inter-cluster density. We do not rely on any generative model for the null model graph. Our measures are shown to meet the axioms of a good clustering quality function. They have an intuitive graph-theoretic interpretation, a formal statistical interpretation and can be tested for significance. Empirical tests also show they are more responsive to graph structure, less likely to breakdown during numerical implementation and less sensitive to uncertainty in connectivity than the commonly used measures.<\/jats:p>","DOI":"10.1093\/comnet\/cnaa012","type":"journal-article","created":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T20:11:03Z","timestamp":1584475863000},"source":"Crossref","is-referenced-by-count":13,"title":["A density-based statistical analysis of graph clustering algorithm performance"],"prefix":"10.1093","volume":"8","author":[{"given":"Pierre","family":"Miasnikof","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander Y","family":"Shestopaloff","sequence":"additional","affiliation":[{"name":"The Alan Turing Institute, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony J","family":"Bonner","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuri","family":"Lawryshyn","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panos M","family":"Pardalos","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL, USA and HSE University, Russian Federation"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"key":"2020080304202756700_B1","first-page":"113","author":"Aloise,","year":"2012","journal-title":"Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13-14, 2012. Proceedings"},{"key":"2020080304202756700_B2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10898-009-9520-1","article-title":"Linear and quadratic programming approaches for the general graph partitioning problem","volume":"48","author":"Fan,","year":"2010","journal-title":"J. Global Optim."},{"key":"2020080304202756700_B3","first-page":"170","article-title":"Robust optimization of graph partitioning and critical node detection in analyzing networks","volume-title":"Proceedings of the 4th International Conference on Combinatorial Optimization and Applications - Volume Part I, COCOA\u201910","author":"Fan & Pardalos,","year":"2010"},{"key":"2020080304202756700_B4","doi-asserted-by":"crossref","first-page":"3121","DOI":"10.1016\/j.cor.2013.03.002","article-title":"Community detection by modularity maximization using GRASP with path relinking","volume":"40","author":"Nascimento,","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"2020080304202756700_B5","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":"2020080304202756700_B6","first-page":"1","author":"Sanders,","year":"2012","journal-title":"Proceedings of Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13\u201314, 2012"},{"key":"2020080304202756700_B7","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/978-3-642-23780-5_13","article-title":"Is there a best quality metric for graph clusters?","author":"Almeida,","year":"2011","journal-title":"Proceedings of Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2011, Athens, Greece, September 5-9, 2011. Part I"},{"key":"2020080304202756700_B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.eswa.2016.11.011","article-title":"Defining quality metrics for graph clustering evaluation","volume":"71","author":"Biswas,","year":"2017","journal-title":"Expert Syst. Appl."},{"journal-title":"On the evaluation potential of quality functions in community detection for different contexts","year":"2015","author":"Creusefond,","key":"2020080304202756700_B9"},{"key":"2020080304202756700_B10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pone.0159161","article-title":"Analysis of network clustering algorithms and cluster quality metrics at scale","volume":"11","author":"Emmons,","year":"2016","journal-title":"PLoS One"},{"key":"2020080304202756700_B11","first-page":"315","volume-title":"Handbook of Cluster Analysis","author":"Huang,","year":"2015"},{"journal-title":"Graph clustering quality functions","year":"2018","author":"Kehagias,","key":"2020080304202756700_B12"},{"key":"2020080304202756700_B13","first-page":"193","article-title":"Axioms for graph clustering quality functions","volume":"15","author":"Van Laarhoven,","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"2020080304202756700_B14","doi-asserted-by":"crossref","first-page":"056117","DOI":"10.1103\/PhysRevE.80.056117","article-title":"Community detection algorithms: a comparative analysis","volume":"80","author":"Lancichinetti,","year":"2009","journal-title":"Phys. Rev. E"},{"key":"2020080304202756700_B15","doi-asserted-by":"crossref","first-page":"046110","DOI":"10.1103\/PhysRevE.78.046110","article-title":"Benchmark graphs for testing community detection algorithms","volume":"78","author":"Lancichinetti,","year":"2008","journal-title":"Phys. Rev. E"},{"journal-title":"Empirical comparison of algorithms for network community detection","year":"2010","author":"Leskovec,","key":"2020080304202756700_B16"},{"key":"2020080304202756700_B17","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1186\/1756-0500-4-549","article-title":"Which clustering algorithm is better for predicting protein complexes?","volume":"4","author":"Moschopoulos,","year":"2011","journal-title":"BMC Res. Notes"},{"journal-title":"Using synthetic networks for parameter tuning in community detection","year":"2019","author":"Prokhorenkova,","key":"2020080304202756700_B18"},{"key":"2020080304202756700_B19","article-title":"Size matters: a comparative analysis of community detection algorithms","author":"Wagenseller,","year":"2017","journal-title":"CoRR"},{"key":"2020080304202756700_B20","article-title":"Defining and evaluating network communities based on ground-truth","author":"Yang,","year":"2012","journal-title":"CoRR"},{"key":"2020080304202756700_B21","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.physd.2006.09.009","article-title":"When are networks truly modular?","volume":"224","author":"Reichardt,","year":"2006","journal-title":"Physica D"},{"key":"2020080304202756700_B22","doi-asserted-by":"crossref","first-page":"P10008","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."},{"key":"2020080304202756700_B23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/080744888","article-title":"A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning","volume":"42","author":"Spielman,","year":"2013","journal-title":"SIAM J. Comput."},{"key":"2020080304202756700_B24","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":"2020080304202756700_B25","first-page":"066111","author":"Clauset,","year":"2004","journal-title":"Finding community structure in very large networks"},{"key":"2020080304202756700_B26","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":"2020080304202756700_B27","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1140\/epjb\/e2013-40169-1","article-title":"Bad communities with high modularity","volume":"86","author":"Kehagias,","year":"2013","journal-title":"Eur. Phys. J. B"},{"key":"2020080304202756700_B28","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/978-3-319-49787-7_10","volume-title":"Algorithms and Models for the Web Graph","author":"Ostroumova Prokhorenkova,","year":"2016"},{"key":"2020080304202756700_B29","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1016\/j.endm.2017.07.058","article-title":"Modularity in several random graph models","volume":"61","author":"Ostroumova Prokhorenkova,","year":"2017","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"2020080304202756700_B30","first-page":"103","author":"Djidjev,","year":"2012","journal-title":"Proceedings on Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13-14, 2012"},{"key":"2020080304202756700_B31","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":"2020080304202756700_B32","first-page":"046106","volume":"81","author":"Good,","year":"2010","journal-title":"Performance of modularity maximization in practical contexts"},{"key":"2020080304202756700_B33","article-title":"Statistical properties of community structure in large social and information networks","author":"Leskovec,","year":"2008","journal-title":"7th International Conference on WWW"},{"key":"2020080304202756700_B34","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1145\/990308.990313","article-title":"On clusterings: good, bad and spectral","volume":"51","author":"Kannan,","year":"2004","journal-title":"J. ACM"},{"key":"2020080304202756700_B35","first-page":"45","article-title":"Using automatic clustering to produce high-level system organizations of source code","author":"Mancoridis,","year":"1998","journal-title":"Program Comprehension, Workshop Proceedings"},{"key":"2020080304202756700_B36","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":"2020080304202756700_B37","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The Elements of Statistical Learning, Second Edition: Data Mining, Inference, and Prediction","author":"Hastie,","year":"2009","edition":"2nd ed."},{"key":"2020080304202756700_B38","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-92871-5_11","volume-title":"A Statistical Performance Analysis of Graph Clustering Algorithms","author":"Miasnikof,","year":"2018"},{"key":"2020080304202756700_B39","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/2980765.2980770","article-title":"Current and future challenges in mining large networks: report on the second SDM workshop on mining networks and graphs","volume":"18","author":"Holder,","year":"2016","journal-title":"SIGKDD Explor. Newsl."},{"key":"2020080304202756700_B40","first-page":"121","article-title":"Measures of clustering quality: a working set of axioms for clustering","author":"Ackerman,","year":"2008","journal-title":"Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference"},{"key":"2020080304202756700_B41","first-page":"463","volume-title":"Advances in Neural Information Processing Systems 15","author":"Kleinberg,","year":"2003"},{"key":"2020080304202756700_B42","first-page":"573","volume-title":"Game-Theoretic Framework for Community Detection","author":"McSweeney,","year":"2014"},{"journal-title":"Community detection in networks: a user guide","year":"2016","author":"Fortunato,","key":"2020080304202756700_B43"},{"key":"2020080304202756700_B44","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.neuroimage.2016.11.026","article-title":"Community detection in weighted brain connectivity networks beyond the resolution limit","volume":"146","author":"Nicolini,","year":"2017","journal-title":"NeuroImage"},{"key":"2020080304202756700_B45","doi-asserted-by":"crossref","DOI":"10.1145\/2433396.2433471","article-title":"Overlapping community detection at scale: a nonnegative matrix factorization approach","volume-title":"WSDM\u201913","author":"Yang,","year":"2013"},{"key":"2020080304202756700_B46","doi-asserted-by":"crossref","first-page":"056113","DOI":"10.1103\/PhysRevE.82.056113","article-title":"Spectral graph analysis of modularity and assortativity","volume":"82","author":"Van Mieghem,","year":"2010","journal-title":"Phys. Rev. E"},{"key":"2020080304202756700_B47","doi-asserted-by":"crossref","first-page":"036106","DOI":"10.1103\/PhysRevE.76.036106","article-title":"Near linear time algorithm to detect community structures in large-scale networks","volume":"76","author":"Raghavan,","year":"2007","journal-title":"Phys. Rev. E"},{"key":"2020080304202756700_B48","first-page":"11","volume-title":"Proceedings of the 7th Python in Science Conference","author":"Hagberg,","year":"2008"},{"key":"2020080304202756700_B49","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: densification and shrinking diameters","volume":"1","author":"Leskovec,","year":"2007","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"2020080304202756700_B50","doi-asserted-by":"crossref","DOI":"10.1145\/3097983.3098069","article-title":"Local higher-order graph clustering","author":"Yin,","year":"2017","journal-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017"},{"journal-title":"Extension of modularity density for overlapping community structure","year":"2015","author":"Chen,","key":"2020080304202756700_B51"},{"key":"2020080304202756700_B52","doi-asserted-by":"crossref","first-page":"18001","DOI":"10.1209\/0295-5075\/90\/18001","article-title":"Modularity measure of networks with overlapping communities","volume":"90","author":"L\u00e0z\u00e0r,","year":"2010","journal-title":"EPL (Europhys. Lett.)"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/3\/cnaa012\/33558820\/cnaa012.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/3\/cnaa012\/33558820\/cnaa012.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T08:21:04Z","timestamp":1596442864000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnaa012\/5879900"}},"subtitle":[],"editor":[{"given":"Ernesto","family":"Estrada","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,6,1]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnaa012","relation":{},"ISSN":["2051-1310","2051-1329"],"issn-type":[{"type":"print","value":"2051-1310"},{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2020,6]]},"published":{"date-parts":[[2020,6,1]]},"article-number":"cnaa012"}}