Network Reconstruction under Compressive Sensing

Many real-world systems and applications such asWorld Wide Web, and social interactions can bemodeled as networks of interacting dynamical nodes.However, in many cases, one encounters the situationwhere the pattern of the node-to-node interactions(i.e., edges) or the structure of a network is unknown.We address this issue by studying the Network Re-construction Problem: Given a network with missingedges, how is it possible to uncover the networkstructure based on certain observable quantities ex-tracted from partial measurements? We propose anovel framework called CS-NetRec based on a newlyemerged paradigm in sparse signal recovery calledCompressive Sensing (CS). The general idea of us-ing CS is that if the presentation of information issparse, then it can be recovered by using a few num-ber of linear measurements. In particular, we utilizethe observed data of information cascades in thecontext of CS for network reconstruction. Our com-prehensive empirical analysis over both synthetic andreal datasets demonstrates that the proposed frame-work leads to an efficient and effective reconstruction.More specifically, the results demonstrate that ourframework can perform accurately even on low num-ber of cascades (e.g. when the number of cascadesis around half of the number of existing edges inthe desired network). Furthermore, our framework iscapable of near-perfect reconstruction of the desirednetwork in presence of 95% sparsity. In addition, wecompared the performance of our framework withNetInf; one of the state-of-the-art methods in infer-ring the networks of diffusion. The results suggestthat the proposed method outperforms NetInf by anaverage of 10% improvement based on the F-measure.