Source-linked AI summary
Network structure from rich but noisy data
M. E. J. Newman
TL;DR
Network measurements can be richly multimodal yet unreliable, so raw observations may not represent the true network structure. The paper uses probabilistic modeling and EM to estimate ground-truth networks and measurement reliability, yielding posterior structures that account for uncertainty. The framework is demonstrated on proximity and self-reported friendship data and extends to other data models.
Problem
Network data may combine rich, multimodal measurements with substantial error and missingness, making naive network estimates differ from the underlying structure.
Method
A probabilistic data model and expectation–maximization algorithm estimate model parameters, posterior edge probabilities, and distributions over ground-truth networks.
Results
The method produces fitted ground-truth network estimates and posterior uncertainty while supporting both repeated edge observations and observer-specific friendship reports.
Takeaways & Limitations
The inference framework can be applied to many networks and extended to additional data models beyond the two demonstrated applications.
Abstract
from arXiv · showhide
Driven by growing interest in the sciences, industry, and among the broader public, a large number of empirical studies have been conducted in recent years of the structure of networks ranging from the internet and the world wide web to biological networks and social networks. The data produced by these experiments are often rich and multimodal, yet at the same time they may contain substantial measurement error. In practice, this means that the true network structure can differ greatly from naive estimates made from the raw data, and hence that conclusions drawn from those naive estimates may be significantly in error. In this paper we describe a technique that circumvents this problem and allows us to make optimal estimates of the true structure of networks in the presence of both richly textured data and significant measurement uncertainty. We give example applications to two different social networks, one derived from face-to-face interactions and one from self-reported friendships.
Methods
The methods infer ground-truth network structure by combining a probabilistic data model with EM estimation of unknown parameters and posterior edge probabilities. The framework accommodates missing observations and heterogeneous reporting reliability.
- Independent edge model: For independently repeated edge measurements, the method uses the numbers of measurements Nij and observed edges Eij to estimate common true-positive and false-positive rates.When all node pairs have the same number of observations, the general updates reduce to the reality-mining equations.
- Network inference: The model assigns a prior probability to each edge and estimates posterior edge probabilities Qij from observed data and parameters.Missing data correctly leave Qij equal to the prior edge probability ρ.
- Heterogeneous observers: For unilateral friendship reports, the method gives each participant individual true-positive and false-positive rates, allowing reliability to vary across observers.The resulting posterior probabilities incorporate reports from both directions of an undirected ground-truth edge.
A. Additional results for the reality mining network
Additional analyses assess model fit and reproducibility for the reality-mining network. The fitted model matches the distribution of proximity observations reasonably well, while independent weekday data show expected variation between inferred networks.
- Model fit: The model treats the number of proximity observations as sufficient for fitting, not the specific days on which those observations occurred.This follows from the assumption that observations are independent.
- Model fit: The best-fit model closely reproduces the histogram of node pairs by the number of days they were observed in proximity.Most pairs have zero observations because the network is sparse, with some deviation between data and fit on close inspection.
- Reproducibility: Wednesday and Thursday observations provide independent data sets for comparing the reconstructed reality-mining network.The two figures use the same nodes and positions to make structural differences easier to inspect.
- Reproducibility: Some variation between networks inferred from different measurements is expected, and the model’s true- and false-positive rates estimate the size of measurement errors.Exact agreement is not expected when the underlying data are error-prone.
B. Additional results for the AddHealth network
The AddHealth analysis models friendship reports as directed observations of an undirected ground-truth network, while allowing each reporter to have distinct reliability. EM inference then combines these asymmetric reports into edge and observer estimates.
- Observation model: Each reported friendship is treated as a directed observation, although the underlying ground-truth friendship network is undirected.Eij records how often node i identifies node j as a friend.
- Observer reliability: The model assigns each participant individual true-positive and false-positive rates to represent differences in reporting reliability.Observations from both directions are included separately in the likelihood.
- Inference: The likelihood combines reported edges and non-edges from both participants before estimating the model parameters.The formulation explicitly includes separate terms for Eij and Eji and their corresponding observation totals.
- Inference: The EM algorithm can infer both posterior edge probabilities and node-specific trustworthiness from patterns of agreement and disagreement in reports.The resulting Qij depends on the estimated reliability of the two reporters, not only on whether they both report an edge.
C. Other data models
The inference framework supports richer network data models beyond the two examples, including multimodal measurements and edges with multiple strengths. Different modes can have different accuracies, while edge-strength levels remain unordered unless reordered afterward.
- Extensions: The framework can incorporate other data models, including multimodal observations and networks with weighted or multiple-strength edges.The specific model depends on the available data and the research question.
- Edge strengths or weights: Multiple-strength networks can represent each edge with several categorical levels and corresponding prior and observation parameters.The approach extends to any number of levels, with model selection potentially used to choose how many levels to include.
- Edge strengths or weights: Edge-strength levels are mathematically unordered, so EM may return equivalent parameterizations with permuted labels.Manual permutation may be needed if higher labels are intended to denote stronger edges.
- Multimodal data: For multimodal data, measurements are conditionally independent across modes and nodes, with mode-specific true-positive and false-positive rates.The model allows each mode m to have its own αm and βm.
- Multimodal data: Reliable modes receive greater inferential weight because observed edges increase, and non-edges decrease, the edge odds more strongly when αm is high and βm is low.This weighting follows directly from the odds-ratio formulation.
D. Computation of network properties
The paper computes network-property estimates from the posterior distribution over possible ground-truth networks. Closed-form calculations apply in some cases, while Monte Carlo sampling handles nonlocal properties and dependent-edge models.
- The posterior distribution q(A) enables expected values and distributions for network properties such as degree, clustering, correlations, and spectral measures.
- For approximately normal quantities, the supplied expressions provide expectations and variances; otherwise, the complete distribution of X can be computed.
- Expected degree can be calculated directly when the model provides an explicit marginal edge probability Qij.
- For nonlocal quantities such as correlation functions or eigenvalues, Monte Carlo sampling estimates expectations, variances, or complete distributions from networks drawn from q(A).Each sampled network is evaluated, and the resulting values are used to calculate the desired statistics.
- When posterior edges are independent, networks are sampled by generating each edge independently with probability Qij; dependent edges require Markov chain importance sampling.The latter repeatedly proposes small network changes, such as adding or removing one edge, and accepts them according to the posterior ratio.