Centrality Based Number Of Cluster Estimation In Graph Clustering

Graph clustering algorithms require the number of the clusters as an input. However, in many real-world practical applications the correct number of the clusters is unknown. Determining the optimal number of clusters for graph clustering algorithms is an essential and challenging task which is a form of model order selection. Here, we propose a new algorithm for estimating the number of clusters in a graph, using the centrality measure. In graph theory, centrality measure is used for determining the most important and most influential nodes within a graph. The proposed centrality based number of cluster estimation (CB-NCE) method considers minimizing the probabilistic bounds on average central error of centrality. The desired criterion represents an information theoretic distance measure in form of description length of centrality. The simulation results show the superior performance of the proposed algorithm among other existing methods, in terms of clustering performance metrics such as normalized mutual information, Rand index and F-measure.