Coarsening Algorithm via Semi-synchronous Label Propagation for Bipartite Networks - Valejo, Alan Demétrius Baria; Althoff, Paulo Eduardo; Faleiros, Thiago de Paulo; Chuerubim, Maria Lígia; Yan, Jianglong; Liu, Weiguang; Zhao, Liang (Anais da Brazilian Conference on Intelligent Systems (BRACIS); 2021: Anais da X Brazilian Conference on Intelligent Systems, 2021)
Several coarsening algorithms have been developed as a powerful strategy to deal with difficult machine learning problems represented by large-scale networks, including, network visualization, trajectory mining, community detection and dimension reduction. It iteratively reduces the original network into a hierarchy of gradually smaller informative representations. However, few of these algorithms have been specifically designed to deal with bipartite networks and they still face theoretical limitations that need to be explored. Specifically, a recently introduced algorithm, called MLPb, is based on a synchronous label propagation strategy. In spite of an interesting approach, it presents the following two problems: 1) A high-cost search strategy in dense networks and 2) the cyclic oscillation problem yielded by the synchronous propagation scheme. In this paper, we address these issues and propose a novel fast coarsening algorithm more suitable for large-scale bipartite networks. Our proposal introduces a semi-synchronous strategy via cross-propagation, which allows a time-effective implementation and deeply reduces the oscillation phenomenon. The empirical analysis in both synthetic networks and real-world networks shows that our coarsening strategy outperforms previous approaches regarding accuracy and runtime.