Robust Reconstruction of Complex Networks from Sparse Data

Abstract

Reconstructing complex networks from measurable data is a fundamental problem for understanding and controlling collective dynamics of complex networked systems. However, a significant challenge arises when we attempt to decode structural information hidden in limited amounts of data accompanied by noise and in the presence of inaccessible nodes. Here, we develop a general framework for robust reconstruction of complex networks from sparse and noisy data. Specifically, we decompose the task of reconstructing the whole network into recovering local structures centered at each node. Thus, the natural sparsity of complex networks ensures a conversion from the local structure reconstruction into a sparse signal reconstruction problem that can be addressed by using the lasso, a convex optimization method. We apply our method to evolutionary games, transportation and communication processes taking place in a variety of model and real complex networks, finding that universal high reconstruction accuracy can be achieved from sparse data in spite of noise in time series and missing data of partial nodes. Our approach opens new routes to the network reconstruction problem and has potential applications in a wide range of fields.

5 pages, 2 figures, 2 tables

References in corpus (9)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Evolutionary games on graphs
• Community Structure in Jazz
• Revealing Network Connectivity From Dynamics
• Defense mechanisms of empathetic players in the spatial ultimatum game
• Reconstructing propagation networks with natural diversity and identifying hidden sources
• Revealing networks from dynamics: an introduction
• The effect of the topology on the spatial ultimatum game

Cited by in corpus (37)

• Network structure from rich but noisy data
• Model-free inference of direct network interactions from nonlinear collective dynamics
• Network reconstruction and community detection from dynamics
• Estimating network structure from unreliable measurements
• Identifying spatial invasion of pandemics on metapopulation networks via anatomizing arrival history
• A statistical inference approach to structural reconstruction of complex networks from binary time series
• Effects of human dynamics on epidemic spreading in Côte d'Ivoire
• Learning interaction kernels in heterogeneous systems of agents from multiple trajectories
• Detecting Hidden Units and Network Size from Perceptible Dynamics
• A universal data based method for reconstructing complex networks with binary-state dynamics
• Hypergraph reconstruction from dynamics
• Finding nonlinear system equations and complex network structures from data: a sparse optimization approach
• Universal structural estimator and dynamics approximator for complex networks
• Reconstructing Network Dynamics of Coupled Discrete Chaotic Units from Data
• Machine Learning Link Inference of Noisy Delay-coupled Networks with Opto-Electronic Experimental Tests
• Immediate Causality Network of Stock Markets
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• Variational Bayesian Weighted Complex Network Reconstruction
• Effects of hidden nodes on the reconstruction of bidirectional networks
• Revealing dynamics, communities and criticality from data
• Tomography of time-dependent quantum spin networks with machine learning
• From State Estimation to Network Reconstruction
• Synergistic signatures of group mechanisms in higher-order systems
• Structural Inference of Networked Dynamical Systems with Universal Differential Equations
• A practical method for estimating coupling functions in complex dynamical systems
• Decoupling approximation robustly reconstructs directed dynamical networks
• Robust and Efficient Network Reconstruction in Complex System via Adaptive Signal Lasso
• Distinguishing Cell Phenotype Using Cell Epigenotype
• Robust reconstruction of sparse network dynamics
• Global and partitioned reconstructions of undirected complex networks
• Reconstruction of Delay Differential Equation via Learning Parameterized Dictionary
• Tensor product algorithms for inference of contact network from epidemiological data
• Distinguishing pairwise and higher-order interactions in coupled oscillators from time series
• Interbank network reconstruction enforcing density and reciprocity
• Controlling symmetries and clustered dynamics of complex networks
• Optimal Localization of Diffusion Sources in Complex Networks
• Assessing the level of merging errors for coauthorship data: a Bayesian model