Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Network community detection via iterative edge removal in a flocking-like system

Full text
Neto Verri, Filipe Alves [1] ; Gueleri, Roberto Alves [2] ; Zheng, Qiusheng [3] ; Zhang, Junbao [3] ; Zhao, Liang [4]
Total Authors: 5
[1] Aeronaut Inst Technol, Comp Sci Div, Sao Jose Dos Campos - Brazil
[2] Univ Sao Paulo, Inst Math & Comp Sci, Sao Carlos - Brazil
[3] Zhongyuan Univ Technol, Sch Comp Sci, Zhengzhou - Peoples R China
[4] Univ Sao Paulo, Fac Philosophy Sci & Letters Ribeirao Preto, Ribeirao Preto - Brazil
Total Affiliations: 4
Document type: Journal article
Source: European Physical Journal-Special Topics; v. 230, n. 14-15, p. 2843-2855, OCT 2021.
Web of Science Citations: 1

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. (AU)

FAPESP's process: 13/08666-8 - Development of semi-supervised learning techniques via collective dynamical systems
Grantee:Roberto Alves Gueleri
Support type: Scholarships in Brazil - Doctorate
FAPESP's process: 19/07665-4 - Center for Artificial Intelligence
Grantee:Fabio Gagliardi Cozman
Support type: Research Grants - Research Centers in Engineering Program
FAPESP's process: 15/50122-0 - Dynamic phenomena in complex networks: basics and applications
Grantee:Elbert Einstein Nehrer Macau
Support type: Research Projects - Thematic Grants
FAPESP's process: 13/25876-6 - High level data classification based on complex network applied to invariant pattern recognition
Grantee:Filipe Alves Neto Verri
Support type: Scholarships in Brazil - Doctorate (Direct)