Analysis of Contractions in System Graphs:
Application to State Estimation

Large-scale networked systems have seen a surge of interest in recent control and signal processing literature with applications in IoT and CPS  [1, 2, 3]. A key challenge in such networks is state estimation [4, 2, 5] via a distributed network of measurements. From this perspective of distributed estimation, an effective tool is the system graph in which nodes represent state variables and edges between two nodes show coupling among the two state variables [6, 7, 8], motivating structural control and graph signal processing. In this sense, structural observability is related to certain system graph properties relying only on the system structure, and not on the exact system parameter values [6, 4, 7, 9].

An important graph-theoretic property to study system observability is the notion of contraction in the system graph, which is the dual of dilation in controllability [7]. In a contraction, multiple nodes are contracted (connected) to a fewer group of nodes. It is known that measuring one state node in every contraction is essential for network observability [10, 11]. All states in a contraction are thus observationally equivalent which is significant for observability recovery, for example, in sensor/measurement failure [4, 11]. The size of contractions is also a key property, representing the number of possible options for estimation/observability recovery. A large contraction presents more choices of equivalent state measurements to replace the failed/faulty observation, or, for example, to minimize cost [12, 13, 14]. Also, the number of contractions represents the number of necessary measurement (or sensors) for estimation. The size and distribution of contractions in a system graph depend on certain graph properties. This work particularly studies how the global clustering coefficient affects the distribution of contractions. This paper is a nonlinear model extension of our previous works [10, 1] on local clustering coefficient and degree heterogeneity.

This paper models the nonlinear system as a random Scale-Free (SF) graph. The reason is that the structure of most real-world systems resemble the structure of SF graphs [15]. To study the effect of the GCC, as our main contribution, the distribution of size/number of contractions in SF graphs and clustered SF (CSF) graphs are compared. Due to specific formation in CSF graphs (known as triad formation) they have higher GCC, while their other properties (particularly power-law degree distribution) are similar to SF graphs. The significance of this contribution is that by tuning the network GCC, e.g., adopting the results of [16, 17], one can improve/impair system observability properties. Our results can be used in the design of large-scale man-made networks to improve their estimation properties in terms of reducing necessary observer nodes (sensor locations) for cost-optimal estimation. An example of such re-design of power grid is given in Section 5 as another contribution of this paper. Another possible application is in changing the structure of social networks to hinder the possibility of distributed estimation [18, 19] and, therefore, improve information privacy and reduce the vulnerability towards information leakage [20].

The rest of this paper is as follows. Section 2 describes graph-theory notions to define the contractions. Section 3 states the specific application to system estimation and observability. In Section 4, the distribution of contractions in SF and CSF graphs are compared, and an illustrative example application in power grid monitoring is given in Section 5. Conclusions and future research are presented in Section 6.

