Network Observability Transitions

In the modeling, monitoring, and control of complex networks, a fundamental problem concerns the comprehensive determination of the state of the system from limited measurements. Using power grids as example networks, we show that this problem leads to a new type of percolation transition, here termed a network observability transition, which we solve analytically for the configuration model. We also demonstrate a dual role of the network’s community structure, which both facilitates optimal measurement placement and renders the networks substantially more sensitive to “observability attacks.” Aside from their immediate implications for the development of smart grids, these results provide insights into decentralized biological, social, and technological networks.

Figure 1

Diagram for the self-consistent equations of (a) the probability $s$ and (b) the probability $u$ that an observable node $i$ (red circle) is not connected to the LOC through a specific edge $e_{ij}$ (red line). The nodes are either not observable (open circles) or observable (solid circles), where green rings mark directly observable nodes.

Figure 2

Network observability transitions. (a) LOC size as a function of $\varphi$ in networks with the degree distributions of the power grids of Germany (red), Europe (green), Spain (blue), and Eastern North America (black) [11, 21]. The continuous lines correspond to our analytical predictions, and the symbols to an average over ten ${10}^6$-node random networks for ten independent random PMU placements each. The inset shows a magnification around the transitions, with the predicted thresholds ${\varphi }_c$ indicated by arrows. (b) Dependence of ${\varphi }_c$ on $⟨k⟩$ and ${\sigma }^2$ for networks (in the thermodynamic limit) with Gamma degree distributions, where the curves indicate equispaced isolines of ${\varphi }_c$ and the symbols indicate the $(⟨k⟩,{\sigma }^2)$ positions of the corresponding networks in (a).

Figure 3

Observability on the largest available power grid (Eastern North America). (a) Complete and incomplete observability: LOC size and FON for random PMU placement (red), greedy LOC size optimization (green), and greedy FON optimization (blue) on the optimal set. The corresponding curves for placement on the full network are shown in gray. (b) Network evolution: LOC size and FON on the planned networks for the years 2015 and 2020 given the optimal PMU placement on the 2010 network (red). The black lines represent the net increase in the number of nodes ($\Delta N$) and the total number of nodes modified by node additions, node removals, or edge rewires ($\Delta N_T$). To facilitate comparison, all curves are plotted relative to the initial number of nodes. (c) Observability attack: LOC size and FON for both FON attack (blue) and LOC size attack (green), where the latter takes advantage of the community structure of the network.