A divide and agglomerate algorithm for community detection in social networks

Communities, or clusters, are usually subgraphs of nodes densely interconnected but sparsely linked with others. The nodes with similar properties or behaviors are more likely to be in the same community, and vice versa. However, due to the complexity and diversity of networks, the accurate organization or function of communities in many real networks is often extremely difficult to be recognized. Hence, methods for community detection would have immediate impact on understanding the organizations and functions of networks. Therefore, algorithm design becomes a fundamental problem for many networks. In this paper, the local and global information are applied together to propose a divide and agglomerate (DA) algorithm for community detection in social networks. The DA algorithm achieves the result with a two-stage strategy: Dividing a network into small groups according to node pairs' similarities, and merging a group with the other who has the biggest attraction for it until the community criterion is steady. The novel similarity, constrained AA index captures the local and global information ensuring the optimal communities detection. The results of experiments show that DA algorithm obtains superior community results compared with six other widely used algorithms, which indicate that DA algorithm has advantages for community detection. (C) 2019 Elsevier Inc. All rights reserved.