We consider the complex system, for example a social system, as an undirected graph or a strongly-connected directed graph (SC digraph) denoted by $\mathcal{G}=(\mathcal{V},\mathcal{E})$, with the node set $\mathcal{V}$ (representing the $n$ states) and edge/link set $\mathcal{E}=\{(v_{i},v_{j})\}$. The associated bipartite system graph $\Gamma=(\mathcal{V}^{+},\mathcal{V}^{-},\mathcal{E}_{\Gamma})$ is defined with two disjoint left/right node sets $\mathcal{V}^{+}$ and $\mathcal{V}^{-}$, and edges $\mathcal{E}_{\Gamma}=\{(v_{j}^{-},v_{i}^{+})|(v_{j},v_{i})\in\mathcal{E}\}$. In $\mathcal{G}$, the edges with no common end node are called a matching $\underline{\mathcal{M}}$, which equivalently in $\Gamma$ represent the subset of edges not incident on the same node in $\mathcal{V}^{+}$. In other words, $\underline{\mathcal{M}}$ is a set of pairwise disjoint edges (with no loop). A matching with maximum size is called maximum (cardinality) matching $\mathcal{M}$, which is not a subset of any other matching. Note that there are many possible choices of $\mathcal{M}$ in general. The nodes respectively in $\mathcal{V}^{+}$ and $\mathcal{V}^{-}$ incident to the chosen $\mathcal{M}$ are denoted by $\partial\mathcal{M}^{+}$ and $\partial\mathcal{M}^{-}$, and the nodes in ${\delta\mathcal{M}=\mathcal{V}^{+}\backslash\partial\mathcal{M}^{+}}$ are unmatched in $\mathcal{V}^{+}$. Given $\mathcal{M}$, let $\Gamma^{\mathcal{M}}$ be the auxiliary graph made by reversing all edges in $\mathcal{M}$, and holding all the other edges $\mathcal{E}_{\Gamma}\backslash\mathcal{M}$ in $\Gamma$. In $\Gamma^{\mathcal{M}}$, an alternating path associated to ${\mathcal{M}}$ (also called ${\mathcal{M}}$-alternating path), denoted by$\mathcal{Q}_{\mathcal{M}}$, is a path starting from a node in $\delta\mathcal{M}$ with its edges alternately in $\mathcal{M}$ and not in $\mathcal{M}$. An augmenting path $\mathcal{P}_{\mathcal{M}}$ associated to ${\mathcal{M}}$ (also called ${\mathcal{M}}$-augmenting path) is an ${\mathcal{M}}$-alternating path in $\Gamma^{\mathcal{M}}$ that starts from and ends in $\delta\mathcal{M}$. For a matching $\underline{\mathcal{M}}$ and associated $\mathcal{P}_{\underline{\mathcal{M}}}$, $\underline{\mathcal{M}}\oplus\mathcal{P}_{\underline{\mathcal{M}}}$ represents a new matching with one more edge than $\underline{\mathcal{M}}$, where $\oplus$ is the XOR operator. In $\Gamma^{\mathcal{M}}$, a contraction $\mathcal{C}_{j}$, associated to an unmatched node $v_{j}\in\delta\mathcal{M}$, is defined as the set of all state nodes in $\mathcal{V}^{+}$ reachable by ${\mathcal{M}}$-alternating paths starting from $v_{j}$. Intuitively speaking, contraction represents subset of nodes linking to smaller subset of nodes [21, 10]. Algorithm 1 [21, 10] presents the pseudo-code for finding graph contractions with polynomial order complexity $\mathcal{O}(n^{2.5})$. Polynomial complexity facilitates applications in large-scale as in social networks or power grids.

In this paper, as our main contribution, we aim to understand possible correlation between the GCC and prevalence of contractions, and interpret the implication of this relation through a system estimation perspective.

In this work, a nonlinear autonomous dynamic system (in contrast to the linear model in [10]) is considered as,

where the state variable $\mathbf{x}=[x^{1},\ldots,x^{n}]^{\top}\in\mathbb{R}^{n}$ is to be estimated via the measurements,

where $\mathbf{y}=[y^{1},\ldots,y^{m}]\in\mathbb{R}^{m}$ is the measurement, and $\mathbf{v}$ and $\mathbf{r}$ are Gaussian noise. The system model (1)-(2) can be represented as a Linear-Structure-Invariant (LSI) model as,

where $A(t)$ and $C(t)$ are time-dependent system and measurement matrices representing the linearization of the system and measurement functions $f(\cdot)$ and $g(\cdot)$ over time. Recall that, from Kalman filtering theory, the underlying system can be estimated if it is observable via the given measurements. System observability implies that the global vector, $\mathbf{x}$, can be uniquely determined by the measurements, $\mathbf{y}$. As shown in [7], the observability of the nonlinear model (1)-(2) is equivalent with the observability of the linearized model (3)-(4) over all operating points. The structure (the zero-nonzero pattern) of the associated linearized matrices $A(t)$ and $C(t)$ are time-invariant while the numerical values of their nonzero entries may vary at different operating points, implying the name structure-invariant. This motivates the concept of structural observability (or generic observability) based on structured systems theory [6, 7, 9], which provides a graph-theoretic method to check for system observability. In structural analysis the system is modeled as a system graph, where a node $v_{i}$ models a state $x^{i}$ and a link $v_{j}\rightarrow v_{i}$ models the dependency of the two state variables $x^{i}$ and $x^{j}$. In other words, if $f^{i}$ is a function of $x^{j}$ then the entry $\frac{\partial f^{i}}{\partial x^{j}}$ in linearized matrix $A$ is nonzero while its exact value depends on the operating point and may change over time [19, 9]. Denote the system graph by $\mathcal{G}_{A}=(\mathcal{V},\mathcal{E}_{A})$, with state nodes $\mathcal{V}$ and $\mathcal{E}_{A}=\{(v_{j},v_{i})~{}|~{}\frac{\partial f^{i}}{\partial x^{j}}\neq 0\}$ including the edges $v_{j}\rightarrow v_{i}$. Using the definitions in Section 2, the next theorem states necessary conditions for observability of the system graph $\mathcal{G}_{A}$.

