Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Multilevel approach for combinatorial optimization in bipartite network

Texto completo
Autor(es):
Valejo, Alan [1] ; Ferreira de Oliveira, Maria Cristina [1] ; Filho, Geraldo P. R. [1] ; Lopes, Alneu de Andrade [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Math & Comp Sci ICMC, POB 668, BR-14560970 Sao Carlos, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: KNOWLEDGE-BASED SYSTEMS; v. 151, p. 45-61, JUL 1 2018.
Citações Web of Science: 2
Resumo

Multilevel approaches aim at reducing the cost of a target algorithm over a given network by applying it to a coarsened (or reduced) version of the original network. They have been successfully employed in a variety of problems, most notably community detection. However, current solutions are not directly applicable to bipartite networks and the literature lacks studies that illustrate their application for solving multilevel optimization problems in such networks. This article addresses this gap and introduces a multilevel optimization approach for bipartite networks and the implementation of a general multilevel framework including novel algorithms for coarsening and uncorsening, applicable to a variety of problems. We analyze how the proposed multilevel strategy affects the topological features of bipartite networks and show that a controlled coarsening strategy can preserve properties such as degree and clustering coefficient centralities. The applicability of the general framework is illustrated in two optimization problems, one for solving the Barber's modularity for community detection and the second for dimensionality reduction in text classification. We show that the solutions thus obtained are statistically equivalent, regarding accuracy, to those of conventional approaches, whilst requiring considerably lower execution times. (C) 2018 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 17/05838-3 - Visual analytics: aplicações e uma investigação conceitual
Beneficiário:Maria Cristina Ferreira de Oliveira
Modalidade de apoio: Auxílio à Pesquisa - Regular
Processo FAPESP: 15/14228-9 - Análise e Mineração de Redes Sociais
Beneficiário:Alneu de Andrade Lopes
Modalidade de apoio: Auxílio à Pesquisa - Regular