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