Title
A coarsening method for bipartite networks via weight-constrained label propagation
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.
Year
DOI
Venue
2020
10.1016/j.knosys.2020.105678
Knowledge-Based Systems
Keywords
DocType
Volume
Complex networks,Multilevel method,Large-scale networks,Bipartite networks,Community detection,Network coarsening,Network visualization
Journal
195
ISSN
Citations 
PageRank 
0950-7051
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Alan Valejo1154.60
Thiago Faleiros200.34
Maria Cristina Ferreira de Oliveira331326.34
Alneu de Andrade Lopes427529.00