Coarsening Algorithm via Semi-synchronous Label Propagation for Bipartite Networks

• Alan Demétrius Baria Valejo UFSCar
• Paulo Eduardo Althoff UnB
• Thiago de Paulo Faleiros UnB
• Maria Lígia Chuerubim UFU
• Jianglong Yan Zhongyuan University of Technology
• Weiguang Liu Zhongyuan University of Technology
• Liang Zhao USP

Resumo

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.

Palavras-chave: Complex networks, Bipartite networks, Multilevel method, Multiscaling analysis