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

A coarsening method for bipartite networks via weight-constrained label propagation

Texto completo
Autor(es):
Valejo, Alan [1] ; Faleiros, Thiago [2] ; Ferreira de Oliveira, Maria Cristina [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
[2] Univ Brasilia UnB, Dept Comp Sci CiC, POB 4466, BR-70910900 Brasilia, DF - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: KNOWLEDGE-BASED SYSTEMS; v. 195, MAY 11 2020.
Citações Web of Science: 0
Resumo

A multilevel method is a scalable strategy to solve optimization problems in large bipartite networks, which operates in three stages. Initially the input network is iteratively coarsened into a hierarchy of gradually smaller networks. Coarsening implies in collapsing vertices into so-called super-vertices which inherit properties of their originating vertices. An initial solution is obtained executing the target algorithm in the coarsest network. Finally, this solution is successively projected back over the inverse sequence of coarsened networks, up to the initial one, yielding an approximate final solution. Despite its potential applicability, the strategy faces several theoretical and practical limitations. Coarsening is usually attained following a user-defined policy to match vertices pairwise. However, the network reduction process is extremely slow and may yield degraded solutions due to propagation of poor matches. Additionally, proper parameterization of coarsening algorithms is difficult, as well as ensuring the super-vertices preserve the relevant properties. We address these issues with a near-linear complexity coarsening strategy based on weight-constrained label propagation. Our strategy collapses groups of vertices, rather than pairs, yielding faster and more extensive network reduction. Moreover, users may specify the desired size of the coarsest network and control super-vertex weights. The applicability of our solution is illustrated in multiple scenarios, namely: multilevel implementation of an existing high-cost community detection algorithm; as a direct community detection algorithm; finally, network visualization, in connection with force-directed graph drawing algorithms. Results provide empirical evidence on the potential of our proposal to foster novel applications of the multilevel method in bipartite networks. (C) 2020 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
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 15/14228-9 - Análise e Mineração de Redes Sociais
Beneficiário:Alneu de Andrade Lopes
Linha de fomento: Auxílio à Pesquisa - Regular