A review and comparative analysis of coarsening algorithms on bipartite networks

Autor(es)

Valejo, Alan Demetrius Baria ^[1] ; de Oliveira dos Santos, Wellington ^[1] ; Naldi, Murilo Coelho ^[1] ; Zhao, Liang ^[2]

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

^[1] Fed Univ Sao Carlos UFSCar, Dept Comp Sci, Sao Carlos, SP - Brazil

^[2] Univ Sao Paulo, Dept Comp & Math DCM, FFCLRP, Ribeirao Preto, SP - Brazil

• Tipo de documento: Artigo de Revisão
• Fonte: European Physical Journal-Special Topics; v. 230, n. 14-15, p. 2801-2811, OCT 2021.
• Citações Web of Science: 1

Resumo

Coarsening algorithms have been successfully used as a powerful strategy to deal with data-intensive machine learning problems defined in bipartite networks, such as clustering, dimensionality reduction, and visualization. Their main goal is to build informative simplifications of the original network at different levels of details. Despite its widespread relevance, a comparative analysis of these algorithms and performance evaluation is needed. Additionally, some aspects of these algorithms' current versions have not been explored in their original or complementary studies. In that regard, we strive to fill this gap, presenting a formal and illustrative description of coarsening algorithms developed for bipartite networks. Afterward, we illustrate the usage of these algorithms in a set of emblematic problems. Finally, we evaluate and quantify their accuracy using quality and runtime measures in a set of thousands of synthetic and real-world networks with various properties and structures. The presented empirical analysis provides evidence to assess the strengths and shortcomings of such algorithms. Our study is a unified and useful resource that provides guidelines to researchers interested in learning about and applying these algorithms. (AU)

• Processo FAPESP: 19/09817-6 - Modelos descritivos escaláveis para grandes volumes de dados distribuídos
• Beneficiário: Murilo Coelho Naldi
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• 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 Aplicada
• 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: 19/14429-5 - Análise visual de redes cerebrais heterogêneas usando métodos multilíveis
• Beneficiário: Alan Demétrius Baria Valejo
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado