Detecting the number of clusters in a network. (7th March 2021)

• Record Type: Journal Article
• Authors: Budel, Gabriel; Van Mieghem, Piet
• Editors: Estrada, Ernesto
• Is Part Of: Journal of complex networks. Volume 8:Number 6(2020)
• Publication Date: 2021-03-07
• Subjects: Complex Networks -- Community Detection -- Spectral Clustering -- Number of Clusters -- Non-backtracking Matrix; Numerical analysis -- Periodicals; Computer networks -- Periodicals; Social networks -- Periodicals; 518.05
• DOI: 10.1093/comnet/cnaa047
• Languages: English
• ISSNs: 2051-1310

Abstract

Abstract: Many clustering algorithms for complex networks depend on the choice for the number of clusters and it is often unclear how to make this choice. The number of eigenvalues located outside a circle in the spectrum of the non-backtracking matrix was conjectured to be an estimator of the number of clusters in a graph. We compare the estimate of the number of clusters obtained from the spectrum of the non-backtracking matrix with three estimators based on the concept of modularity and evaluate the methods on several benchmark graphs. We find that the non-backtracking method detects the number of clusters better than the modularity-based methods for the graphs in our simulation study, especially when the clusters have slightly different sizes. The estimates of the non-backtracking method are narrowly distributed around the true number of clusters for all benchmark graphs considered. Additionally, for graphs without a clustering structure, the non-backtracking method detects exactly one cluster, which is a convenient property of an estimator of the number of clusters. However, the lack of a well-defined concept of a cluster prevents sharp conclusions.