Network Reconstruction Based on Evolutionary-Game Data via Compressive Sensing

Evolutionary games model a common type of interactions in a variety of complex, networked, natural systems and social systems. Given such a system, uncovering the interacting structure of the underlying network is key to understanding its collective dynamics. Based on compressive sensing, we develop an efficient approach to reconstructing complex networks under game-based interactions from small amounts of data. The method is validated by using a variety of model networks and by conducting an actual experiment to reconstruct a social network. While most existing methods in this area assume oscillator networks that generate continuous-time data, our work successfully demonstrates that the extremely challenging problem of reverse engineering of complex networks can also be addressed even when the underlying dynamical processes are governed by realistic, evolutionary-game type of interactions in discrete time.

Popular Summary

Complex networks and compressive sensing seem like two scientific topics that are far apart. Complex networks, composed of individual nodes and links, are mathematical- and physical- framework structures that distill and describe the essence and salient features of many complex interacting systems in nature and society. Neuronal networks in the human brain, protein networks in biological cells, and collaboration networks among scientists are some of the significant and interesting examples of complex networks. Compressive sensing is a technique recently developed in applied mathematics and signal processing to reconstruct a full picture and dynamics of an underlying system based on only a sparse amount of data. It has been widely used in many applications, including, for example, the analysis of large-scale sensor networks and digital-image processing in electrical engineering. In this paper, we bring compressive sensing to bear on the studies of complex networks and solve, for a class of social-interaction networks, one of the most challenging problems in complex-networks research: The problem of reconstructing the full node-link structures of interactions of the networks from sparse data on how the individual nodes act or function.

Interactions underlying a broad range of social-interaction networks fall under the theoretical models of evolutionary games, such as the so-called prisoner’s-dilemma games, which are caricatures of the emergence and the persistence of social cooperation among selfish individuals. In this paper, we first investigate theoretical models of networks of a number of known benchmark structures, where the individual parties (or nodes) interact with each other through a type of evolutionary game. Based only on small amounts of data collected on the individual players’ actions and results and, without using at all any prior knowledge of the network structures, our compressive-sensing-inspired approach successfully reconstructs the network structures faithfully.

To show that this success is not limited just to the theoretical models, we also conduct an actual social-interaction experiment involving 22 participants from Arizona State University, in which they play a version of prisoner’s-dilemma games. After collecting only a small amount of data on the participants’ strategies and payoffs, we apply our technique to analyze the data, assuming no knowledge of any existing social links between the participants. As in the cases of theoretical models, we fully uncover the network hosting those social links.

Looking ahead, we believe that our method can potentially be applied in other important contexts in science, for example, to construct gene-regulation networks from limited experimental data or digital-communication networks from information flow.

Figure 1

Success rates of inferring three types of networks: random, small-world and scale-free, with PDG and SG dynamics. The network size $N$ is 100. Each data point is obtained by averaging over 10 network realizations. For each realization, measurements are randomly picked from a time series of temporary evolution. The error bars denote the standard deviations. The payoff parameters for the PDG and the SG are $b=1.2$ and $r=0.7$, respectively. We have also systematically tested other values of $b$ and $r$ and obtained similar success rates. The average node degrees of all used networks are fixed to 6 and the noise parameter $\kappa =0.1$.

Figure 2

Threshold data $T_{\mathrm{d}}$ of SREL and SRNL for a successful reconstruction as a function of network size $N$ for PDG and SG on scale-free networks, where $T_{\mathrm{d}}$ is defined as the amount of data normalized by network size that enables 99% success rate. Each data point is obtained by 10 independent realizations, and the error bars represent standard deviations. The average node degrees of all used networks are fixed to 6. The parameters in the PDG and the SG are $b=1.2$, $r=0.7$, and $\kappa =0.1$.

Figure 3

Prediction errors $E_w$ in link weights and $E_z$ in nonexistent links for PDG on weighted scale-free networks. The network size is 100, and the weights follow a uniform distribution, ranging from 1.0 to 6.0. Each value of the prediction error is obtained using 10 independent network realizations. Other parameters are the same as for Fig. 1.

Figure 4

(a) Structure of the experimental social network. (b) Success rates of uncovering the network topology and (c) normalized payoff of each player as a function of node degrees. The sizes of the red nodes in (a) denote their node degrees, and the two light gray nodes (for players who did not complete the experiment) are isolated without any interactions with other nodes. The 10 independent realizations used in calculating the average success rates were randomly chosen from the database of 31 rounds of games.