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 problem of data reliability in complex networks. In particular, we are able to reliably identify both missing and spurious interactions in noisy network observations. Remarkably, our approach also enables us to obtain, from those noisy observations, network reconstructions that yield estimates of the true network properties that are more accurate than those provided by the observations themselves. Our approach has the potential to guide experiments, to better characterize network data sets, and to drive new discoveries. complex networks | data reliability | network reconstruction | block model | missing and spurious interactions Abbreviations: BM, stochastic block model; HRG, hierarchical random graph T he structure of the network of interactions between the units of a system affects the system's dynamics, and conveys information about the functional needs of the system, its evolution, and the role of individual units. For these reasons, network analysis has become a cornerstone of fields as diverse as systems biology and sociology [1]. Unfortunately, the reliability of network data is often a source of concern. In systems biology, high-throughput technologies hold the promise to uncover the intricate processes within the cell, but are also reportedly inaccurate. Protein interaction data provide, arguably, the most blatant example of data inaccuracy: in 2002, a systematic comparison of several high-throughput methods to a reference high-quality data set showed that these methods have accuracies below 20% [2]. Additionally, different methods result in networks that have different topological properties [3], and the coverage of real interactomes is very limited: 80% of the interactome of yeast [3] and 99.7% of the human interactome [4, 5] are still unknown. In the social sciences, missing data due to individual nonresponse and dropout [6], informant inaccuracy [7] , and sampling biases [8] are also pervasive. Simulation studies have established that these inaccuracies can lead to fundamentally wrong estimates of network properties and to misleading conclusions [8] , which is particularly worrisome at a time when social network analysis is being used for finding new friends and partners, singling out key individuals in organizations, and identifying criminal activity. Despite these concerns, the issue of network reliability has only been addressed in a field-by-field basis (for example, to deal with protein-protein interactions [9, 10] or to take into account informant inaccuracy in social networks [7] ), and in studies that only address parts of the problem (for example, to detect missing interactions [11] ). Therefore, a general framework to deal with the problem of data reliability in complex networks is lacking. Here, we develop such a framework. Specifically, we show that within our framework we can reliably: (i) identify false negatives (missing interactions) and false positives (spurious interactions), and (ii) generate, from a single observed network, a reconstructed network whose properties (clustering coefficient, modularity, assortativity, epidemic spreading threshold, and synchronizability, among others) are closer to the "true" underlying network than those of the observed network itself. We show that our approach outperforms previous attempts to predict missing and spurious interactions, and illustrate the potential of our method by applying it to a protein interaction network of yeast [12] . We end by discussing how our approach will help to guide experiments and new discoveries, and to better characterize important data sets. Consider an observed network with adjacency matrix A O ; A O ij = 1 if nodes i and j are connected and 0 otherwise. We assume that this observed network is a realization of an underlying probabilistic model, either because the network itself is the result of a stochastic process, because the measurement has uncertainty, or both [7] 1 . Let us call M the set of generative models that could conceivably give rise to the observed network, and p(M |A O ) the probability that M ∈ M is the model that gave rise to the observation A O . If we could get a new observation of the network, the outcome would in general be different from A O ; our best estimate for the probability p(X = x) for an arbitrary network property X is where p(X = x|M ) is the probability that X = x in a network generated with model M . Using Bayes theorem, we can rewrite Eq. (1) as where p(A O |M ) is the probability that model M gives rise to A O among all possible adjacency matrices, and p(M ) is the a priori probability that model M is the correct one. We call p(X = x|A O ) the reliability of the X = x measurement. Given the generality of these arguments, the key to good estimates of reliability is to identify sets of models that are general, empirically Reserved for Publication Footnotes
In the generalist class we have methods that reduce the dimensionality of the edge set to let the underlying structure of the network emerge REF .
Missing and spurious interactions and the reconstruction of complex networks
Proc. Natl. Acad. Sci. U. S. A. 106, 22073-22078 (2009)
Computer Science Physics Biology Medicine