A Hetero-functional Graph Resilience Analysis for Convergent Systems-of-Systems

Our modern life has grown to depend on many and nearly ubiquitous large complex engineering systems[1]. Transportation, water distribution, electric power, natural gas, healthcare, manufacturing, agriculture, and supply chain logistics are but a few. These systems are characterized by a large number of component parts that realize many elaborate processes in a highly complex web of interactions. Our heavy reliance on these systems coupled with a growing recognition that disruptions and failures; be they natural or man-made; unintentional or malicious; are inevitable[2, 3, 4]. Therefore, in recent years, many disciplines have seemingly come to ask the same question: “How resilient are these systems?” Said differently, in the face of assumed disruption, to what degree will these systems continue to perform and when will they be able to bounce back to normal operation[5, 6, 7]. Furthermore, the major disruptions of 9/11, the 2003 Northeastern Blackout, and Hurricane Katrina has caused numerous agencies[8, 9, 10] to make resilient engineering systems a policy goal.

While each of the large complex engineering systems mentioned above require greater resilience in their own right, there is a growing recognition that the greatest societal challenges of the Anthropocene era are indeed intertwined[11, 12, 13]. For example, the simultaneous stabilization of carbon emissions, management of nitrogen and phosphorus cycles, and provision of clean water creates complex synergies and trade-offs across multiple underlying engineering systems. In contrast, a systematic review of 245 publications on the food-energy-water nexus[14] revealed that most do not even capture interactions among water, energy and food that they purport to address. Similarly, Northeast Hurricane Sandy and Texas Winter Storm Yuri revealed the interdependence of the natural gas, electric power, and transportation systems[15, 16, 17]. The interdependence and consequent emergent behavior between these critical engineering systems must be systematically identified, understood, and analyzed[18, 19] within a larger systems-of-systems modeling and analysis framework[20, 21]. Because of each of these systems is associated with its own engineering discipline, systems-of-systems engineering [22, 23] requires a deep convergence of disciplines founded on reconciled ontologies, data, and theoretical methods[24].

Perhaps in contrast to convergence research, a large body of academic literature has developed on the subject across multiple disciplines. These include ecological[25], economic[26], organizational[27, 28], network[29, 30, 31, 32, 33, 34], socio-ecological[35], infrastructure[36, 37, 38] , and psychological[39] resilience. Not surprisingly, a number of reviews [39, 40, 41, 42, 43, 44, 45, 46, 47] on the topic have found that these contributions while complementary are not necessarily in agreement[48]. The emerging field of resilience engineering, therefore, is still developing and requires formal conceptualizations and definitions[49, 50, 51, 52, 53, 54, 55], and quantitative models and measures[56, 57, 58, 59, 60, 61, 62]. A key element to such rigorous approaches is the development of resilience measures which many, even recently, have identified as an area for concerted effort[57, 49, 63, 39, 64, 40, 65, 58, 66, 67, 68]. Such resilience measures would not only quantify resilience but could also inform designers and planners in advance how to best improve system resilience[69].

This paper develops a methodology for hetero-functional graph resilience analysis and demonstrates it on a convergent system-of-systems. In that regards, it seeks to address the recognized need for resilience in systems-of-systems[70] as a specialized class of engineering systems. It also seeks to use the Systems Modeling Language[71, 72], model-based systems engineering[73] and Hetero-Functional Graph Theory (HFGT)[74, 75, 76] to overcome the convergence research challenges when constructing models and measures for systems resilience[68]. In addition to addressing this two-fold need, this work is in agreement with the developing majority view which divides the resilience property into two complementary aspects: a static “survival” property which measures the degree of performance after a disruption, and a dynamic “recovery” property which measures how quickly the performance returns to normal operation (Figure 1)[39, 40, 41, 42, 43, 44, 45, 46, 47]. This paper also strikes a middle ground between two complementary approaches to resilience measurement. In the first, many resilience measures depend on formal graph theoretic approaches. The choice of HFGT over formal graph theory allows the paper’s scope to expand from homo-functional engineering systems to hetero-functional engineering systems, and systems-of-systems more specifically. In the second, resilience measurement is often conducted via complex simulation packages. While HFGT facilitates a variety of engineering system simulation approaches, the model presented in this work is at a higher level of abstraction to facilitate decision-making earlier in the system life-cycle. This paper also generalizes a previous resilience measure based on HFGT[77, 78, 79, 80, 81] which demonstrated its convergence potential with applications in transportation, electric power, water distribution, and production systems. The resilience analysis presented here also benefits from recent theoretical and computational developments in HFGT[74, 75, 76, 82, 83, 84] that directly support the modeling and analysis of convergent systems-of-systems. To demonstrate the methodological developments, the resilience analysis is conducted on a hypothetical energy-water nexus system of moderate size.

