Source-linked AI summary
Robust Reconstruction of Complex Networks from Sparse Data
Xiao Han, Zhesi Shen, Wen-Xu Wang, Zengru Di
TL;DR
Limited observable data, noise, and inaccessible nodes make network structure reconstruction difficult. The paper decomposes whole-network recovery into sparse local-neighborhood reconstruction with lasso, achieving high accuracy across dynamical processes and model and real networks from relatively small datasets.
Problem
Limited observable data, noise, and inaccessible nodes complicate reconstruction of network structures needed to understand and control collective dynamics.
Method
The framework infers each node’s local connections from measurable time-series relationships by formulating sparse signal reconstruction with lasso, then assembles the whole network from local neighborhoods.
Results
High reconstruction accuracy was achieved across ultimatum games, electrical-current transportation, and communications on homogeneous, heterogeneous, model, and real networks with noise and inaccessible nodes.
Takeaways & Limitations
The framework supports robust network reconstruction when available data are much less than network size and measurements include noise or missing nodes.
Takeaways & Limitations
The application scope is not completely known because no general procedure exists for establishing the reconstruction form Y = ΦX for different networked systems.
Abstract
from arXiv · showhide
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.