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

Autor(es)

Neto Verri, Filipe Alves ^[1] ; Gueleri, Roberto Alves ^[2] ; Zheng, Qiusheng ^[3] ; Zhang, Junbao ^[3] ; Zhao, Liang ^[4]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: European Physical Journal-Special Topics; v. 230, n. 14-15, p. 2843-2855, OCT 2021.
• Citações Web of Science: 1

Resumo

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)

• Processo FAPESP: 13/08666-8 - Desenvolvimento de técnicas de aprendizado semissupervisionado via sistemas dinâmicos coletivos
• Beneficiário: Roberto Alves Gueleri
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 19/07665-4 - Centro de Inteligência Artificial
• Beneficiário: Fabio Gagliardi Cozman
• Modalidade de apoio: Auxílio à Pesquisa - Programa eScience e Data Science - Centros de Pesquisa em Engenharia
• Processo FAPESP: 15/50122-0 - Fenômenos dinâmicos em redes complexas: fundamentos e aplicações
• Beneficiário: Elbert Einstein Nehrer Macau
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/25876-6 - Classificação de dados de alto nível baseada em redes complexas com aplicações em reconhecimento invariante de padrões
• Beneficiário: Filipe Alves Neto Verri
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto