基于独立集与匹配数的几乎完全网络熵的度量
A Measure of Almost Complete Network Entropy Based on Independent Sets and Matching
DOI: 10.12677/aam.2025.148374, PDF,    科研立项经费支持
作者: 邓 赫：青海民族大学数学与统计学院，青海 西宁
关键词: 图熵；几乎完全网络；独立集；匹配数；Graph Entropy； Almost Complete Networks； Independent Set； Matching
摘要: 为探究边稠密网络的结构复杂性，本文选取基于独立集与匹配数的图熵，在前人探究了完全网络删除至多1条边的基础上，我们延续了他们的工作，研究了完全网络删除至多5条边所得到的几乎完全网络的所有情况，并根据删边数量分类讨论找到了这两类图熵的极值，最后通过数值模拟的方法进行了验证。
Abstract: To explore the structural complexity of edge-dense networks, this paper selects graph entropy based on independent sets and matching numbers. Based on the previous research on deleting at most one edge from a complete network, we continue their work and study all situations of almost complete networks obtained by deleting at most five edges from a complete network. We also discuss and classify them according to the number of deleted edges and find the extreme values of these two types of graph entropy, which are finally verified through numerical simulation.
文章引用：邓赫. 基于独立集与匹配数的几乎完全网络熵的度量[J]. 应用数学进展, 2025, 14(8): 95-108. https://doi.org/10.12677/aam.2025.148374

参考文献

