Robust Reconstruction of Complex Networks from Sparse Data

Xiao Han, Zhesi Shen, Wen-Xu Wang, and Zengru Di
Phys. Rev. Lett. 114, 028701 – Published 14 January 2015
PDFHTMLExport Citation

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.

  • Figure
  • Figure
  • Received 8 March 2014

DOI:https://doi.org/10.1103/PhysRevLett.114.028701

© 2015 American Physical Society

Authors & Affiliations

Xiao Han, Zhesi Shen, Wen-Xu Wang*, and Zengru Di

  • School of Systems Science, Beijing Normal University, Beijing 100875, People’s Republic of China

  • *wenxuwang@bnu.edu.cn

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 114, Iss. 2 — 16 January 2015

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×