Detecting the number of clusters in a network

Research output: Contribution to journalArticleScientificpeer-review

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.

Original languageEnglish
Article numbercnaa047
Number of pages1
JournalJournal of Complex Networks
Volume8
Issue number6
DOIs
Publication statusPublished - 2021

Keywords

  • Community Detection
  • Complex Networks
  • Non-backtracking Matrix
  • Number of Clusters
  • Spectral Clustering

Fingerprint

Dive into the research topics of 'Detecting the number of clusters in a network'. Together they form a unique fingerprint.

Cite this