Compressive Sensing is a new paradigm in signal processing and information theory for efficient sparse signal recovery which aims to simultaneously sample and compress sparse signals. It tries to recover high dimensional signals from a total number of measurements much smaller than their dimensions. This is possible if we have prior knowledge about some properties (i.e. sparsity) of the signal to be recovered. Compressive sensing has drawn much attention in several fields (such as astronomy, biology, image and video processing, medicine, and cognitive radio) for its ability to extract sparse information from big data. However, its role in networking is still in its early stages due to the existing challenges. One of most limiting challenges is the construction of measurement matrix that must be feasible based on two fundamental constraints: taking only nonnegative integer entries; and considering the topology of network (graph) which means only nodes that induce a connected sub-graph in the underlying topology can be aggregated together in the same measurement.
This open problem for sparse recovery in networks has many real-world applications. For example, central nodes play significant roles in the spread of propaganda, ideologies, or gossips in social networks. Taking the advertising industry, in order to improve the effectiveness of word of mouth
advertising and increase recommendation-based product adoption, companies may only want to give free product samples to central nodes instead of giving free samples to random people. For example, CNN reported that Samsung offers free phones to frustrated iPhone users in an
advertising campaign using information from social networks, or CNET said that this company gives iPhone users a trial run with new Galaxy smartphones. To this end, Samsung tried to identify dissatisfied iPhone owners who are the most important users in terms of communicating with other users. This problem is formally defined as, “for any given positive integer k, the top-k nodes in a social network, based on a certain measure appropriate for the network”. We can address such challenging problems via compressive sensing considering network topological structure.