A two-stage algorithm for network reconstruction

The topology of a network is crucial to its function and behavior. In many cases, various data are obtained from the network, for example, information spreading data, gene expression microarray data, game data, but the topology of the network is unknown. Reconstructing the topology of the network from the observed data is meaningful in many applications. In this paper an evolutionary algorithm is proposed for network reconstruction from observed game data. The proposed two-stage evolutionary algorithm decomposes the network reconstruction problem as sequentially reconstructing the edges of the nodes. The edges of a node are described by the corresponding column vector of the network adjacency matrix. In the first stage, possible vectors are obtained from the proposed genetic algorithm. In the second stage, the true vector is obtained by the proposed heuristic local search. Both analyses and experiments show that the proposed evolutionary algorithm is more accurate and applicable in more general cases than the algorithm based on compressive sensing theory.