This work considers system-of-systems as a type of engineering system and adopts both within its scope.

The remainder of this paper is organized as follows. Section II provides a background to graph theoretic preliminaries in terms of basic definitions, theorems, and limitations of formal graph theory and multi-layer networks. Next, the quantification of resilience is recognized as an indirect measurement process depicted in Fig. 2. Consequently, Sec. III introduces the hetero-functional graph theory model and its constituent measureables and measurement methods. Sec. IV then uses this model to develop resilience measures for convergent systems-of-systems. These developments are then demonstrated on a hypothetical energy-water nexus system as a type of systems-of-systems. Finally, Section VI concludes the work.

As mentioned in the introduction, many works in the resilience measurement literature have been based on graph theory[39, 40, 41, 42, 43, 44, 45, 46, 47]. A number of basic definitions and theorems from this field are introduced to support the remainder of the discussion.

While for decades, graph theory has presented a useful abstraction across many applications, it has limitations in the systems engineering of convergent systems-of-systems. Graph theory, as it is traditionally applied, focuses primarily on an abstracted model of a system’s form; neglecting an explicit description of system’s function[1, 91]. Newman lists common applications of (formal) graph theory in Table I. In all cases, nodes and edges in a formal graph represents nouns; with nodes typically representing point objects in space and edges representing line objects. The system function, what a system does, in terms of verbal phrases, has been entirely omitted from the explicit statement of the formal graph and any understanding of the system’s function is implicit. Consequently, all of the applications listed in Table I describe homo-functional engineering systems where operands (of some specific type) are transported between physical locations. While transportation processes that account for movement from one location to another are fundamentally different, ultimately, they are of the same class or type. Thus, it is less than clear how formal graph theory may be applied to convergent systems-of-systems that are of a fundamentally transformative nature with multiple operands. As convergent systems-of-systems are hetero-functional (i.e. include functions and operands of many types), formal graph theory may impede rigorous approaches where resilience can be engineered into the system.

To address the inherent complexity in many engineering systems, the field of network science has generalized formal graphs into multi-layer networks[92, 93]. In a recent comprehensive review Kivela et. al [93] write:

“The study of multi-layer networks $\ldots$ has become extremely popular. Most real and engineered systems include multiple subsystems and layers of connectivity and developing a deep understanding of multi-layer systems necessitates generalizing ‘traditional’ graph theory. Ignoring such information can yield misleading results, so new tools need to be developed. One can have a lot of fun studying ‘bigger and better’ versions of the diagnostics, models and dynamical processes that we know and presumably love – and it is very important to do so but the new ‘degrees of freedom’ in multi-layer systems also yield new phenomena that cannot occur in single-layer systems. Moreover, the increasing availability of empirical data for fundamentally multi-layer systems amidst the current data deluge also makes it possible to develop and validate increasingly general frameworks for the study of networks.

$\ldots$ Numerous similar ideas have been developed in parallel, and the literature on multi-layer networks has rapidly become extremely messy. Despite a wealth of antecedent ideas in subjects like sociology and engineering, many aspects of the theory of multi-layer networks remain immature, and the rapid onslaught of papers on various types of multilayer networks necessitates an attempt to unify the various disparate threads and to discern their similarities and differences in as precise a manner as possible.

$\ldots$ [The multi-layer network community] has produced an equally immense explosion of disparate terminology, and the lack of consensus (or even generally accepted) set of terminology and mathematical framework for studying is extremely problematic.” In addition to the above limitations, Kivela et. al showed that all of the reviewed works have exhibited at least one of eight different types of modeling constraints[93]. To demonstrate the consequences of these modeling limitations, the HFGT text[74] developed a small, but highly heterogeneous, hypothetical test case system that exhibited all eight of the modeling limitations identified by Kivela et. al. Consequently, none of the multi-layer network models identified by Kivela et. al. would be able to model such a hypothetical test case. In contrast, a complete HFGT analysis of this hypothetical test case was demonstrated in the aforementioned text[74]. To follow up this result, the tensor formulation of hetero-functional graph theory proved that multi-layer networks are neither ontologically lucid nor complete[75].

