| Full text | |
| Author(s): |
Valejo, Alan
[1]
;
Faleiros, Thiago
[2]
;
Ferreira de Oliveira, Maria Cristina
[1]
;
Lopes, Alneu de Andrade
[1]
Total Authors: 4
|
| Affiliation: | [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
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | KNOWLEDGE-BASED SYSTEMS; v. 195, MAY 11 2020. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| FAPESP's process: | 17/05838-3 - Visual analytics: applications and a conceptual investigation |
| Grantee: | Maria Cristina Ferreira de Oliveira |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 15/14228-9 - Social Network Analysis and Mining |
| Grantee: | Alneu de Andrade Lopes |
| Support Opportunities: | Regular Research Grants |