Missing and spurious interactions and the reconstruction of complex networks

Abstract

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.

References in corpus (14)

• Community structure in social and biological networks
• Cooperative Game Theory Approaches for Network Partitioning
• Synchronization in complex networks
• Mixing patterns in networks
• Characterization of complex networks: A survey of measurements
• Hierarchical structure and the prediction of missing links in networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Optimal network topologies for local search with congestion
• Epidemic spreading in correlated complex networks
• Extracting the hierarchical organization of complex systems
• Classes of complex networks defined by role-to-role connectivity profiles
• Detection of node group membership in networks with group overlap

Cited by in corpus (168)

• Link Prediction in Complex Networks: A Survey
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Leaders in Social Networks, the Delicious Case
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Robust Detection of Dynamic Community Structure in Networks
• The Statistical Physics of Real-World Networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Learning Latent Block Structure in Weighted Networks
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Network structure from rich but noisy data
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Rate-optimal graphon estimation
• Link prediction in complex networks: a local na\"ıve Bayes model
• Enhancing network robustness for malicious attacks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Topological data analysis of contagion maps for examining spreading processes on networks
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Random graph models for dynamic networks
• Network reconstruction and community detection from dynamics
• Link Prediction in Complex Networks: A Mutual Information Perspective
• Estimating the number of communities in a network
• Entropy of stochastic blockmodel ensembles
• Progresses and Challenges in Link Prediction
• Link Prediction with Node Clustering Coefficient
• Predicting missing links and their weights via reliable-route-based method
• Bayesian stochastic blockmodeling
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Link Prediction via Matrix Completion
• Nonparametric weighted stochastic block models
• Link prediction via linear optimization
• Model Selection for Degree-corrected Block Models
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Reconstruction methods for networks: the case of economic and financial systems
• A network inference method for large-scale unsupervised identification of novel drug-drug interactions
• Estimating network structure from unreliable measurements
• Efficient method for estimating the number of communities in a network
• Reconstructing networks with unknown and heterogeneous errors
• Link Prediction in Multiplex Networks based on Interlayer Similarity
• Predicting the Future of AI with AI: High-quality link prediction in an exponentially growing knowledge network
• Benchmark model to assess community structure in evolving networks
• Removing spurious interactions in complex networks
• Finding missing edges in networks based on their community structure
• Reconstructing commuters network using machine learning and urban indicators
• Link Prediction in Complex Networks: A Clustering Perspective
• Bayesian inference of network structure from unreliable data
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• Consistencies and inconsistencies between model selection and link prediction in networks
• Structural inference for uncertain networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Collective dynamics of stock market efficiency
• Uncovering missing links with cold ends
• Justice blocks and predictability of US Supreme Court votes
• Accurate and scalable social recommendation using mixed-membership stochastic block models
• Predicting human preferences using the block structure of complex social networks
• Merge-split Markov chain Monte Carlo for community detection
• Link prediction with hyperbolic geometry
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Matching-centrality decomposition and the forecasting of new links in networks
• The interplay of microscopic and mesoscopic structure in complex networks
• Review on Learning and Extracting Graph Features for Link Prediction
• Network structure, metadata and the prediction of missing nodes and annotations
• Revealing consensus and dissensus between network partitions
• Stochastic block model and exploratory analysis in signed networks
• Disentangling homophily, community structure and triadic closure in networks
• Reconstructing networks
• Robustness of Network Measures to Link Errors
• Accuracy Test for Link Prediction in terms of Similarity Index: The Case of WS and BA Models
• Prediction of scientific collaborations through multiplex interaction networks
• Identifying vital nodes by Achlioptas process
• Fundamental limits to learning closed-form mathematical models from data
• Latent Self-Exciting Point Process Model for Spatial-Temporal Networks
• Predicting missing links via significant paths
• Link prediction in multiplex networks via triadic closure
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Validation of a smartphone app to map social networks of proximity
• Representative community divisions of networks
• Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• The maximum capability of a topological feature in link prediction
• Link Prediction Adversarial Attack
• Predicting future conflict between team-members with parameter-free models of social networks
• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• The Infinite Degree Corrected Stochastic Block Model
• Multilayer Networks for Text Analysis with Multiple Data Types
• Mapping flows on sparse networks with missing links
• Mining and Forecasting Career Trajectories of Music Artists
• Finding missing edges and communities in incomplete networks
• A multi-class approach for ranking graph nodes: models and experiments with incomplete data
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• Collaborative Filtering Approach to Link Prediction
• A Stochastic Block Model Approach for the Analysis of Multilevel Networks: an Application to the Sociology of Organizations
• Local degree blocking model for link prediction in complex networks
• Improving personalized link prediction by hybrid diffusion
• A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions
• Entropy-based approach to missing-links prediction
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Target Defense Against Link-Prediction-Based Attacks via Evolutionary Perturbations
• Estimating the outcome of spreading processes on networks with incomplete information: a mesoscale approach
• Higher-order link prediction via local information
• Growing networks of overlapping communities with internal structure
• Known by the company we keep: `Triadic influence' as a proxy for compatibility in social relationships
• Bidirectional selection between two classes in complex social networks
• GitHub open source project recommendation system
• Inferring Network Structure with Unobservable Nodes from Time Series Data
• Convex skeletons of complex networks
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Inferring propagation paths for sparsely observed perturbations on complex networks
• Semi-supervised network inference using simulated gene expression dynamics
• Inference of Edge Correlations in Multilayer Networks
• Detecting Hidden Layers from Spreading Dynamics on Complex Networks
• Performance of Local Information Based Link Prediction: A Sampling Perspective
• Symmetry-driven network reconstruction through pseudobalanced coloring optimization
• Network-based confidence scoring system for genome-scale metabolic reconstructions
• Missing links as a source of seemingly variable constants in complex reaction networks
• Decoupling approximation robustly reconstructs directed dynamical networks
• DecLiNe -- Models for Decay of Links in Networks
• Change-Point Detection in Dynamic Networks with Missing Links
• Limitations and Alternatives for the Evaluation of Large-scale Link Prediction
• Simulating systematic bias in attributed social networks and its effect on rankings of minority nodes
• Community models for networks observed through edge nominations
• Automatic Discovery of Families of Network Generative Processes
• Fundamental Structures in Dynamic Communication Networks
• Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network
• Geometric randomization of real networks with prescribed degree sequence
• Link Prediction via controlling the leading eigenvector
• Contextual Centrality: Going Beyond Network Structures
• Analytical approach to network inference: Investigating degree distribution
• Strong Structural Controllability of Colored Structured Systems
• The Atlas for the Aspiring Network Scientist
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• Node metadata can produce predictability transitions in network inference problems
• Dynamic patterns of knowledge flows across technological domains: empirical results and link prediction
• Network Backboning with Noisy Data
• Global and partitioned reconstructions of undirected complex networks
• Learning common structures in a collection of networks. An application to food webs
• The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome
• Synthetic graphs for link prediction benchmarking
• DINE: A Framework for Deep Incomplete Network Embedding
• Reconstructing propagation networks with temporal similarity metrics
• Missing Data as Part of the Social Behavior in Real-World Financial Complex Systems
• Feature Learning and Network Structure from Noisy Node Activity Data
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Understanding the Design Principles of Link Prediction in Directed Settings
• SimBins: An information-theoretic approach to link prediction in real multiplex networks
• Priority Attachment: a Comprehensive Mechanism for Generating Networks
• Data reliability in complex directed networks
• Discrimination universally determines reconstruction of multiplex networks
• Network-based models for social recommender systems
• Assessing the level of merging errors for coauthorship data: a Bayesian model
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay
• Complex network prediction using deep learning
• Link prediction for interdisciplinary collaboration via co-authorship network
• Hierarchical Hyperlink Prediction for the WWW
• From Cities to Series: Complex Networks and Deep Learning for Improved Spatial and Temporal Analytics*
• Domain matters: Towards domain-informed evaluation for link prediction
• Impacts of Data Splitting Strategies on Parameterized Link Prediction Algorithms
• Drug-disease networks and drug repurposing
• Outliers Detection in Networks with Missing Links
• A Block-based Generative Model for Attributed Networks Embedding
• Disentangling the structure of ecological bipartite networks from observation processes
• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks