https://doi.org/10.1140/epjs/s11734-021-00154-5
Regular Article
Network community detection via iterative edge removal in a flocking-like system
1
Computer Science Division, Aeronautics Institute of Technology, São José dos Campos, Brazil
2
Institute of Mathematics and Computer Science, University of São Paulo, São Carlos, Brazil
3
School of Computer Science, Zhongyuan University of Technology, Zhengzhou, China
4
Faculty of Philosophy, Science and Letters at Ribeirão Preto, University of São Paulo, Ribeirão Prêto, Brazil
Received:
16
September
2020
Accepted:
21
April
2021
Published online:
8
June
2021
We present a network community-detection technique based on properties that emerge from a nature-inspired flocking system. Our algorithm comprises two alternating mechanisms: first, we control the particles alignment in higher dimensional space and, second, we present an iterative process of edge removal. These mechanisms together can potentially reduce accidental alignment among particles from different communities and, consequently, the model can generate robust community-detection results. In the proposed model, a random-direction unit vector is assigned to each vertex initially. A nonlinear dynamic law is established, so that neighboring vertices try to become aligned with each other. After some time, the system stops and edges that connect the least-aligned pairs of vertices are removed. Then, the evolution starts over without the removed edges, and after enough number of removal rounds, each community becomes a connected component. The proposed approach is evaluated using widely accepted benchmarks and real-world networks. Experimental results reveal that the method is robust and excels on a wide variety of networks. For large sparse networks, the edge-removal process runs in quasilinear time, which enables application in large-scale networks. Moreover, the distributed nature of the process eases the parallel implementation of the model.
© The Author(s), under exclusive licence to EDP Sciences, Springer-Verlag GmbH Germany, part of Springer Nature 2021
