Rearranging 'indivisible' Blocks for Community Detection

Peng Gang Sun, Xunlian Wu, Yi-Ning Quan, Qiguang Miao

Abstract

Unattributed social networks are more complicated, and it tends not to determine the best division by over-optimizing a theoretical measure for unsupervised algorithms. Nowadays, communities strongly overlap due to the fact that people strongly interact, which makes community detection even more challenging. The paper develops a new algorithm by rearranging ‘indivisible’ blocks (RaidB). In RaidB, we first initialize ‘indivisible’ blocks by disjoint $k$-clique blocks in a network, and then these blocks are rearranged by moving nodes from one block to another based on maximizing modularity to uncover non-overlapping communities. For identifying overlapping communities, the above blocks are further rearranged, i.e., each block is subdivided and expanded to determine sub-blocks by introducing a dynamic linear threshold (DLT) model for influence interpenetration, and we finally determine a division from these sub-blocks with the minimum size that can cover the network. We compare RaidB with the existing state of the art methods for non-overlapping and overlapping community detection. The results show that RaidB tends to achieve better performance especially on sparse networks with unobvious communities and networks with strongly overlapping communities.
BibTeX
@article{sun2023rearranging,
  author = {Peng Gang Sun and Xunlian Wu and Yi-Ning Quan and Qiguang Miao},
  title = {{Rearranging 'indivisible' Blocks for Community Detection}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  url = {https://openreview.net/forum?id=rGYHYbwGNK},
}

Loading related content...

Figure