[1] Boltzmann, L. (1866) Ueber die mechanische bedeutung des zweiten Hauptsatzes der wärmetheorie: Sond.-Abdr. Wiss. Staatsdruckerei.
[2] Shannon, C.E. (1948) A Mathematical Theory of Communication. Bell System Technical Journal, 27, 379-423. [Google Scholar] [CrossRef] 
[3] Rashevsky, N. (1955) Life, Information Theory, and Topology. The Bulletin of Mathematical Biophysics, 17, 229-235. [Google Scholar] [CrossRef] 
[4] Mowshowitz, A. (1968) Entropy and the Complexity of Graphs: I. An Index of the Relative Complexity of a Graph. The Bulletin of Mathematical Biophysics, 30, 175-204. [Google Scholar] [CrossRef] [PubMed]
[5] Li, S., He, J. and Song, K. (2016) Network Entropies of the Chinese Financial Market. Entropy, 18, Article 331. [Google Scholar] [CrossRef] 
[6] Coutrot, A., Manley, E., Goodroe, S., Gahnstrom, C., Filomena, G., Yesiltepe, D., et al. (2022) Entropy of City Street Networks Linked to Future Spatial Navigation Ability. Nature, 604, 104-110. [Google Scholar] [CrossRef] [PubMed]
[7] Ruby, U. and Yendapalli, V. (2020) Binary Cross Entropy with Deep Learning Technique for Image Classification. International Journal of Advanced Trends in Computer Science and Engineering, 9, 5393-5397. [Google Scholar] [CrossRef] 
[8] Zhou, C., Ye, Z., Yao, C., Fan, X. and Xiong, F. (2024) Estimation of the Anisotropy of Hydraulic Conductivity through 3D Fracture Networks Using the Directional Geological Entropy. International Journal of Mining Science and Technology, 34, 137-148. [Google Scholar] [CrossRef] 
[9] Liu, T., Qi, S., Qiao, X. and Liu, S. (2024) A Hybrid Short-Term Wind Power Point-Interval Prediction Model Based on Combination of Improved Preprocessing Methods and Entropy Weighted GRU Quantile Regression Network. Energy, 288, Article 129904. [Google Scholar] [CrossRef] 
[10] Bonchev, D. and Rouvray, D.H. (2003) Complexity in Chemistry: Introduction and Fundamentals. Taylor & Francis.
[11] Bonchev, D.G. (1995) Kolmogorov’s Information, Shannon’s Entropy, and Topological Complexity of Molecules. Bulgarian Chemical Communications, 28, 567-582.
[12] Zenil, H., Kiani, N.A. and Tegnér, J. (2017) Low-Algorithmic-Complexity Entropy-Deceiving Graphs. Physical Review E, 96, Article 012308. [Google Scholar] [CrossRef] [PubMed]
[13] Morzy, M., Kajdanowicz, T. and Kazienko, P. (2017) On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy. Complexity, 2017, Article ID: 3250301. [Google Scholar] [CrossRef] 
[14] Cao, S., Dehmer, M. and Shi, Y. (2014) Extremality of Degree-Based Graph Entropies. Information Sciences, 278, 22-33. [Google Scholar] [CrossRef] 
[15] Bonchev, D. and Trinajstić, N. (1977) Information Theory, Distance Matrix, and Molecular Branching. The Journal of Chemical Physics, 67, 4517-4533. [Google Scholar] [CrossRef] 
[16] Braunstein, S.L., Ghosh, S. and Severini, S. (2006) The Laplacian of a Graph as a Density Matrix: A Basic Combinatorial Approach to Separability of Mixed States. Annals of Combinatorics, 10, 291-317. [Google Scholar] [CrossRef] 
[17] Estrada, E., de la Peña, J.A. and Hatano, N. (2014) Walk Entropies in Graphs. Linear Algebra and Its Applications, 443, 235-244. [Google Scholar] [CrossRef] 
[18] Dehmer, M. (2008) Information Processing in Complex Networks: Graph Entropy and Information Functionals. Applied Mathematics and Computation, 201, 82-94. [Google Scholar] [CrossRef] 
[19] Dehmer, M., Grabner, M. and Furtula, B. (2012) Structural Discrimination of Networks by Using Distance, Degree and Eigenvalue-Based Measures. PLOS ONE, 7, e38564. [Google Scholar] [CrossRef] [PubMed]
[20] Kraus, V., Dehmer, M. and Emmert-Streib, F. (2014) Probabilistic Inequalities for Evaluating Structural Network Measures. Information Sciences, 288, 220-245. [Google Scholar] [CrossRef] 
[21] Dehmer, M. and Mowshowitz, A. (2011) A History of Graph Entropy Measures. Information Sciences, 181, 57-78. [Google Scholar] [CrossRef] 
[22] Chen, Z., Dehmer, M., Emmert-Streib, F. and Shi, Y. (2015) Entropy of Weighted Graphs with Randi’c Weights. Entropy, 17, 3710-3723. [Google Scholar] [CrossRef] 
[23] Chen, Z., Dehmer, M. and Shi, Y. (2014) A Note on Distance-Based Graph Entropies. Entropy, 16, 5416-5427. [Google Scholar] [CrossRef] 
[24] Ilić, A. and Dehmer, M. (2015) On the Distance Based Graph Entropies. Applied Mathematics and Computation, 269, 647-650. [Google Scholar] [CrossRef] 
[25] Merrifield, R. and Simmons, H. (1989) Topological Methods in Chemistry. Wiley.
[26] Wagner, S. and Gutman, I. (2010) Maxima and Minima of the Hosoya Index and the Merrifield-Simmons Index: A Survey of Results and Techniques. Acta Applicandae Mathematicae, 112, 323-346. [Google Scholar] [CrossRef] 
[27] Cao, S., Dehmer, M. and Kang, Z. (2017) Network Entropies Based on Independent Sets and Matchings. Applied Mathematics and Computation, 307, 265-270. [Google Scholar] [CrossRef] 
[28] Zhang, H., Wu, T. and Lai, H. (2014) Per-Spectral Characterizations of Some Edge-Deleted Subgraphs of a Complete Graph. Linear and Multilinear Algebra, 63, 397-410. [Google Scholar] [CrossRef] 
[29] Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S. and Emmert-Streib, F. (2020) On Graph Entropy Measures Based on the Number of Independent Sets and Matchings. Information Sciences, 516, 491-504. [Google Scholar] [CrossRef] 

为你推荐