  Sparse recovery can recover sparse signals from a set of underdetermined
linear measurements. Motivated by the need to monitor large-scale networks from
a limited number of measurements, this paper addresses the problem of
recovering sparse signals in the presence of network topological constraints.
Unlike conventional sparse recovery where a measurement can contain any subset
of the unknown variables, we use a graph to characterize the topological
constraints and allow an additive measurement over nodes (unknown variables)
only if they induce a connected subgraph. We provide explicit measurement
constructions for several special graphs, and the number of measurements by our
construction is less than that needed by existing random constructions.
Moreover, our construction for a line network is provably optimal in the sense
that it requires the minimum number of measurements. A measurement construction
algorithm for general graphs is also proposed and evaluated. For any given
graph $G$ with $n$ nodes, we derive bounds of the minimum number of
measurements needed to recover any $k$-sparse vector over $G$ ($M^G_{k,n}$).
Using the Erd\H{o}s-R\'enyi random graph as an example, we characterize the
dependence of $M^G_{k,n}$ on the graph structure.
