Automatic network clustering via density-constrained optimization with grouping operator

• The network clustering is formulated as the density-constrained optimization and an evolutionary algorithm is provided.
• The proposed clustering algorithm can be free from the resolution limit problem.
• The performance of the algorithm does not sensitively depend on the parameter.
• The detection accuracy is also obviously improved by the density constraint.

Automatic network clustering is an important technique for mining the meaningful communities (or clusters) of a network. Communities in a network are clusters of nodes where the intra-cluster connection density is high and the inter-cluster connection density is low. The most popular scheme of automatic network clustering aims at maximizing a criterion function known as modularity in partitioning all the nodes into clusters. But it is found that the modularity suffers from the resolution limit problem, which remains an open challenge. In this paper, the automatic network clustering is formulated as a constrained optimization problem: maximizing a criterion function with a density constraint. With this scheme, the established algorithm can be free from the resolution limit problem. Furthermore, it is found that the density constraint can improve the detection accuracy of the modularity optimization. The efficiency of the proposed scheme is verified by comparative experiments on large scale benchmark networks.