Compressed Sensing in Cyber Physical Social Systems

We overview the main results in Compressed Sensing and Social Networks, and discuss the impact they have on Cyber Physical Social Systems (CPSS), which are currently emerging on top of the Internet of Things. Moreover, inspired by randomized Gossip Protocols, we introduce TopGossip, a new compressed-sensing algorithm for the prediction of the top-k most influential nodes in a social network. TopGossip is able to make this prediction by sampling only a relatively small portion of the social network, and without having any prior knowledge of the network structure itself, except for its set of nodes. Our experimental results on three well-known benchmarks, Facebook, Twitter, and Barabási, demonstrate both the efficiency and the accuracy of the TopGossip algorithm.