Abstract
Enumerating maximal biclique subgraphs from a graph is substantially important in many fields such as web mining, business intelligence, bioinformatics, social network analysis and so on. Although many previous studies have contributed much to efficient enumerating maximal biclique subgraphs from a graph, all of them proposed their algorithms based on a large static graph which remained unchanged in their application scenarios. In the real world, the social networks and other models have often dynamically changed thus either vertices or edges will be added to or removed from the corresponding graph. Therefore, these traditional approaches are not effective because they will repeat a complete enumeration process which has much repetitive work done in the previous enumeration. To reduce repetitive work and achieve high efficiency, we proposed a novel algorithm for enumerating maximal bicliques in a dynamically changed graph. Rather than to search the whole graph from first to last, we only search for newly created or reduced maximal bicliques based on the results enumerated before the change of the graph. In this paper, we proved the rightness of our methods and performed many simulations compared with other algorithms only for static graphs. The results demonstrated that our methods achieved high efficiency for dynamically changed graphs.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsReferences
Yi, J., Maghoul, F.: Query clustering using click-through graph. In: International Conference on World Wide Web, pp. 1055–1056. ACM (2009)
Selvan, S., Nataraj, R.V.: Efficient mining of large maximal bicliques from 3D symmetric adjacency matrix. IEEE Trans. Knowl. Data Eng. 22(12), 1797–1802 (2010)
Li, J., Liu, G., Li, H., Wong, L.: Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: A one-to-one correspondence and mining algorithms. IEEE Trans. Knowl. Data Eng. 19(12), 1625–1637 (2007)
Chu, W., Song, Y., Jaimes, A.: Video co-summarization: video summarization by visual co-occurrence. In: 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA, pp. 3584–3592 (2015)
Kingsford, C., Nagarajan, N.: Uncovering genomic reassortments among influenza strains by enumerating maximal bicliques. In: 2008 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pp. 223–230 (2008)
Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Inf. Process. Lett. 71, 199–204 (1999)
Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L.: Discovering frequent closed itemsets for association rules. In: ICDT 1999, January 1999
Pei, J., Han, J., Mao, R.: CLOSET: an efficient algorithm for mining frequent closed itemsets. In: DMKD 2000, May 2000
Wang, J., Han, J., Pei, J.: CLOSET + : searching for the best strategies for mining frequent closed itemsets. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2003)
Burdick, D., Calimlim, M., Gehrke, J.: MAFIA: a maximal frequent itemset algorithm for transactional databases. In: ICDE 2001, April 2001
Zaki, M., Hsiao, C.: CHARM: an efficient algorithm for closed itemset mining. In: SDM 2002, April 2002
Uno, T., Asai, T., Uchida, Y., et al.: An efficient algorithm for enumerating closed patterns in transaction databases. In: Lecture Notes in Computer Science, vol. 3245, pp. 16–31 (2004)
Uno, T., Kiyomi, M., Arimura, H.: LCM ver.2: efficient mining algorithms for frequent/closed/maximal itemsets. In: Proceedings of IEEE ICDM 2004 Workshop, FIMI 2004 (2004)
Uno, T., Kiyomi, M., Arimura, H.: LCM ver.3: collaboration of array, bitmap and prefix tree for frequent itemset mining. In: OSDM 2005, Proceedings of the 1st International Workshop on Open Source Data Mining, pp. 77–86 (2005)
Fan, Z.J., et al.: Efficient algorithm for extreme maximal biclique mining in cognitive frequency decision making. In: IEEE International Conference on Communication Software and Networks. IEEE, pp. 25–30 (2011)
Grahne, G., Zhu, J.: Fast algorithms for frequent itemset mining using FP-tree. IEEE Trans. Knowl. Data Eng. 17, 1347–1362 (2005)
Kloster, K., Sullivan, B.D., van der Poel, A.: Mining maximal induced bicliques using odd cycle transversals. In: Proceedings of the 2019 SIAM International Conference on Data Mining (2019)
Manku, G.S., Motwani, R.: Approximate frequency counts over data streams. In: Proceedings of the International Conference on Very Large Data Bases, pp. 346–357 (2002)
Li, H., Lee, S., Shan, M.: An efficient algorithm for mining frequent itemsets over the entire history of data streams. In: Proceedings of the International Workshop on Knowledge Discovery in Data Streams (2004)
Chi, Y., Wang, H., Yu, P.S., Muntz, R.R.: Catch the moment: maintaining closed frequent itemsets over a data stream sliding window. Knowl. Inf. Syst. 10(3), 265–294 (2006)
Li, H., Lu, Z., Chen, H.: Mining approximate closed frequent itemsets over stream. In: Proceedings of the International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, pp. 405–410 (2008)
Calders, T., Dexters, N., Goethals, B.: Mining frequent items in a stream using flexible windows. Intell. Data Anal. 12(3), 293–304 (2008)
Guo, L., Su, H., Qu, Y.: Approximate mining of global closed frequent itemsets over data streams. J. Frankl. Inst. 348(6), 1052–1081 (2011)
Das, A., Tirthapura, S.: A change-sensitive algorithm for maintaining maximal bicliques in a dynamic bipartite graph (2017)
Das, A., Tirthapura, S.: Incremental maintenance of maximal bicliques in a dynamic bipartite graph. IEEE Trans. Multi-Scale Comput. Syst. 4, 231–242 (2018)
Zhang, S., Liao, M., Xiao, Q., Hou, X., Lv, P.: An algorithm for maximal bicliques searching in dynamic relationship graph (2017)
Acknowledgment
The work is supported by both the National Scientific and Technological Innovation Zone (No. 17-H863-01-ZT-005-005-01) and State’s Key Project of Research and Development Plan (No. 2016QY03D0505). The contributions of the authors of this paper are as follows: Liao proposed this problem, Qin provided the basic code of the EMBS algorithm and Wang completed the theories, the simulation, and the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, R., Liao, M., Qin, C. (2020). An Efficient Algorithm for Enumerating Maximal Bicliques from a Dynamically Growing Graph. In: Liu, Y., Wang, L., Zhao, L., Yu, Z. (eds) Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery. ICNC-FSKD 2019. Advances in Intelligent Systems and Computing, vol 1075. Springer, Cham. https://doi.org/10.1007/978-3-030-32591-6_35
Download citation
DOI: https://doi.org/10.1007/978-3-030-32591-6_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-32590-9
Online ISBN: 978-3-030-32591-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)