Maximum Entropy Methods for Reconstructing Complex Network Topologies

Abstract

econstructing the topology of a complex network from partial or aggregate information, such as node-level degree
sequences alone, without access to the full edge list, is a common inference problem in economics, ecology, and
systems biology, and maximum entropy methods provide a principled statistical framework for this task, but their
reconstruction accuracy across differing network structures and levels of missing information has not been
systematically benchmarked. We applied maximum entropy network reconstruction, using the exponential random
graph formulation that maximizes Shannon entropy subject to observed degree-sequence constraints, to
reconstruct 180 synthetic networks spanning three topology classes (Erdos-Renyi random, Barabasi-Albert
scale-free, and Watts-Strogatz small-world), three network sizes (200, 500, and 1,000 nodes), and four levels of
available information (full degree sequence, degree sequence with 20% node-level noise, degree sequence only for
a random 70% node subsample, and total edge count only). Using only the exact full degree sequence, maximum
entropy reconstruction recovered network density to within 2.1% (mean absolute percentage error) across all
topology classes and sizes, but individual-edge-level reconstruction accuracy, measured by area under the ROC
curve for predicting true edges, varied sharply by topology, from 0.91 for Erdos-Renyi networks to 0.68 for
Barabasi-Albert scale-free networks, a 0.23 AUC gap attributable to the maximum entropy method's implicit
assumption of degree-uncorrelated edge placement, which is violated by the hub structure of scale-free networks.
Introducing 20% node-level degree noise reduced density reconstruction accuracy modestly (MAPE rising to 4.8%)
but degraded edge-level AUC more severely, by 0.09-0.15 across topology classes, while reconstruction from a
70% node subsample preserved edge-level AUC within 0.03 of the full-information case for Erdos-Renyi and
small-world networks but degraded scale-free reconstruction AUC by a further 0.11, compounding its already-lower
baseline accuracy. Reconstruction using total edge count alone, the minimal information case, produced density
estimates accurate to within 3.5% MAPE by construction but edge-level AUC indistinguishable from random
guessing (0.50-0.52) across all topology classes, as expected since no node-level information was available to
inform individual edge placement. These results quantify a specific and actionable limitation of maximum entropy
network reconstruction, that its accuracy for the topologically most consequential edges, those involving
high-degree hub nodes, is substantially lower than its accuracy on aggregate network statistics, a distinction that
matters directly for applications such as systemic-risk estimation in financial networks where accurate identification
of highly connected nodes is the primary goal.