CENTRALITY BASED NUMBER OF CLUSTER ESTIMATION IN GRAPH CLUSTERING

Graph clustering algorithms require the number of clusters as an input. However, in many real-world practical applications, the correct number of 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, the 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 the average central error of centrality. The desired criterion represents an information theoretic distance measure in the 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.