On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach

On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach
Title:
On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach
Other Titles:
SIAM International Conference on Data Mining
DOI:
10.1137/1.9781611974348.36
Publication Date:
05 May 2016
Citation:
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.
License type:
PublisherCopyrights
Funding Info:
Description:
ISBN:
978-1-61197-434-8
Files uploaded:

File Size Format Action
sdm16.pdf 863.97 KB PDF Open