Network Reconstruction under Compressive Sensing

  • user warning: Duplicate entry '10021-10436' for key 'PRIMARY' query: INSERT INTO drupal_morning_biblio_duplicates (vid, did, type) VALUES (10021, 10436, 0) in /var/www/dmlsite/includes/ on line 3529.
  • warning: Invalid argument supplied for foreach() in /var/www/dmlsite/sites/all/modules/biblio/ on line 181.
TitleNetwork Reconstruction under Compressive Sensing
Publication TypeJournal Article
Year of Publication2012
JournalASE Human Journal
Start Page130-143
Date Published12/2012
Type of ArticleJournal
AbstractMany real-world systems and applications such as World Wide Web, and social interactions can be modeled as networks of interacting dynamical nodes. However, in many cases, one encounters the situation where 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 Reconstruction Problem: Given a network with missing edges, how is it possible to uncover the network structure based on certain observable quantities extracted from partial measurements? We propose a novel framework called CS-NetRec based on a newly emerged paradigm in sparse signal recovery called Compressive Sensing (CS). The general idea of using CS is that if the presentation of information is sparse, then it can be recovered by using a few number of linear measurements. In particular, we utilize the observed data of information cascades in the context of CS for network reconstruction. Our comprehensive empirical analysis over both synthetic and real datasets demonstrates that the proposed framework leads to an efficient and effective reconstruction. More specifically, the results demonstrate that our framework can perform accurately even on low number of cascades (e.g. when the number of cascades is around half of the number of existing edges in the desired network). Furthermore, our framework is capable of near-perfect reconstruction of the desired network in presence of 95% sparsity. In addition, we compared the performance of our framework with NetInf; one of the state-of-the-art methods in inferring the networks of diffusion. The results suggest that the proposed method outperforms NetInf by an average of 10% improvement based on the F-measure.
URL<a href="/dmlsite/?q=%3Ca%20href%3D%22/dmlsite/%3Fq%3D%253Ca%2520href%253D%2522/dmlsite/%253Fq%253D%25253Ca%252520href%25253D%252522/dmlsite/%25253Fq%25253D%2525253Ca%25252520href%2525253D%25252522/dmlsite/%2525253Fq%2525253D%252525253Ca%2525252520href%25