Hetero-functional graph theory makes its connection to human language explicit through a set of system resources $R$ as subjects, a set of system processes $P$ as predicates, and a set of operands $L$ as their constituent objects.

Hetero-functional graph theory further recognizes that there are inherent differences within the set of resources as well as within the set of processes. Therefore, as shown in Fig. 3, classifications of these sets of resources and sets of processes are introduced. $R=M\cup B\cup H$ where $M$ is the set of transformation resources, $B$ is the set of independent buffers, and $H$ is the set of transportation resources. Furthermore, the set of buffers $B_{S}=M\cup B$ is introduced for later discussion. Similarly, $P=P_{\mu}\cup P_{\bar{\eta}}$ where $P_{\mu}$ is the set of transformation processes and $P_{\bar{\eta}}$ is the set of refined transportation processes. The latter, in turn, is determined from the Cartesian product (❌) of the set of transportation processes $P_{\eta}$ and the set of holding processes $P_{\gamma}$. $P_{\bar{\eta}}=P_{\gamma}\mbox{{\char 14\relax}}P_{\eta}$. Further explanation of HFGT meta-architecture and its taxonomies of processes and resources can be found in [74].

System processes can be allocated to system resources to form subject+verb+object sentences called system capabilities.

Every filled element of the system concept indicates a system capability (Defn. LABEL:defn:capability) of the form: “Resource $r_{v}$ does process $p_{w}$”. The system constraints matrix limits the availability of capabilities in the system knowledge base to create the system concept $A_{S}$. Importantly, in the next section, the set of capabilities ${\cal E}_{S}$ become the nodes of a hetero-functional graph adjacency matrix.

As the system concept $A_{S}$ is very sparse, it is often computationally useful to to introduce a (non-unique) projection operator $\mathds{P}_{S}$ that eliminates this sparsity by projecting the system knowledge base onto a one’s vector[74, 75, 76].

where $()^{V}$ is shorthand for matrix vectorization (i.e. $vec()$). In such a case, a system capability $\epsilon_{wv}\in{\cal E}_{S}$ becomes more straightforwardly labelled by the index $\psi\in\left[1,\dots,|{\cal E}_{S}|\right]$.

Once the system capabilities ${\cal E}_{S}$ have been defined within the system concept $A_{S}$, they can be related to one another through the hetero-functional incidence tensor and subsequently simulated with the engineering system net. The (third-order) hetero-functional hetero-functional incidence tensor $\widetilde{\cal M}_{\rho}$ describes the structural relationships between the physical capabilities ${\cal E}_{S}$, the system operands $L$, and the system buffers $B_{S}$.

In order to facilitate matrix-based calculation, the third-order hetero-functional incidence tensor $\widetilde{\cal M}_{\rho}$ can be matricized into its associated second order form $\widetilde{M}_{\rho}$ (where the first two dimensions are combined into a single dimension). The resulting matrix has a size of $|{\cal L}||B_{S}|\times|\cal{E_{S}}|$[75]. The underlying physical intuition provides each buffer $b_{s_{y}}\in B_{S}$ with $|{\cal L}|$ places (i.e. bins or shelves) for each operand at that buffer. These $|{\cal L}||B_{S}|$ places form a bipartite graph with the system’s physical capabilities ${\cal E_{S}}$.

Consequently, the supply, demand, transportation, storage, transformation, assembly, and disassembly of multiple operands in distinct locations over time can be described by an Engineering System Net and its associated State Transition Function[83].

The construction of the second-order hetero-functional incidence matrix $\widetilde{M}_{\rho}=\widetilde{M}_{\rho}^{+}+\widetilde{M}_{\rho}^{-}$ facilitates the creation of a hetero-functional adjacency matrix $A_{\rho}$ to represent the feasible pairwise sequences of capabilities[74, 75, 76].

In addition to identifying the potential for multiple operands (Defn. 11) in a system-of-systems, hetero-functional graph theory recognizes that each operand may have a behavior whose state that evolves in time. In the case of commodities, the operand may simply come in and out of existence (e.g. by virtue of a chemical process). In more complex products, raw material may be transformed into work-in-progress, and then again into final products. Operands may also represent services at various stages of delivery. Finally, operands may also represent complex services that consist of multiple operands, products and services and their associated state evolution. The state evolution of each operand $l_{i}\in{\cal L}$ is described by an Operand Net ${\cal N}_{l_{i}}$ and its associated state transition function $\Phi_{l_{i}}()$.

