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. 89.75.Fb, 05.45.Tp Complex networked systems are common in many fields [1] [2] [3] . The need to ascertain collective dynamics of such systems to control them is shared among different scientific communities [4] [5] [6] . Much evidence has demonstrated that interaction patterns among dynamical elements captured by a complex network play deterministic roles in collective dynamics [7] . It is thus imperative to study a complex networked system as a whole rather than study each component separately to offer a comprehensive understanding of the whole system [8] . However, we are often incapable of directly accessing network structures; instead, only limited observable data are available [9] , raising the need for network reconstruction approaches to uncovering network structures from data. Network reconstruction, the inverse problem, is challenging because structural information is hidden in measurable data in an unknown manner and the solution space of all possible structural configurations is of extremely high dimension. So far a number of approaches have been proposed to address the inverse problem [4, 5, [9] [10] [11] [12] [13] [14] [15] [16] [17] . However, accurate and robust reconstruction of large complex networks is still a challenging problem, especially given limited measurements disturbed by noise and unexpected factors. In this letter, we develop a general framework to reconcile the contradiction between the robustness of reconstructing complex networks and limits on our ability to access sufficient amounts of data required by conventional approaches. The key lies in converting the network reconstruction problem into a sparse signal reconstruction problem that can be addressed by exploiting the lasso, a convex optimization algorithm [18, 19] . In particular, reconstructing the whole network structure can be achieved by inferring local connections of each node individually via our framework. The natural sparsity of complex networks suggests that on average the number of real connections of a node is much less than the number of all possible connections, i.e., the size of a network. Thus, to identify direct neighbors of a node from the pool of all nodes in a network is analogous to the problem of sparse signal reconstruction. By using the lasso that incorporates both an error control term and an L1-norm, the neighbors of each node can be reliably identified from a small amount of data that can be much less than the size of a network. The L1-norm, according to the compressed sensing theory [20] , ensures the sparse data requirement while, simultaneously, the error control term ensures the robustness of reconstruction against noise and missing nodes. The whole network can then be assembled by simply matching neighboring sets of all nodes. We will validate our reconstruction framework by considering three representative dynamics, including ultimatum games [21] , transportation [22] and communications [23] , taking place in both homogeneous and heterogeneous networks. Our approach opens new routes towards understanding and controlling complex networked systems and has implications for many social, technical and biological networks. We articulate our reconstruction framework by taking ultimatum games as a representative example. We then apply the framework to the transportation of electrical current and communications via sending data packets. In evolutionary ultimatum games (UG) on networks, each node is occupied by a player. In each round, player i plays the UG twice with each of his/her neighbors, both as a proposer and a responder with strategy (p i , q i ), where p i denotes the amount offered to the other player if i proposes and q i denotes the minimum acceptance level if i responds [24, 25] .
Another interesting topic is the network inference, which engages in revealing the topology structure of a network from the hint underlying the dynamics on a network REF .
Robust Reconstruction of Complex Networks from Sparse Data
Physical Review Letters, 114(2), 028701 (2015)
Physics Computer Science Medicine