Irregularity-Based Entropy Inequalities Determining Complete Interconnection Network Complexity

Articles in Press

Document Type : Original paper

Authors

1 Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, 60000, Pakistan

2 Department of Mathematics, COMSATS University Islamabad, Vehari Campus, Vehari, 61100, Pakistan

3 Department of Mathematics and Statistics, Institute of Southern Punjab, Multan 60800, Pakistan

4 Department of Mathematics, COMSATS University Islamabad, Sahiwal Campus, Sahiwal, 57000, Pakistan

5 University of Northumbria

Abstract

In contemporary scientific research, network analysis theory contributes significantly to diverse systems, including forecasting cetane numbers, examining thermal transport phenomena, addressing sustainability in supply chains, monitoring postoperative health, shaping public policy through social networks, and investigating phase transitions in storage tanks. Various Interconnection networks (ICNs) are discriminated based on attributes such as bandwidth, latency, switch radix, and network topology. Entropy is pivotal in extracting meaningful information from these scientific models, thereby enhancing their efficiency. The butterfly and Benes networks and their derived networks are widely utilized in diverse systems, including IBM, NEC Cenju-3, MIT Transit Project, optical coupler internal structures, permutation routing, chip networks, and multiprocessor systems. To extract meaningful information, a few models to discriminate these networks on the basis of their entropy and complexity have been introduced in recent research. In this paper, we propose an entropy-determining model based on the irregularity of these ICNs, which is applied to obtain mathematical formulae for entropy determination, leading to complexity analysis of these ICNs. The analysis shows that we determine explicit inequalities through numeric data produced by these formulae, thus giving a complete characterization of this family of ICNs and answering the recently posed questions.

Keywords

Main Subjects

References

