Network structure reconstruction with symmetry constraint

Abstract Complex networks have been an effective paradigm to represent a variety of complex systems, such as social networks, collaborative networks, and biomolecular networks, where network topology is unkown in advance and has to be inferred with limited observed measurements. Compressive sensing (CS) theory is an efficient technique to achieve accurate network reconstruction in complex networks by formulating the problem as a series of convex optimization models and utilizing the sparsity of networks. However, previous CS-based works have to solve a large number of convex optimization models, which is time-consuming especially when the network scale becomes large. Further, since partial link information shared among multiple convex models, data conflict problem may incur when the derived common variables are inconsistent, which may badly degrade infer precision. To address the issues above, we propose a new model for network reconstruction based on compressive sensing. To be specific, a single convex optimization model is formulated for inferring global network structure by combing the series of convex optimization models, which can effectively improve computation efficiency. Further, we devise a vector to represent the connection states of all the nodes without redundant link information, which is used for representing the unkown topology variables in the proposed optimization model based a devised transformation method. In this way, the proposed model can eliminate data conflict problem and improve infer precision. The comprehensive simulation results shows the superiority of the proposed model compared with the competitive algorithms under a wide variety of scenarios.