High Reconstructability of Degree-Heterogeneous Networks

Reconstructing complex networks from observed, often noisy data is a fundamental task crucial for understanding complex systems across various domains. Despite numerous methods proposed for network reconstruction, little attention has been given to the relationship between reconstructability and the intrinsic properties of hidden networks. Here, we present a mathematical proof that, for scale-free networks, the reconstruction accuracy increases as the exponent of the power-law degree distribution decreases. This suggests that degree heterogeneity contributes to higher reconstructability. We validate this conclusion in empirical networks, where nodal degrees may not strictly adhere to power laws. Our results demonstrate that the reconstruction accuracy of degree-heterogeneous networks is indeed significantly higher than that of their randomized counterparts.