A density-based statistical analysis of graph clustering algorithm performance. (3rd August 2020)

• Record Type: Journal Article
• Authors: Miasnikof, Pierre; Shestopaloff, Alexander Y; Bonner, Anthony J; Lawryshyn, Yuri; Pardalos, Panos M
• Editors: Estrada, Ernesto
• Is Part Of: Journal of complex networks. Volume 8:Number 3(2020)
• Publication Date: 2020-08-03
• Subjects: graph clustering -- graph community detection -- modularity -- conductance -- graph mining -- network science -- complex networks -- social networks -- unsupervised learning -- data science -- data analysis; Numerical analysis -- Periodicals; Computer networks -- Periodicals; Social networks -- Periodicals; 518.05
• DOI: 10.1093/comnet/cnaa012
• Languages: English
• ISSNs: 2051-1310

Abstract

Abstract: 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.