Network reconstruction via density sampling

The structure of many financial networks is protected by privacy and has to be inferred from aggregate observables. Here we consider one of the most successful network reconstruction methods, producing random graphs with desired link density and where the observed constraints (related to the market size of each node) are replicated as averages over the graph ensemble, but not in individual realizations. We show that there is a minimum critical link density below which the met...

We propose a novel method for network inference from partially observed edges using a node-specific degree prior. The degree prior is derived from observed edges in the network to be inferred, and its hyper-parameters are determined by cross validation. Then we formulate network inference as a matrix completion problem regularized by our degree prior. Our theoretical analysis indicates that this prior favors a network following the learned degree distribution, and may lead to...

A major problem in the study of complex socioeconomic systems is represented by privacy issues$-$that can put severe limitations on the amount of accessible information, forcing to build models on the basis of incomplete knowledge. In this paper we investigate a novel method to reconstruct global topological properties of a complex network starting from limited information. This method uses the knowledge of an intrinsic property of the nodes (indicated as fitness), and the nu...

The need to produce accurate estimates of vertex degree in a large network, based on observation of a subnetwork, arises in a number of practical settings. We study a formalized version of this problem, wherein the goal is, given a randomly sampled subnetwork from a large parent network, to estimate the actual degree of the sampled nodes. Depending on the sampling scheme, trivial method of moments estimators (MMEs) can be used. However, the MME is not expected, in general, to...

Network analysis is currently used in a myriad of contexts: from identifying potential drug targets to predicting the spread of epidemics and designing vaccination strategies, and from finding friends to uncovering criminal activity. Despite the promise of the network approach, the reliability of network data is a source of great concern in all fields where complex networks are studied. Here, we present a general mathematical and computational framework to deal with the probl...

When a network is reconstructed from data, two types of errors can occur: false positive and false negative errors about the presence or absence of links. In this paper, the vertex degree distribution of the true underlying network is analytically reconstructed using an iterative procedure. Such procedure is based on the inferred network and estimates for the probabilities $\alpha$ and $\beta$ of type I and type II errors, respectively. The iteration procedure consists of cho...

The amount of large-scale real data around us increase in size very quickly and so does the necessity to reduce its size by obtaining a representative sample. Such sample allows us to use a great variety of analytical methods, whose direct application on original data would be infeasible. There are many methods used for different purposes and with different results. In this paper we outline a simple and straightforward approach based on analyzing the nearest neighbors (NN) th...

We develop a new sampling method to estimate eigenvector centrality on incomplete networks. Our goal is to estimate this global centrality measure having at disposal a limited amount of data. This is the case in many real-world scenarios where data collection is expensive, the network is too big for data storage capacity or only partial information is available. The sampling algorithm is theoretically grounded by results derived from spectral approximation theory. We studied ...

We use mathematical methods from the theory of tailored random graphs to study systematically the effects of sampling on topological features of large biological signalling networks. Our aim in doing so is to increase our quantitative understanding of the relation between true biological networks and the imperfect and often biased samples of these networks that are reported in public data repositories and used by biomedical scientists. We derive exact explicit formulae for de...

In this paper we estimate the propagation of liquidity shocks through interbank markets when the information about the underlying credit network is incomplete. We show that techniques such as Maximum Entropy currently used to reconstruct credit networks severely underestimate the risk of contagion by assuming a trivial (fully connected) topology, a type of network structure which can be very different from the one empirically observed. We propose an efficient message-passing ...