Network reconstruction via density sampling

Reconstructing weighted networks from partial information is necessary in many important circumstances,e.g. for a correct estimation of systemic risk. It has been shown that, in order toachieve an accurate reconstruction, it is crucial to reliably replicate the empirical degree sequence,which is however unknown in many realistic situations. More recently, it has been found that theknowledge of the degree sequence can be replaced by the knowledge of the strength sequence, whichis typically accessible, complemented by that of the total number of links, thus considerably relaxingthe observational requirements. Here we further relax these requirements and devise a procedurevalid when even the the total number of links is unavailable. We assume that, apart from the heterogeneityinduced by the degree sequence itself, the network is homogeneous, so that its (global)link density can be estimated by sampling subsets of nodes with representative density. We showthat the best way of sampling nodes is the random selection scheme, any other procedure beingbiased towards unrealistically large, or small, link densities. We then introduce our core techniquefor reconstructing both the topology and the link weights of the unknown network in detail. Whentested on real economic and financial data sets, our method achieves a remarkable accuracy and isvery robust with respect to the sampled subsets, thus representing a reliable practical tool wheneverthe available topological information is restricted to small portions of nodes.