[1] H. Abdo, S. Brandt, and D. Dimitrov, The total irregularity of a graph, Discrete Mathematics and Theoretical Computer Science 16 (2014), no. 1, 201–206. https://doi.org/10.46298/dmtcs.1263
[2] M.O. Albertson, The irregularity of a graph, Ars Combin. 46 (1997), 219–225.
[3] V.E. Beneš, Some inequalities in the theory of telephone traffic, The Bell System Technical Journal 44 (1965), no. 9, 1941–1975. https://doi.org/10.1002/j.1538-7305.1965.tb03154.x
[4] S.A.U.H. Bokhary, Adnan, M.K. Siddiqui, and M. Cancan, On topological indices and QSPR analysis of drugs used for the treatment of breast cancer, Polycyclic Aromatic Compounds 42 (2022), no. 9, 6233–6253. https://doi.org/10.1080/10406638.2021.1977353
[5] Y. Burnier and A. Rothkopf, Bayesian approach to spectral function reconstruction for euclideanqquantum field theories, Phys. Rev. Lett. 111 (2013), no. 18, 182003. https://doi.org/10.1103/PhysRevLett.111.182003
[6] J. Cardoso, Complexity analysis of BPEL web processes, Software Process: Improvement and Practice 12 (2007), no. 1, 35–49. https://doi.org/10.1002/spip.302
[7] J. Cardoso, J. Mendling, G. Neumann, and H.A. Reijers, A discourse on complexity of process models, Business Process Management Workshops, vol. 4103, Springer, Berlin/Heidelberg, Germany, 2006, pp. 117–128.
[8] G.M. Constantine, Graph complexity and the Laplacian matrix in blocked experiments, Linear Multilinear Algebra 28 (1990), no. 1-2, 49–56. https://doi.org/10.1080/03081089008818029
[9] K.C. Das and S. Mondal, On neighborhood inverse sum indeg index of molecular graphs with chemical significance, Inf. Sci. 623 (2023), 112–131. https://doi.org/10.1016/j.ins.2022.12.016
[10] M. Dehmer, Information processing in complex networks: Graph entropy and information functionals, Appl. Math. Comput. 201 (2008), no. 1-2, 82–94. https://doi.org/10.1016/j.amc.2007.12.010
[11] M. Dehmer, F. Emmert-Streib, and Y. Shi, Quantitative Graph Theory: A new branch of graph theory and network science, Inf. Sci. 418-419 (2017), 575–580. https://doi.org/10.1016/j.ins.2017.08.009
[12] M. Dehmer and A. Mowshowitz, A history of graph entropy measures, Inf. Sci. 181 (2011), no. 1, 57–78. https://doi.org/10.1016/j.ins.2010.08.041
[13] N. Drepanou, A. Lymperis, E.N. Saridakis, and K. Yesmakhanova, Kaniadakis holographic dark energy and cosmology, Eur. Phys. J. C 82 (2022), no. 5, 449. https://doi.org/10.1140/epjc/s10052-022-10415-9
[14] M.U. Ghani, F. Sultan, E.S.M. Tag El Din, A.R. Khan, J.B. Liu, and M. Cancan, A paradigmatic approach to find the valency-based K-banhatti and redefined Zagreb entropy for niobium oxide and a metal–organic framework, Molecules 27
(2022), no. 20, 6975. https://doi.org/10.3390/molecules27206975
[15] J. Guo, J. Liu, X. Liu, and L. Li, Summarizing source code through heterogeneous feature fusion and extraction, Information Fusion 103 (2024), 102058. https://doi.org/10.1016/j.inffus.2023.102058
[16] I. Gutman, Topological indices and irregularity measures, J. Bull 8 (2018), 469–475.
[17] L. Han, F. Escolano, E.R. Hancock, and R.C. Wilson, Graph characterizations from von Neumann entropy, Pattern Recognition Letters 33 (2012), no. 15, 1958–1967. https://doi.org/10.1016/j.patrec.2012.03.016
[18] A. Hussain, M. Numan, N. Naz, S.I. Butt, A. Aslam, and A. Fahad, On topological indices for new classes of benes network, J. Math. 2021 (2021), no. 3, 1–7. https://doi.org/10.1155/2021/6690053
[19] M. Imran, S. Hayat, and M.Y.H. Malik, On topological indices of certain interconnection networks, Appl. Math. Comput. 244 (2014), 936–951. https://doi.org/10.1016/j.amc.2014.07.064
[20] S. Jiang, O.L. Landen, H.D. Whitley, S. Hamel, R. London, D.S. Clark, P. Sterne, S.B. Hansen, S.X. Hu, G.W. Collins, and Y. Ping, Thermal transport in warm dense matter revealed by refraction-enhanced x-ray radiography with a deepneural-network analysis, Commun. Phys. 6 (2023), 98. https://doi.org/10.1038/s42005-023-01190-4
[21] Y.H. Kao, M. Yang, N.S. Artan, and H.J. Chao, CNoC: high-radix clos network-on-chip, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30 (2011), no. 12, 1897–1910. https://doi.org/10.1109/TCAD.2011.2164538
[22] Y. Kim, J. Cho, N. Naser, S. Kumar, K. Jeong, R.L. McCormick, and S. Kim, Physics-informed graph neural networks for predicting cetane number with systematic data quality analysis, Proceedings of the Combustion Institute 39 (2023),
no. 4, 4969–4978. https://doi.org/10.1016/j.proci.2022.09.059
[23] E. Klavins, Communication complexity of multi-robot systems, Algorithmic Foundations of Robotics V, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 275–291.
[24] E. Kushilevitz, Communication complexity, Advances in Computers, vol. 44, Elsevier, 1997, pp. 331–360.
[25] A.M. Latva-Koivisto, Finding a complexity measure for business process models, 2001.
[26] K.N. Levitt, M.W. Green, and J. Goldberg, A study of the data commutation problems in a self-repairable multiprocessor, Proceedings of the April 30–May 2, 1968, spring joint computer conference, April 1968, pp. 515–527.
https://doi.org/10.1145/1468075.1468151
[27] L.J. Li, F. Ming, X.K. Song, L. Ye, and D. Wang, Quantumness and entropic uncertainty in curved space-time, Eur. Phys. J. C 82 (2022), no. 8, 726. https://doi.org/10.1140/epjc/s10052-022-10687-1
[28] X. Li and I. Gutman, Mathematical aspects of Randic-type molecular structure descriptors, Mathematical Chemistry Monographs No.1, University of Kragujevac, 2006.
[29] H. Liu, L. Xie, J. Liu, and L. Ding, Application of butterfly clos-network in network-on-chip, The Scientific World Journal 2014 (2014), no. 2, 102651. https://doi.org/10.1155/2014/102651
[30] J.B. Liu, Y. Bao, and W.T. Zheng, Analyses of some structural properties on a class of hierarchical scale-free networks, Fractals 30 (2022), no. 7, 1–11. https://doi.org/10.1142/S0218348X22501365
[31] J.B. Liu, Y.Q. Zheng, and X.B. Peng, The statistical analysis for Sombor indices in a random polygonal chain networks, Discrete Appl. Math. 338 (2023), 218–233. https://doi.org/10.1016/j.dam.2023.06.006
[32] X. Liu, J. Zhang, and Z. Pei, Machine learning for high-entropy alloys: Progress, challenges and opportunities, Progress in Materials Science 131 (2022), 101018. https://doi.org/10.1016/j.pmatsci.2022.101018
[33] X.C. Liu and Q.P. Gu, Multicasts on WDM all-optical butterfly networks, JISE J. Inf. Sci. Eng. 18 (2002), no. 6, 1049–1058. https://doi.org/10.6688/JISE.2002.18.6.5
[34] P. J. Lu, M. C. Lai, and J. S. Chang, A survey of high-performance interconnection networks in high-performance computer systems, Electronics 11 (2022), no. 9, 1369. https://doi.org/10.3390/electronics11091369
[35] G.G. Luciano and E.N. Saridakis, Baryon asymmetry from Barrow entropy: theoretical predictions and observational constraints, Eur. Phys. J. C 82 (2022), no. 6, 558. https://doi.org/10.1140/epjc/s10052-022-10530-7
[36] Y. Ma, M. Dehmer, U.M. Kunzi, S. Tripathi, M. Ghorbani, J. Tao, and F. Emmert-Streib, The usefulness of topological indices, Inf. Sci. 606 (2022), 143–151. https://doi.org/10.1016/j.ins.2022.05.038
[37] M. Maghsoudi, S. Shokouhyar, A. Ataei, S. Ahmadi, and S. Shokoohyar, Coauthorship network analysis of AI applications in sustainable supply chains: Key players and themes, Journal of Cleaner Production 422 (2023), 138472.
https://doi.org/10.1016/j.jclepro.2023.138472
[38] K.A. McLean, S.R. Knight, T.M. Diehl, C. Varghese, N. Ng, M.A. Potter, and E.M. Harrison, Readiness for implementation of novel digital health interventions for postoperative monitoring: a systematic review and clinical innovation network
analysis, The Lancet Digital Health 5 (2023), no. 5, e295–e315.
[39] M. Moschetti, P.A. Burr, E. Obbard, J.J. Kruzic, P. Hosemann, and B. Gludovatz, Design considerations for high entropy alloys in advanced nuclear applications, Journal of Nuclear Materials 567 (2022), 153814. https://doi.org/10.1016/j.jnucmat.2022.153814
[40] A. Mowshowitz, Entropy and the complexity of graphs: I. An index of the relative complexity of a graph, The Bulletin of Mathematical Biophysics 30 (1968), 175–204. https://doi.org/10.1007/BF02476948
[41] A. Mowshowitz and M. Dehmer, Entropy and the complexity of graphs revisited, Entropy 14 (2012), no. 3, 559–570.
https://doi.org/10.3390/e14030559
[42] D.L. Neel and M.E. Orrison, The linear complexity of a graph, Electron. J. Comb. 13 (2006), #R9. https://doi.org/10.37236/1035
[43] S. Prabhu, V. Manimozhi, M. Arulperumjothi, and S. KlavΕΎar, Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks, Appl. Math. Comput. 420 (2022), 126897.
https://doi.org/10.1016/j.amc.2021.126897
[44] M.P. Rahul and J. Clement, Topological characterization and entropy measures of large cavity cycloarene oligomers, Eur. Phys. J. Plus 137 (2022), no. 12, 1365. https://doi.org/10.1140/epjp/s13360-022-03506-9
[45] A. Rani, A. Fahad, I.F. Hussain, U. Ali, and M. Ashraf, A comparison between certain graph parameters of biswapped networks and their maximal twinpreserving subgraphs with applications in determining complexity, Meas. Sci.
Technol. 35 (2023), no. 1, 015603. https://doi.org/10.1088/1361-6501/acffe7
[46] E.N. Saridakis, K. Bamba, R. Myrzakulov, and F.K. Anagnostopoulos, Holographic dark energy through Tsallis entropy, J. Cosmol. Astropart. Phys. 2018 (2018), no. 12, 012. https://doi.org/10.1088/1475-7516/2018/12/012.
[47] K. Selvakumar, P. Gangaeswari, and G. Arunkumar, The Wiener index of the zero-divisor graph of a finite commutative ring with unity, Discrete Appl. Math. 311 (2022), 72–84. https://doi.org/10.1016/j.dam.2022.01.012
[48] Y. Shang, Bounding extremal degrees of edge-independent random graphs using relative entropy, Entropy 18 (2016), no. 2, 53. https://doi.org/10.3390/e18020053
[49] , Subgraph robustness of complex networks under attacks, IEEE Transactions on Systems, Man, and Cybernetics: Systems 49 (2019), no. 4, 821–832. https://doi.org/10.1109/TSMC.2017.2733545
[50] , Sombor index and degree-related properties of simplicial networks, Appl. Math. Comput. 419 (2022), 126881.
https://doi.org/10.1016/j.amc.2021.126881
[51] J. Shetty and J. Adibi, Discovering important nodes through graph entropy the case of Enron email database, Proceedings of the 3rd international workshop on Link discovery, August 2005, pp. 74–81. https://doi.org/10.1145/1134271.1134282
[52] R. Trobec, R. Vasiljevic, M. Tomaševic, V. Milutinovic, R. Beivide, and M. Valero, Interconnection networks in petascale computer systems: A survey, ACM Computing Surveys (CSUR) 49 (2016), no. 3, 1–24. https://doi.org/10.1145/2983387
[53] T.L. Veldhuizen, Software libraries and their reuse: Entropy, Kolmogorov complexity, and Zipf ’s law, arXiv preprint cs/0508023, 2005.
[54] S.S. Vempala, R. Wang, and D.P. Woodruff, The communication complexity of optimization, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2020,
pp. 1733–1752. https://doi.org/10.1137/1.9781611975994.106
[55] W. Wang, H. Arshad, A. Fahad, and I. Javaid, On some ev-degree and ve-degreedependent indices of Benes network and its derived classes, Comput. Model. Eng. Sci 135 (2023), no. 2, 1685–1699. https://doi.org/10.32604/cmes.2022.023563
[56] W. Wang, A. Fahad, M. Vladimir, N. Mujahid, and M. Abisado, Interconnection network analysis through ve-degree based information functional entropy and complexity, Eur. Phys. J. Plus 138 (2023), 1109. https://doi.org/10.1140/epjp/s13360-023-04725-4
[57] W. Wang, A. Nisar, A. Fahad, M.I. Qureshi, and A. Alameri, Modified Zagreb connection indices for Benes network and related classes, J. Math. 2022 (2022), no. 1, 1–8. https://doi.org/10.1155/2022/8547332
[58] T. Xiao, Z. Liu, L. Lu, H. Han, X. Huang, X. Song, X. Yang, and X. Meng, LSTM-BP neural network analysis on solid-liquid phase change in a multi-channel thermal storage tank, Eng. Anal. Bound. Elem. 146 (2023), 226–240.
https://doi.org/10.1016/j.enganabound.2022.10.014
[59] J. Xu, Topological Structure and Analysis of Interconnection Networks, vol. 7, Springer Science and Business Media, 2013.
[60] J. Yang, A. Fahad, M. Mukhtar, M. Anees, A. Shahzad, and Z. Iqbal, Complexity analysis of Benes network and its derived classes via information functional based entropies, Symmetry 15 (2023), no. 3, 761. https://doi.org/10.3390/sym15030761
[61] W. Yang, S. Pang, Y. Liu, Q. Wang, P.K. Liaw, and T. Zhang, Design and properties of novel Ti–Zr–Hf–Nb–Ta high-entropy alloys for biomedical applications, Intermetallics 141 (2022), 107421. https://doi.org/10.1016/j.intermet.2021.107421
[62] Y. Yang, B.B. Jin, X. Sun, X.D. Zhang, B. Li, K. Zhao, and H. Wang, Exact counting of subtrees with diameter no more than d in trees: A generating function approach, Info. Computation 307 (2025), 105353. https://doi.org/10.1016/j.ic.2025.105353
[63] J. Zhang, A. Fahad, M. Mukhtar, and A. Raza, Characterizing interconnection networks in terms of complexity via entropy measures, Symmetry 15 (2023), no. 10, 1868. https://doi.org/10.3390/sym15101868
[64] P. Zhang, W. Xu, H. Gao, K. Niu, X. Xu, X. Qin, C. Yuan, Z. Qin, H. Zhao, J. Wei, and F. Zhang, Toward wisdom-evolutionary and primitive-concise 6G: A new paradigm of semantic communication networks, Engineering 8 (2022), 60–
73. https://doi.org/10.1016/j.eng.2021.11.003
[65] W. Zhang, M. Zhang, L. Yuan, and F. Fan, Social network analysis and public policy: what’s new?, Journal of Asian Public Policy 16 (2023), no. 2, 115–145. https://doi.org/10.1080/17516234.2021.1996869
[66] X. Zhang, A. Razzaq, K. Ali, S. Tahir Raza Rizvi, and M.R. Farahani, A new approach to find eccentric indices of some graphs, J. Inf. Optim. Sci. 41 (2020), no. 4, 865–877. https://doi.org/10.1080/02522667.2020.1744304
[67] X. Zhao, H. Ali, B. Ali, M.A. Binyamin, J.B. Liu, and A. Raza, Statistics and calculation of entropy of dominating David derived networks, Complexity 2021 (2021), 1–15. https://doi.org/10.1155/2021/9952481
[68] X. Zhao, M.K. Siddiqui, S. Manzoor, S. Ahmad, M.H. Muhammad, and J.B. Liu, On computation and analysis of entropy measures for metal-insulator transition super lattice, IETE Journal of Research 70 (2024), no. 2, 1911–1922.
https://doi.org/10.1080/03772063.2023.2165175
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 20 June 2026

Files

Share

How to cite

Statistics