A stepwise algorithm for community detection based on marginal utility and neighborhood

Community detection is a pivotal research area in network analysis. In this context, the nodes on the borders of multiple communities are of great significance, attributed to their crucial positions in the information flow of communities. From the perspective of a special disposition of such nodes, this study proposes a novel community detection method termed the AIA (acquisition-integration-allocation) algorithm to improve community detection. The algorithm consists of three steps: ① isolating certain nodes and creating multiple components to refine the structure of a network based on the principle of diminishing marginal utility and neighborhood information; ② integrating the components as the base of communities via the spectral clustering method; and ③ allocating the unprocessed nodes through label transfer and the Graclus distance. Experimental validations on both synthetic and real-world datasets demonstrate the effectiveness of the proposed approach.