DocumentCode :
2439442
Title :
Network Reconstruction under Compressive Sensing
Author :
Siyari, Peyman ; Rabiee, Hamid R. ; Salehi, Marzieh ; Mehdiabadi, M.E.
Author_Institution :
Dept. of Comput. Eng., Sharif Univ. of Technol., Tehran, Iran
fYear :
2012
fDate :
14-16 Dec. 2012
Firstpage :
19
Lastpage :
25
Abstract :
Many real-world systems and applications such as World Wide Web, and social interactions can be modeled as networks of interacting 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 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.
Keywords :
compressed sensing; signal reconstruction; CS; CS-NetRec framework; World Wide Web; compressive sensing; network reconstruction problem; network structure; node-to-node interaction; social interaction; sparse signal recovery; Compressive Sensing; Network Reconstruction; networks of diffusion;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Social Informatics (SocialInformatics), 2012 International Conference on
Conference_Location :
Lausanne
Print_ISBN :
978-1-4799-0234-7
Type :
conf
DOI :
10.1109/SocialInformatics.2012.84
Filename :
6542417
Link To Document :
بازگشت