Finally, hetero-functional graph theory recognizes that any given transition in an operand net cannot be realized without the execution of a corresponding transition in the engineering system net. This correspondence is described by the operand-capability feasibility matrix.

From Theorem 1, the number of k-capability paths through a hetero-functional graph between an arbitrary pair of capabilities is given by $\widetilde{A}_{Pk}=\widetilde{A}_{\rho}^{(k-1)}$ where $\widetilde{A}_{\rho}$ is the projected hetero-functional adjacency matrix (Defn. 20). As self-loops are assumed not to contribute to resilience, the number of simple k-capability paths (i.e. without loops) between an arbitrary pair of capabilities $\widetilde{A}_{Pk}$ is calculated recursively from Theorem 2.

In the context of resilience measurement, the calculation of $\widetilde{A}_{Pk}$ must be generalized so as to include the possibility that some capabilities may not be available at a given time. Consequently,

where the projected system constraint matrix $\widetilde{K_{S}}$ (Defn. 15) introduces a binary availability condition to the formulation, $\neg$ is Boolean NOT, and $()^{V}$ is matrix vectorization (i.e. $vec()$).

Next, it is important to recognize that a given operand $l_{i}\in{\cal L}$ (Defn. 11) may not require all available capabilities in a hetero-functional graph. As an operand net $N_{l_{i}}$ (Defn. 21) is executed, it introduces a sequence of operand net firing vectors $U_{l_{i}}[k]$. These, in turn, by Eq. 28, must find a feasible correspondence with the engineering system net firing vectors $U_{S}[k]$. Therefore, the engineering system net firing vectors in binary form $bi(U_{S}[k])$ can be used to select out relevant parts of the hetero-functional graph. Consequently, the calculation of $\widetilde{A}_{Pk}$ must be further generalized to account for the applicability to a given operand $l_{i}$.

This calculation of $\widetilde{A}_{Pk}$ requires the determination of the firing operand net vectors $U_{l_{i}}[k]$ such that it completes its behavior in a pre-specified number of steps $K$. In many cases, operand nets either have a small size or simple topology that lend themselves to determining these firing vectors by inspection or by simple forward or backward scheduling heuristics. However, in the general case of a complex operand net topology, a mixed integer program must be solved.

where the objective function in Eq. 36 maximizes the number of operand net transitions fired over time, Eq. 37 is the first half of the operand net state transition function that imposes a non-negativity firing condition, and Eq. 38 is the second half of the operand net state transition function. The initial condition on $Q_{S_{l_{i}}}$ in Eq. 39 ensures that there is a large number of tokens in the postset places of the initial transition $\epsilon_{x1}$. These tokens serve to enable the evolution of the operand net through Eq. 37. (Note that, $e_{x1}$ is the $x_{1}^{th}$ elementary basis vector of appropriate size.). Furthermore, Eq. 40 ensures that the initial transition is not fired after the first time step. Finally, because the system constraints matrix limits the nonzero elements of the engineering system net firing vectors (via Eq. 20), and they, in turn, evolve the operand net firing vectors (via Eq. 27), there is an upper bound on the operand net firing vectors in Eq. 41.

It is important to recognize that operand nets may take an arbitrary topology. Whereas earlier hetero-functional graph theory works on resilience[77, 78, 79, 80, 81] required operands to have a state evolution described by a single sequence of events (or transitions), the method advanced here allows for operands to have an arbitrary state evolution. Consequently, operands nets may describe complex operands (i.e. products and services) composed of more basic operands that undergo assembly (i.e. joining) and disassembly (i.e. disjoining). As the state of such a complex operand evolves, certain transitions of its operand net may be executed simultaneously (i.e. in parallel). The resulting operand net firing vectors $U_{l_{i}}[k]$ may each contain more than a single nonzero element at a given moment $k$. This parallelism is then reflected as multiple nonzero elements in the engineering system net firing vectors $U_{S}[k]$. Additionally, it is possible that there are multiple capabilities that realize a given transition in a given operand. Such a condition is reflected by a multiple nonzero elements in a given row of the operand-capability feasibility matrix $\widetilde{\Lambda_{i}}$. Therefore, the plurality of nonzero elements in $U_{S}[k]$ is driven by the parallelism in $U_{l_{i}}[k]$ and the multiple feasibility conditions in $\widetilde{\Lambda_{i}}$. In such a manner, the calculation of $\widetilde{A}_{Pk}$ enumerates the number of k-capability paths through a hetero-functional graph for an operand net, even when the operand-net itself can take an arbitrary topology and not just that of a single sequence of events.

