SACA: SCM-based adaptive clustering algorithm

Network clustering is an important technique widely used in efficient hierarchical routing protocol design, network modelling and performance evaluation, etc. In this paper, we discuss the important clustering criteria, such as node connectivity, cluster diameter, number of orphan nodes. Our main contribution is a novel clustering algorithm SACA based on an accurate clustering measure called SCM. SACA adaptively forms clusters to incrementally improve the clustering quality, taking node connectivity into consideration. It can control the cluster size effectively and limit the number of orphan nodes. Our simulation study indicates that SACA is more accurate than MCL, a well accepted scalable and efficient clustering scheme, while requiring comparable running time for power law topologies and grid topologies, and significantly less running time for random topologies.