Robust Reconstruction of Complex Networks from Sparse Data
Open Access
- 14 January 2015
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 114 (2), 028701
- https://doi.org/10.1103/physrevlett.114.028701
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.Funding Information
- National Natural Science Foundation of China (11105011, 61374175)
This publication has 37 references indexed in Scilit:
- Wisdom of crowds for robust gene network inferenceNature Methods, 2012
- Abnormal cascading on complex networksPhysical Review E, 2009
- The effect of the topology on the spatial ultimatum gameZeitschrift für Physik B Condensed Matter, 2008
- Reconstructing the topology of sparsely connected dynamical networksPhysical Review E, 2008
- Evolutionary games on graphsPhysics Reports, 2007
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- Taming complexityNature Physics, 2005
- Fairness Versus Reason in the Ultimatum GameScience, 2000
- Management of multiple congested conditions in unbundled operation of a power systemIEEE Transactions on Power Systems, 1998
- Envisioning power system data: concepts and a prototype system state representationIEEE Transactions on Power Systems, 1993