Reconstructing Heterogeneous Networks via Compressive Sensing and Clustering

Reconstructing complex networks from observed data is a fundamental problem in network science. Compressive sensing, widely used for recovery of sparse signals, has also been used for network reconstruction under the assumption that networks are sparse. However, heterogeneous networks are not exactly sparse. Moreover, when using compressive sensing to recover signals, the projection matrix is usually a random matrix that satisfies the restricted isometry property (RIP) condition. This condition is much harder to satisfy during network reconstruction because the projection matrix depends on time-series data of network dynamics. To overcome these shortcomings, we devised a novel approach by adapting the alternating direction method of multipliers to find a candidate adjacency matrix. Then we used clustering to identify high-degree nodes. Finally, we replaced the elements of the candidate adjacency vectors of high-degree nodes, which are likely to be incorrect, with the corresponding elements of small-degree nodes, which are likely to be correct. The proposed method thus overcomes the shortcomings of compressive sensing and is suitable for reconstructing heterogeneous networks. Experiments with both artificial scale-free and empirical networks showed that the proposed method is accurate and robust.