Rearranging 'indivisible' blocks for community detection

Peng Gang Sun, Xunlian Wu, Yining 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 Yining 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