Reconstructing networks with unknown and heterogeneous errors

Abstract

The vast majority of network datasets contains errors and omissions, although this is rarely incorporated in traditional network analysis. Recently, an increasing effort has been made to fill this methodological gap by developing network reconstruction approaches based on Bayesian inference. These approaches, however, rely on assumptions of uniform error rates and on direct estimations of the existence of each edge via repeated measurements, something that is currently unavailable for the majority of network data. Here we develop a Bayesian reconstruction approach that lifts these limitations by not only allowing for heterogeneous errors, but also for single edge measurements without direct error estimates. Our approach works by coupling the inference approach with structured generative network models, which enable the correlations between edges to be used as reliable uncertainty estimates. Although our approach is general, we focus on the stochastic block model as the basic generative process, from which efficient nonparametric inference can be performed, and yields a principled method to infer hierarchical community structure from noisy data. We demonstrate the efficacy of our approach with a variety of empirical and artificial networks.

27 pages, 17 figures

References in corpus (11)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Missing and spurious interactions and the reconstruction of complex networks
• Phase transition in the detection of modules in sparse networks
• Parsimonious module inference in large networks
• Learning Latent Block Structure in Weighted Networks
• Network structure from rich but noisy data
• The entropic origin of disassortativity in complex networks
• Nonparametric weighted stochastic block models

Cited by in corpus (29)

• Network reconstruction and community detection from dynamics
• Estimating network structure from unreliable measurements
• Reconstructing commuters network using machine learning and urban indicators
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Merge-split Markov chain Monte Carlo for community detection
• Link prediction with hyperbolic geometry
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Disentangling homophily, community structure and triadic closure in networks
• Reconstructing networks
• Machine Learning Link Inference of Noisy Delay-coupled Networks with Opto-Electronic Experimental Tests
• Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data
• Mapping flows on sparse networks with missing links
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• Hypergraph reconstruction from noisy pairwise observations
• Synergistic signatures of group mechanisms in higher-order systems
• Clustering of heterogeneous populations of networks
• Atomic subgraphs and the statistical mechanics of networks
• Algorithmic complexity of multiplex networks
• Analytical Formulation of the Block-Constrained Configuration Model
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Latent Poisson models for networks with heterogeneous density
• Symmetry-driven network reconstruction through pseudobalanced coloring optimization
• Missing links as a source of seemingly variable constants in complex reaction networks
• Robust and Efficient Network Reconstruction in Complex System via Adaptive Signal Lasso
• Cutting Through the Noise to Infer Autonomous System Topology
• Simulating systematic bias in attributed social networks and its effect on rankings of minority nodes
• Feature Learning and Network Structure from Noisy Node Activity Data
• Co-factor analysis of citation networks
• Anomaly, reciprocity, and community detection in networks