  The quantitative understanding and precise control of complex dynamical
systems can only be achieved by observing their internal states via measurement
and/or estimation. In large-scale dynamical networks, it is often difficult or
physically impossible to have enough sensor nodes to make the system fully
observable. Even if the system is in principle observable, high-dimensionality
poses fundamental limits on the computational tractability and performance of a
full-state observer. To overcome the curse of dimensionality, we instead
require the system to be functionally observable, meaning that a targeted
subset of state variables can be reconstructed from the available measurements.
Here, we develop a graph-based theory of functional observability, which leads
to highly scalable algorithms to i) determine the minimal set of required
sensors and ii) design the corresponding state observer of minimum order.
Compared to the full-state observer, the proposed functional observer achieves
the same estimation quality with substantially less sensing and computational
resources, making it suitable for large-scale networks. We apply the proposed
methods to the detection of cyber-attacks in power grids from limited phase
measurement data and the inference of the prevalence rate of infection during
an epidemic under limited testing conditions. The applications demonstrate that
the functional observer can significantly scale up our ability to explore
otherwise inaccessible dynamical processes on complex networks.
