Kronecker product decomposition of Boolean matrix with application to topological structure analysis of Boolean networks

Xiaomeng Wei; Haitao Li; Guodong Zhao; Xiaomeng Wei; Haitao Li; Guodong Zhao

doi:10.3934/mmc.2023025

Mathematical Modelling and Control

2023, Volume 3, Issue 4: 306-315. doi: 10.3934/mmc.2023025

Previous Article Next Article

Research article Special Issues

Kronecker product decomposition of Boolean matrix with application to topological structure analysis of Boolean networks

School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, China

Received: 30 December 2022 Revised: 01 April 2023 Accepted: 25 April 2023 Published: 11 December 2023

This paper investigated the Kronecker product (KP) decomposition of the Boolean matrix and analyzed the topological structure of Kronecker product Boolean networks (KPBNs). First, the support matrix set of the Boolean matrix consisting of support matrices was defined. Second, a verifiable condition was presented for the KP decomposition of the Boolean matrix based on the support matrices. Third, the equivalence of KP decomposition between the Boolean matrix and support matrix set was established. Finally, the KP decomposition of Boolean matrix was used to analyze the topological structure of KPBNs. It was shown that the topological structure of KPBNs can be determined by that of the factor of Boolean networks (BNs).
- KP decomposition,
- Boolean matrix,
- BNs,
- topological structure
Citation: Xiaomeng Wei, Haitao Li, Guodong Zhao. Kronecker product decomposition of Boolean matrix with application to topological structure analysis of Boolean networks[J]. Mathematical Modelling and Control, 2023, 3(4): 306-315. doi: 10.3934/mmc.2023025

Related Papers:

Abstract

This paper investigated the Kronecker product (KP) decomposition of the Boolean matrix and analyzed the topological structure of Kronecker product Boolean networks (KPBNs). First, the support matrix set of the Boolean matrix consisting of support matrices was defined. Second, a verifiable condition was presented for the KP decomposition of the Boolean matrix based on the support matrices. Third, the equivalence of KP decomposition between the Boolean matrix and support matrix set was established. Finally, the KP decomposition of Boolean matrix was used to analyze the topological structure of KPBNs. It was shown that the topological structure of KPBNs can be determined by that of the factor of Boolean networks (BNs).

References

