On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach Eran Shaham, Honghai Yu, and Xiao-Li Li Proceedings of the 2016 SIAM International Conference on Data Mining. 2016, 315-323
Abstract:
Bipartite graphs have been proven useful in modeling a wide range of relationship networks. Finding the maximum edge biclique within a bipartite graph is a well-known problem in graph theory and data mining, with numerous real-world applications across different domains. We propose a probabilistic algorithm for finding the maximum edge biclique using a Monte Carlo subspace clustering approach. Extensive experimentation with both artificial and real-world datasets shows that the algorithm is significantly better than the state-of-the-art technique. We prove that there are solid theoretical reasons for the algorithm’s efficacy that manifest in a polynomial complexity of time and space.