Estimating network structure from unreliable measurements

Most empirical studies of networks assume that the network data we are given represent a complete and accurate picture of the nodes and edges in the system of interest, but in real-world situations this is rarely the case. More often the data only specify the network structure imperfectly: Like data in essentially every other area of empirical science, network data are prone to measurement error and noise. At the same time, the data may be richer than simple network measurements, incorporating multiple measurements, weights, lengths, or strengths of edges, node or edge labels, or annotations of various kinds. Here we develop a general method for making estimates of network structure and properties using any form of network data, simple or complex, when the data are unreliable, and give example applications to a selection of social and biological networks.

Figure 1

Two examples of inferred networks of connections between a subset of the participants in the “reality mining” study of Eagle and Pentland [75, 76]. (a) Network inferred using the Poisson random graph for the network model and the independent edge model of Sec. 4a for the data model. Edges with probability less than 0.01 are omitted, as are nodes that have no edges with probability 0.01 or greater. (b) Network inferred from the same data, but using the configuration model as the network model. For ease of comparison, the same set of nodes is shown in (b) as in (a), with each in the same spatial position.

Figure 2

Inferred values of the true-positive and false-discovery rates for each of the nine types of evidence considered in our analysis of the Messel Shale food web data set of Dunne et al. [77]. A high true-positive rate indicates a type of evidence that is frequently observed when there truly is a link in the network; a high false-discovery rate indicates that many observations of links using this type of evidence are in error.

Figure 3

Inferred network of friendships among the students in a medium-sized American high school and its feeder middle school. Edge thicknesses represent the inferred posterior probabilities of the edges. Node sizes represent the inferred values of the degree parameters ${\varphi }_i$ for the configuration model. Shading of the nodes represents the estimated average precision of reports made by the corresponding individual, precision being the probability that a reported friendship actually exists. Lightest shades correspond to the lowest precision and darkest shades to the highest. Only edges that are reported to exist by at least one participant are shown, and nodes with no reported edges are omitted.