[1]	D. D. Lee, H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), 788–791. https://doi.org/10.1038/44565 doi: 10.1038/44565
[2]	C. J. Lin, On the convergence of multiplicative update algorithm for non-negative matrix factorization, IEEE Trans. Neural Networks, 18 (2007), 1589–1596. https://doi.org/10.1109/TNN.2007.895831 doi: 10.1109/TNN.2007.895831
[3]	D. Guillamet, J. Vitri, B. Schiele, Introducing a wighted non-negative matrix factorization for image classification, Pattern Recogni. Lett., 24 (2003), 2447–2454. https://doi.org/10.1016/S0167-8655(03)00089-8 doi: 10.1016/S0167-8655(03)00089-8
[4]	O. Zoidi, A. Tefas, I. Pitas, Multiplicative update rules for concurrent nonnegative matrix factorization and maximum margin classfication, IEEE Trans. Neural Networks Learn. Syst., 24 (2013), 422–434. https://doi.org/10.1109/TNNLS.2012.2235461 doi: 10.1109/TNNLS.2012.2235461
[5]	H. Che, J. Wang, A nonnegative matrix factorization algorithm based on a discrete-time projection neural network, Neural Networks, 103 (2018), 63–71. https://doi.org/10.1016/j.neunet.2018.03.003 doi: 10.1016/j.neunet.2018.03.003
[6]	V. Snasel, J. Kromer, J. Platos, D. Husek, On the implementation of Boolean matrix factorization, Procedings of the 19th International Workshop on Database and Expert Systems Applications, 2008,554–558. https://doi.org/10.1109/DEXA.2008.92 doi: 10.1109/DEXA.2008.92
[7]	J. Vaidya, Boolean matrix decomposition problem: Theory, variations and applications to data engineering, Proceedings of IEEE 28th International Conference on Data Engineering, 2012, 1222–1224. https://doi.org/10.1109/ICDE.2012.144 doi: 10.1109/ICDE.2012.144
[8]	X. Li, J. Wang, S. Kwong, Boolean matrix factorization based on collaborative neurodynamic optimization with Boltzmann machines, Neural Networks, 153 (2022), 142–151. https://doi.org/10.1016/j.neunet.2022.06.006 doi: 10.1016/j.neunet.2022.06.006
[9]	T. Martin, T. Marketa, Boolean matrix factorization with background knowledge, Knowl. Based Syst., 241 (2022), 108261. https://doi.org/10.1016/j.knosys.2022.108261 doi: 10.1016/j.knosys.2022.108261
[10]	Z. Zhang, T. Li, C. Ding, X. Ren, X. Zhang, Binary matrix factorization for analyzing gene expression data, Data Min. Knoewl. Disc., 20 (2010), 28–52. https://doi.org/10.1007/s10618-009-0145-2 doi: 10.1007/s10618-009-0145-2
[11]	H. Li, Y. Wang, Logical matrix factorization with application to topological structure analysis of Boolean networks, IEEE Trans. Autom. Control, 60 (2015), 1380–1385. https://doi.org/10.1109/TAC.2014.2348216 doi: 10.1109/TAC.2014.2348216
[12]	P. K. Jha, Kronecke product of paths and cycles: decomposition, factorization and bi-pancyclicity, Discrete Math., 182 (1998), 153–167. https://doi.org/10.1016/S0012-365X(97)00138-6 doi: 10.1016/S0012-365X(97)00138-6
[13]	P. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc., 113 (1962), 47–52. https://doi.org/10.1090/S0002-9939-1962-0133816-6 doi: 10.1090/S0002-9939-1962-0133816-6
[14]	R. Hammack, E. Imrich, S. Klavzar, Handbook of product graphs, Boca Raton: CRC Press, 2011.
[15]	F. Pasqualetri, D. Borra, F. Bullo, Consensus networks over finite fields, Automatica, 50 (2014), 349–358. https://doi.org/10.1016/j.automatica.2013.11.011 doi: 10.1016/j.automatica.2013.11.011
[16]	X. Zhu, H. Liu, Y. Liang, J. Wu, Image encryption based on Kronecker product over finite fields and DNA operation, Optik, 224 (2020), 164725. https://doi.org/10.1016/j.ijleo.2020.164725 doi: 10.1016/j.ijleo.2020.164725
[17]	J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, Kronecker graphs: an approach to modeling networks, J. Mach. Learn. Res., 11 (2010), 985–1042. https://doi.org/10.1145/1756006.1756039 doi: 10.1145/1756006.1756039
[18]	Y. Hao, Q. Wang, Z. Duan, G. Chen, Controllability of kronecker product networks, Automatica, 110 (2019), 108597. https://doi.org/10.1016/j.automatica.2019.108597 doi: 10.1016/j.automatica.2019.108597
[19]	C. F. V. Loan, N. Pitsianis, Approximation with Kronecker products, Netherlands: Springer, 1993.
[20]	K. K. Wu, H. Yam, H. Meng, M. Mesbahi, Kronecker product approximation with multiple factor matrices via the tensor product algorithm, Proceedings of 2016 IEEE International Conference on Systems, Man, and Cybernetics, 2016, 4277–4282. https://doi.org/10.1109/SMC.2016.7844903 doi: 10.1109/SMC.2016.7844903
[21]	X. Li, H. Li, S. Wang, Tensor product decomposition of large-size logical matrix, Proceedings of 37th Chinese Control Conference, 2018, 1077–1081. https://doi.org/10.23919/CHICC.2018.8483707 doi: 10.23919/CHICC.2018.8483707
[22]	D. Cheng, Y. Li, J. Feng, J. Zhao, On numerical/non-numerical algebra: semi-tensor product method, Math. Modell. Control, 1 (2021), 1–11. https://doi.org/10.3934/mmc.2021001 doi: 10.3934/mmc.2021001
[23]	D. Cheng, H. Qi, A linear representation of dynamics of Boolean networks, IEEE Trans. Autom. Control, 55 (2010), 2251–2258. https://doi.org/10.1109/TAC.2010.2043294 doi: 10.1109/TAC.2010.2043294
[24]	D. Cheng, H. Qi, Z. Li, Analysis and control of Boolean networks: a semi-tensor product approach, London: Springer, 2011.
[25]	Y. Liu, B. Li, H. Chen, J. Cao, Function perturbations on singular Boolean networks, Automatica, 84 (2017), 36–42. https://doi.org/10.1016/j.automatica.2017.06.035 doi: 10.1016/j.automatica.2017.06.035
[26]	J. Lu, R. Liu, J. Lou, Y. Liu, Pinning stabilization of Boolean control networks via a minimum number of controllers, IEEE Trans. Cybern., 51 (2021), 373–381. https://doi.org/10.1109/TCYB.2019.2944659 doi: 10.1109/TCYB.2019.2944659
[27]	Y. Wu, X. Sun, X. Zhao, T. Shen, Optimal control of Boolean control networks with average cost: a policy iteration approach, Automatica, 100 (2019), 378–387. https://doi.org/10.1016/j.automatica.2018.11.036 doi: 10.1016/j.automatica.2018.11.036
[28]	Q. Zhang, J. Feng, B. Wang, P. Wang, Event-triggered mechanism of designing set stabilization state feedback controller for switched Boolean networks, Appl. Math. Comput., 383 (2020), 125372. https://doi.org/10.1016/j.amc.2020.125372 doi: 10.1016/j.amc.2020.125372
[29]	Y. Zhao, Y. Liu, Output controllability and observability of mix-valued logic control networks, Math. Modell. Control, 1 (2021), 145–156. https://doi.org/10.3934/mmc.2021013 doi: 10.3934/mmc.2021013
[30]	S. Zhu, J. Lu, S. Azuma, W. X. Zheng, Strong structural controllability of Boolean networks: polynomial-time criteria, minimal node control, and distributed pinning strategies, IEEE Trans. Automa. Control, 68 (2022), 5461–5476. https://doi.org/10.1109/TAC.2022.3226701 doi: 10.1109/TAC.2022.3226701
[31]	S. Zhu, J. Lu, L. Sun, J. Cao, Distributed pinning set stabilization of large-scale Boolean networks, IEEE Trans. Automa. Control, 68 (2023), 1886–1893. https://doi.org/10.1109/TAC.2022.3169178 doi: 10.1109/TAC.2022.3169178
[32]	L. Lin, J. Cao, S. Zhu, P. Shi, Synchronization analysis for stochastic networks through finite fields, IEEE Trans. Autom. Control, 67 (2022), 1016–1022. https://doi.org/10.1109/TAC.2021.3081621 doi: 10.1109/TAC.2021.3081621
[33]	M. Meng, X. Li, G. Xiao, Synchronization of networks over finite fields, Automatica, 115 (2020), 108877. https://doi.org/10.1016/j.automatica.2020.108877 doi: 10.1016/j.automatica.2020.108877
[34]	K. H. Kim, Boolean matrix theory and applications, New York: Marcel Dekker, 1982.
[35]	R. A. Horn, C. R. Johnson, Matrix analysis, Cambridge: Cambradge University Press, 1986.

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)