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

Abstract:

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.

• Periodical: Advanced Materials Research (Volume 710)
• Pages: 687-691
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.710.687
• Online since: June 2013
• Authors: Pei Qiang Liu
• Keywords: Algorithm (GA), Biclique, Bipartite, Complexity, K-Biclique Vertex Partition

References

[1] Abello JM, Pardalos PM, Resende MGC. Handbook of massive data sets. The Netherlands: Kluwer Academic Publishers, 2002.

[2] Busygin S, Prokopyev O, Pardalos P. Biclustering in data mining. Computers & Operations Research, 2008, 35(9):2964-2987.

DOI: 10.1016/j.cor.2007.01.005

[3] Jain AK. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 2010, 31(8):651-666.

DOI: 10.1016/j.patrec.2009.09.011

[4] Madeira SC, Oliveira AL. Biclustering Algorithms for Biological Data Analysis: A Survey. IEEE/ACM Trans Comput Biol Bioinformatics, 2004, 1(1):24-45.

DOI: 10.1109/tcbb.2004.2

[5] Tanay A, Sharan R, Shamir R.Biclustering Algorithms: A Survey. Handbook of Computational Molecular Biology.Aluru S, ed. London; Chapman and Hall/CRC Press. 2006: 26_21-26_17.

DOI: 10.1201/9781420036275.ch26

[6] Cheng Y, Church GM. Biclustering of Expression Data. In: Bourne PE, Gribskov M, Altman RB, eds. Proc. of ISMB'00. California: AAAI Press, 2000.93-103.

[7] Hartigan J. Direct clustering of a data matrix. Journal of the American Statistical Association, 1972:123-129.

[8] Yang J, Wang W, Wang H, et al. δ-clusters: capturing subspace correlation in a large data set. In: Agrawal R, Dittrich K, Ngu AH, eds. Proc. of the 18th International Conference on Data Engineering. Washington: IEEE Computer Society, 2002.517-528.

DOI: 10.1109/icde.2002.994771

[9] Dhillon IS. Co-clustering documents and words using bipartite spectral graph partitioning. In: Lee D, Schkolnick M, Provost F, eds. Proc. of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. New York: ACM, 2001.269-274.

DOI: 10.1145/502512.502550

[10] Chakrabarti D, Papadimitriou S, Modha DS, et al. Fully automatic cross-associations. In: Kim W, Kohavi R, Gehrke J, eds. Proc. of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. New York: ACM, 2004.79-88.

DOI: 10.1145/1014052.1014064

[11] Figueroa A, Borneman J, Jiang T. Clustering binary fingerprint vectors with missing values for DNA array data analysis. Journal of Computational Biology, 2004, 11(5):887-901.

DOI: 10.1089/cmb.2004.11.887

[12] Liu PQ, Zhu DM, Xie QS, et al. Complexity and improved heuristic algorithms for binary fingerprints clustering. Journal of Software, 2008, 19(3):500-510.

DOI: 10.3724/sp.j.1001.2008.00500

[13] Wang L, Lin Y, Liu X. Approximation Algorithms for Biclustering Problems. SIAM Journal on Computing, 2008, 38(4):1504-1518.

DOI: 10.1137/060664112

[14] Zhang ZY, Li T, Ding C, et al. Binary matrix factorization for analyzing gene expression data. Data Mining and Knowledge Discovery, 2010, 20(1):28-52.

DOI: 10.1007/s10618-009-0145-2

[15] Amit N. The Bicluster Graph Editing problem.Master, Tel Aviv: Tel Aviv University, 2004.

[16] Tanay A, Sharan R, Shamir R. Discovering statistically significant biclusters in gene expression data. Bioinformatics 2002, 18 Suppl 1:S136-144.

DOI: 10.1093/bioinformatics/18.suppl_1.s136

[17] Dawande M, Keskinocak P, Swaminathan JM, et al. On Bipartite and Multipartite Clique Problems. Journal of Algorithms, 2001, 41(2):388-403.

DOI: 10.1006/jagm.2001.1199

[18] Dawande M, Keskinocak P, Tayur S. On the biclique problem in bipartite graphs.GSIA Working Paper, Pittsburgh, PA 15213, USA: Carnegie Mellon University, 1996.

[19] Peeters R. The maximum edge biclique problem is NP-complete. Discrete Applied Mathematics, 2003, 131(3):651-654.

DOI: 10.1016/s0166-218x(03)00333-0

[20] Harary F. Graph Theory. 1969. Addison-Wesley, Reading, MA.

[21] Heydari MH, Morales L, C. O. Shields J, et al. Computing Cross Associations for Attack Graphs and Other Applications. In: Ralph H. Sprague J, ed. Proc. of the 40th Annual Hawaii International Conference on System Sciences. Washington, DC, USA: IEEE Computer Society, 2007.270b.

DOI: 10.1109/hicss.2007.141

[22] Bein D, Morales L, Bein W, et al. Clustering and the Biclique Partition Problem. In: Ralph H. Sprague J, ed. Proc. of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008). Big Island, Hawaii: IEEE Computer Society Press, 2008.475.

DOI: 10.1109/hicss.2008.21

[23] Garey M, Johnson D. Computers and intractability. A guide to the theory of NP-completeness. New York, NY, USA: W.H. Freeman and Company, 1979.

[24] Prelic A. A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics, 2005, 22(9):1122-1129.