Structural Entropy Analysis in Graphs via Minimum Spanning Forests: A Computational Approach

This paper presents a computational analysis of the structural entropy of graphs before and after the application of the Minimum Spanning Forest (MSF) algorithm. Using the NetworkX library in Python, graphs with multiple connected components and randomly weighted edges were generated, on which the structural entropy based on the vertex degree distribution was calculated. The results show that applying the MSF reduces the graph’s structural entropy from 2.5074 to 1.6815, while preserving the connectivity of the components and reducing the number of edges from 140 to 69. This reduction demonstrates that the MSF induces a more regular and predictable topological structure, with a less heterogeneous degree distribution. The study contributes to understanding the relationships between graph optimization and structural complexity measures, with potential applications in communication networks, bioinformatics, and data science.