To complete the calculation of path enumeration in engineering systems, it is important to recognize that the total number of paths depends on their length; from length 2 up to a prespecified number $K$ of capabilities.

In the context of this work, the performance of an engineering system depends purely on its static structure. Consider an operand $l_{i}$, that is being delivered by an engineering system through a path that begins with capability $\epsilon_{\psi_{1}}$ and ends with capability $\epsilon_{\psi_{2}}$. If a quantity of this operand $Q_{i}(\psi_{1},\psi_{2})$ is delivered between this pair of capabilities $(\epsilon_{\psi_{1}},\epsilon_{\psi_{1}})$, then the associated performance of the engineering system is given by[77, 78, 79, 80, 81]:

Here, it is assumed that the existence of such a delivery path, rather than the number of such delivery paths, is sufficient for the delivery of the entire quantity $Q_{i}(\psi_{1},\psi_{2})$ of the operand $l_{i}$. As such, it assumes that each path is not capacity limited.

The above result can be generalized to account for the flow of all operands $l_{i}\in L$ between any pair of capabilities in the engineering system[77, 78, 79, 80, 81].

where $c_{i}$ is a measure of value of the $i^{th}$ operand such as utility, cost or profit that harmonizes the units of all $Q_{i}$. Eq. 45, when taken in the context of Eq. 43, shows the direct dependence of the performance of an engineering system on its structure as quantified by the choice of operand, its hetero-functional adjacency matrix $A_{\rho}$ and its system constraints matrix $K_{S}$. Consequently, it is useful to write the engineering performance of an engineering systemin terms of these three quantities: $EP(L,A_{\rho},K_{S})$.

The actual engineering resilience (AER) with respect to a particular disruption that takes the system through the transformation: $(L_{0},A_{\rho 0},K_{S0})\rightarrow(L,A_{\rho},K_{S})$ can now be defined straightforwardly[77, 78, 79, 80, 81].

This actual engineering resilience measure benefits from the binary function $bi()$. As expected, engineering systems that exhibit some path redundancy for their services will not suffer from performance degradation. Indeed, for many engineering managers, path redundancy may be viewed as unnecessary luxury, or a costly inefficiency, when the sole focus is to deliver products and services through an optimal delivery path. That said, the $bi()$ also hides the effect of redundancy elimination caused by successive disruptions and so is not the most accurate predictor of the engineering system’s “structural health” or vulnerability towards future disruptions.

To address the limitations of the actual engineering resilience measure, a latent engineering resilience measure is proposed[77, 78, 79, 80, 81].

where again the number of paths for an operand $l_{i}$ through hetero-functional graph adjacency matrix $A_{Pi}$ is written explicitly in terms of its dependency on the system constraints matrix $K_{S}$. Here, the LER measure degrades gracefully with the transformation $(L_{0},A_{\rho 0},K_{S0})\rightarrow(L,A_{\rho},K_{S})$ because of the ratio of actual enumerated paths to the prior enumerated paths. Furthermore, it is important to recognize that the paths through a hetero-functional adjacency matrix often grows exponentially with number of steps in the path. Conceptually, this is because the choice of paths through the hetero-functional graph has a corresponding decision-tree with the same number of end-nodes as the number of enumerated paths. Consequently, it is often useful to report the $LER$ measure as $log(LER)$ [81] so as to understand how a given disruption can close off one or more large branches of this decision-tree and leave others intact.

Finally, Fig. 1 describes the resilience of an engineering system by its engineering performance as it survives an initial disruption and then bounces back to a new equilibrium level. In this context, the AER and LER measures provided above are static resilience (i.e. survivability) measures[77, 78, 79, 80, 81]. They correspond to the engineering performance of an engineering system at a single point in time; presumably after a disruption. A dynamic resilience measure must, therefore, recognize that the engineering performance will begin to rise again with restorative actions[115] that evolve $(L[t],A_{\rho}[t],K_{S}[t])$ in time. Constraints within $K_{S}[t]$ may be removed, new capabilities in $A_{\rho}[k]$ may be added, and new operands in the form of products and services in $L[t]$ may be added as well. Consequently, and much like other literature on dynamic resilience[116], a dynamic measure of actual and latent engineering resilience integrates the static measures over time.