We refer to [7] for the proof (in the dual case of controllability). Based on the definition, for a given maximum matching $\mathcal{M}$, every node $v_{j}\in\delta\mathcal{M}$ belongs to a contraction $\mathcal{C}_{i}$, while the nodes $\mathcal{C}_{i}\backslash v_{j}$ are all matched. This leads to the following observational equivalence property in contractions:

See the proofs in [10, 11]. This corollary implies that when a critical measurement fails, causing loss of observability, measurement of any other state node in the same contraction recovers the system observability [4]. Recall that (structural) rank deficiency of the system matrix $A$ defines the cardinality of $\delta\mathcal{M}$ and $\mathcal{C}$ in its associated system graph $\mathcal{G}_{A}$ [21, 22].

In this section, the distribution of contractions in SF networks, as random graph-representations of real-world systems, is studied. Such random models simplify the understanding of different processes, e.g., spreading processes and cascading failures [15, 23, 24, 25]. The main feature of SF graphs is their power-law degree distribution [15], which implies that there are few hubs (nodes with high degree) and large number of low-degree nodes in the SF network. To construct such networks, Ref. [15] provides an iterative algorithm initializing with a small seed graph and recursively adding a new node with $m$ new edges. The main feature of this iterative procedure is that the linking probability between the new node and an old node is proportional to its degree. In other words, the new node prefers connecting to old hubs, hence it is named preferential attachment. Such SF graphs are known to have low GCC¹¹1GCC is defined as the ratio of the triangles $tr$ to the total number of connected open triplets $trp$ in the graph, i.e., $\text{GCC}=\frac{3.tr}{trp}$ [15]., while real-world networks, for example social networks, show high clustering. Therefore, a modified model with high GCC is proposed [23, 24, 25], named Clustered Scale Free (CSF). The building blocks of this model are similar to the preferential attachment, where the difference is the triad formation step. In this model, the newly added node directly links to $m_{r}$ nodes, while also making $m_{s}$ preferential linking to some neighbors of $m_{r}$ preferentially attached nodes to create triads. This significantly increases the GCC in CSF networks with the same average node degree as SF networks.

The power grid, as an engineered infrastructural network, can be conceived as a large-scale dynamical system [26], where the sparcity of its (linearized) system matrix follows the structure of the power distribution network [27]. To ensure reliable power delivery, the electrical phasor state (voltage, current, etc.) is typically measured via advanced sensors, known as phasor measurement units (PMUs), distributed over the electricity grid. The PMU placement is such that to ensure observability of the entire power grid for monitoring puposes [28]. Following the results of this paper, one can reduce the number of allocated PMUs for observability by changing the structure of the power network. Consider the European power grid [29] shown in Fig. 2(top) with $1494$ nodes (buses) and $2156$ edges (transmission lines). The unmatched nodes represent the possible location of PMU placement in the grid. Following the results in Section 4, we increase the GCC by adding $40$ edges between certain bus-nodes in the network as shown in Fig. 2(bottom). The network grid properties before and after link addition are compared in Table 2. Note that the change in average node degree is negligible while the GCC is increased about $19\%$. As expected, contractions and unmatched nodes are reduced by $47\%$ by adding only $40$ edges which are about $1.8\%$ of the total edges in the network.

In this work, distribution of contractions in SC digraphs and its relation with graph GCC is studied. Note that for general non-SC digraphs, another component known as root SCC or parent SCC also affects system graph observability [30, 31]. As future research, we intend to study the correlation between prevalence/size of both parent SCCs and contractions with other graph features, such as assortativity/disassortativity and community/hierarchical structure [15].