An Exact Algorithm for Finding K-Biclique Vertex Partitions of Bipartites

Biclustering has been extensively studied in many fields such as data mining, e-commerce, computational biology, information security, etc. Problems of finding bicliques in bipartite, which are variants of biclustering, have received much attention in recent years due to its importance for biclustering. The k-biclique vertex partition problem proposed by Bein et al. is one of finding bicliques problems in bipartite. Its aim is to find k bicliques (kk) such that each vertex of the bipartite occurs in exactly one member of these bicliques. First, we give a sufficient condition of the k-biclique vertex partition problem. Moreover, we present an exact algorithm for finding k-biclique vertex partitions of a bipartite. Finally, we propose a method to generate simulated datasets used to test the algorithm. Experimental results on simulated datasets show that the algorithm can find k-biclique vertex partitions of a bipartite with relatively fast speed.