Network controllability

Last updated January 06, 2024

Controlling a simple network. YYL1.png — Controlling a simple network.

Network controllability concerns the structural controllability of a network. Controllability describes our ability to guide a dynamical system from any initial state to any desired final state in finite time, with a suitable choice of inputs. This definition agrees well with our intuitive notion of control. The controllability of general directed and weighted complex networks has recently been the subject of intense study by a number of groups in wide variety of networks, worldwide. Recent studies by Sharma et al.^[1] on multi-type biological networks (gene–gene, miRNA–gene, and protein–protein interaction networks) identified control targets in phenotypically characterized Osteosarcoma showing important role of genes and proteins responsible for maintaining tumor microenvironment.

Background

Consider the canonical linear time-invariant dynamics on a complex network ${\dot {\mathbf {X} }}(t)=\mathbf {A} \cdot \mathbf {X} (t)+\mathbf {B} \cdot \mathbf {u} (t)$ where the vector $\mathbf {X} (t)=(x_{1}(t),\cdots ,x_{N}(t))^{\mathrm {T} }$ captures the state of a system of $N$ nodes at time $t$ . The $N\times N$ matrix $\mathbf {A}$ describes the system's wiring diagram and the interaction strength between the components. The $N\times M$ matrix $\mathbf {B}$ identifies the nodes controlled by an outside controller. The system is controlled through the time dependent input vector $\mathbf {u} (t)=(u_{1}(t),\cdots ,u_{M}(t))^{\mathrm {T} }$ that the controller imposes on the system. To identify the minimum number of driver nodes, denoted by $N_{\mathrm {D} }$ , whose control is sufficient to fully control the system's dynamics, Liu et al.^[2] attempted to combine the tools from structural control theory, graph theory and statistical physics. They showed^[2] that the minimum number of inputs or driver nodes needed to maintain full control of the network is determined by the maximum-cardinality matching in the network. From this result, an analytical framework, based on the in–out degree distribution, was developed to predict $n_{\mathrm {D} }=N_{\mathrm {D} }/N$ for scale-free and Erdős–Rényi random graphs.^[2] However, more recently it has been demonstrated that network controllability (and other structure-only methods that use exclusively the connectivity of a graph, $\mathbf {A}$ , to simplify the underlying dynamics), both undershoot and overshoot the number and which sets of driver nodes best control network dynamics, highlighting the importance of redundancy (e.g. canalization) and non-linear dynamics in determining control.^[3]

It is also notable that Liu's et al. formulation^[2] would predict same values of ${n_{\mathrm {D} }}$ for a chain graph and for a weak densely connected graph. Obviously, both these graphs have very different in and out degree distributions. A recent unpublished work^[4] questions whether degree, which is a purely local measure in networks, would completely describe controllability and whether even slightly distant nodes would have no role in deciding network controllability. Indeed, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of ${n_{\mathrm {D} }}^{real}$ and ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ calculated by Liu et al.^[2] is notable. If controllability is decided mainly by degree, why are ${n_{\mathrm {D} }}^{real}$ and ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ so different for many real world networks? They argued^[2] (arXiv:1203.5161v1) that this might be due to the effect of degree correlations. However, it has been shown^[4] that network controllability can be altered only by using betweenness centrality and closeness centrality, without using degree (graph theory) or degree correlations at all.

A schematic diagram shows the control of a directed network. For a given directed network (Fig. a), one calculates its maximum matching: a largest set of edges without common heads or tails. The maximum matching will compose of a set of vertex-disjoint directed paths and directed cycles (see red edges in Fig.b). If a node is a head of a matching edge, then this node is matched (green nodes in Fig.b). Otherwise, it is unmatched (white nodes in Fig.b). Those unmatched nodes are the nodes one needs to control, i.e. the driver nodes. By injecting signals to those driver nodes, one gets a set of directed path with starting points being the inputs (see Fig.c). Those paths are called "stems". The resulting digraph is called U-rooted factorial connection. By "grafting" the directed cycles to those "stems", one gets "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem, since there is a cacti structure spanning the controlled network (see Fig.e), the system is controllable. The cacti structure (Fig.d) underlying the controlled network (Fig.e) is the "skeleton" for maintaining controllability. YYL2.pdf — A schematic diagram shows the control of a directed network. For a given directed network (Fig. a), one calculates its maximum matching: a largest set of edges without common heads or tails. The maximum matching will compose of a set of vertex-disjoint directed paths and directed cycles (see red edges in Fig.b). If a node is a head of a matching edge, then this node is matched (green nodes in Fig.b). Otherwise, it is unmatched (white nodes in Fig.b). Those unmatched nodes are the nodes one needs to control, i.e. the driver nodes. By injecting signals to those driver nodes, one gets a set of directed path with starting points being the inputs (see Fig.c). Those paths are called "stems". The resulting digraph is called U-rooted factorial connection. By "grafting" the directed cycles to those "stems", one gets "buds". The resulting digraph is called the cacti (see Fig.d). According to the structural controllability theorem, since there is a cacti structure spanning the controlled network (see Fig.e), the system is controllable. The cacti structure (Fig.d) underlying the controlled network (Fig.e) is the "skeleton" for maintaining controllability.

Structural controllability

The concept of the structural properties was first introduced by Lin (1974)^[5] and then extended by Shields and Pearson (1976)^[6] and alternatively derived by Glover and Silverman (1976).^[7] The main question is whether the lack of controllability or observability are generic with respect to the variable system parameters. In the framework of structural control the system parameters are either independent free variables or fixed zeros. This is consistent for models of physical systems since parameter values are never known exactly, with the exception of zero values which express the absence of interactions or connections.

Maximum matching

In graph theory, a matching is a set of edges without common vertices. Liu et al.^[2] extended this definition to directed graph, where a matching is a set of directed edges that do not share start or end vertices. It is easy to check that a matching of a directed graph composes of a set of vertex-disjoint simple paths and cycles. The maximum matching of a directed network can be efficiently calculated by working in the bipartite representation using the classical Hopcroft–Karp algorithm, which runs in O(E√N) time in the worst case. For undirected graph, analytical solutions of the size and number of maximum matchings have been studied using the cavity method developed in statistical physics.^[8] Liu et al.^[2] extended the calculations for directed graph.

By calculating the maximum matchings of a wide range of real networks, Liu et al.^[2] asserted that the number of driver nodes is determined mainly by the networks degree distribution $P(k_{\mathrm {in} },k_{\mathrm {out} })$ . They also calculated the average number of driver nodes for a network ensemble with arbitrary degree distribution using the cavity method. It is interesting that for a chain graph and a weak densely connected graph, both of which have very different in and out degree distributions; the formulation of Liu et al.^[2] would predict same values of ${n_{\mathrm {D} }}$ . Also, for many real-word networks, namely, food webs, neuronal and metabolic networks, the mismatch in values of ${n_{\mathrm {D} }}^{real}$ and ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ calculated by Liu et al.^[2] is notable. If controllability is decided purely by degree, why are ${n_{\mathrm {D} }}^{real}$ and ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ so different for many real world networks? It remains open to scrutiny whether "control robustness" in networks is influenced more by using betweenness centrality and closeness centrality ^[4] over degree-based metrics.

While sparser graphs are more difficult to control,^[2]^[4] it would obviously be interesting to find whether betweenness centrality and closeness centrality ^[4] or degree heterogeneity^[2] plays a more important role in deciding controllability of sparse graphs with almost-similar degree distributions.

Control of composite quantum systems and algebraic graph theory

A control theory of networks has also been developed in the context of universal control for composite quantum systems, where subsystems and their interactions are associated to nodes and links, respectively.^[9] This framework permits formulation of Kalman's criterion with tools from algebraic graph theory via the minimum rank of a graph and related notions.^[10]^[11]

Related Research Articles

<span class="mw-page-title-main">Navier–Stokes equations</span> Equations describing the motion of viscous fluid substances

The Navier–Stokes equations are partial differential equations which describe the motion of viscous fluid substances. They were named after French engineer and physicist Claude-Louis Navier and the Irish physicist and mathematician George Gabriel Stokes. They were developed over several decades of progressively building the theories, from 1822 (Navier) to 1842–1850 (Stokes).

Controllability is an important property of a control system and plays a crucial role in many control problems, such as stabilization of unstable systems by feedback, or optimal control.

In vector calculus, the divergence theorem, also known as Gauss's theorem or Ostrogradsky's theorem, is a theorem which relates the flux of a vector field through a closed surface to the divergence of the field in the volume enclosed.

In mathematics, the Legendre transformation, first introduced by Adrien-Marie Legendre in 1787 when studying the minimal surface problem, is an involutive transformation on real-valued functions that are convex on a real variable. Specifically, if a real-valued multivariable function is convex on one of its independent real variables, then the Legendre transform with respect to this variable is applicable to the function.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

In multivariable calculus, the implicit function theorem is a tool that allows relations to be converted to functions of several real variables. It does so by representing the relation as the graph of a function. There may not be a single function whose graph can represent the entire relation, but there may be such a function on a restriction of the domain of the relation. The implicit function theorem gives a sufficient condition to ensure that there is such a function.

<span class="mw-page-title-main">Holonomy</span> Concept in differential geometry

In differential geometry, the holonomy of a connection on a smooth manifold is a general geometrical consequence of the curvature of the connection measuring the extent to which parallel transport around closed loops fails to preserve the geometrical data being transported. For flat connections, the associated holonomy is a type of monodromy and is an inherently global notion. For curved connections, holonomy has nontrivial local and global features.

In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a specialization of the tensor product from vectors to matrices and gives the matrix of the tensor product linear map with respect to a standard choice of basis. The Kronecker product is to be distinguished from the usual matrix multiplication, which is an entirely different operation. The Kronecker product is also sometimes called matrix direct product.

Belief propagation, also known as sum–product message passing, is a message-passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. Belief propagation is commonly used in artificial intelligence and information theory, and has demonstrated empirical success in numerous applications, including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability.

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

In graph theory, eigenvector centrality is a measure of the influence of a node in a network. Relative scores are assigned to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes. A high eigenvector score means that a node is connected to many nodes who themselves have high scores.

In physics, a quantum vortex represents a quantized flux circulation of some physical quantity. In most cases, quantum vortices are a type of topological defect exhibited in superfluids and superconductors. The existence of quantum vortices was first predicted by Lars Onsager in 1949 in connection with superfluid helium. Onsager reasoned that quantisation of vorticity is a direct consequence of the existence of a superfluid order parameter as a spatially continuous wavefunction. Onsager also pointed out that quantum vortices describe the circulation of superfluid and conjectured that their excitations are responsible for superfluid phase transitions. These ideas of Onsager were further developed by Richard Feynman in 1955 and in 1957 were applied to describe the magnetic phase diagram of type-II superconductors by Alexei Alexeyevich Abrikosov. In 1935 Fritz London published a very closely related work on magnetic flux quantization in superconductors. London's fluxoid can also be viewed as a quantum vortex.

<span class="mw-page-title-main">Euclidean plane</span> Geometric model of the planar projection of the physical universe

In mathematics, a Euclidean plane is a Euclidean space of dimension two, denoted $E 2$ . It is a geometric space in which two real numbers are required to determine the position of each point. It is an affine space, which includes in particular the concept of parallel lines. It has also metrical properties induced by a distance, which allows to define circles, and angle measurement.

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

Algebraic signal processing (ASP) is an emerging area of theoretical signal processing (SP). In the algebraic theory of signal processing, a set of filters is treated as an (abstract) algebra, a set of signals is treated as a module or vector space, and convolution is treated as an algebra representation. The advantage of algebraic signal processing is its generality and portability.

Artificial neural networks are combinations of multiple simple mathematical functions that implement more complicated functions from (typically) real-valued vectors to real-valued vectors. The spaces of multivariate functions that can be implemented by a network are determined by the structure of the network, the set of simple functions, and its multiplicative parameters. A great deal of theoretical work has gone into characterizing these function spaces.

Stokes' theorem, also known as the Kelvin–Stokes theorem after Lord Kelvin and George Stokes, the fundamental theorem for curls or simply the curl theorem, is a theorem in vector calculus on $. Given a vector field, the theorem relates the integral of the curl of the vector field over some surface, to the line integral of the vector field around the boundary of the surface. The classical theorem of Stokes can be stated in one sentence: The line integral of a vector field over a loop is equal to its curl through the enclosed surface. It is illustrated in the figure, where the direction of positive circulation of the bounding contour \partialΣ, and the direction n of positive flux through the surface Σ, are related by a right-hand-rule. For the right hand the fingers circulate along \partialΣ and the thumb is directed along n .$

In the study of artificial neural networks (ANNs), the neural tangent kernel (NTK) is a kernel that describes the evolution of deep artificial neural networks during their training by gradient descent. It allows ANNs to be studied using theoretical tools from kernel methods.

In computer science, an e-graph is a data structure that stores an equivalence relation over terms of some language.

A graph neural network (GNN) belongs to a class of artificial neural networks for processing data that can be represented as graphs.

References

↑ Sharma, Ankush; Cinti, Caterina; Capobianco, Enrico (2017). "Multitype Network-Guided Target Controllability in Phenotypically Characterized Osteosarcoma: Role of Tumor Microenvironment". Frontiers in Immunology. 8: 918. doi: 10.3389/fimmu.2017.00918 . ISSN 1664-3224. PMC 5536125 . PMID 28824643.
1 2 3 4 5 6 7 8 9 10 11 12 13 Liu, Yang-Yu; Slotine, Jean-Jacques; Barabási, Albert-László (2011). "Controllability of complex networks". Nature. Springer Science and Business Media LLC. 473 (7346): 167–173. Bibcode:2011Natur.473..167L. doi:10.1038/nature10011. ISSN 0028-0836. PMID 21562557. S2CID 4334171.
↑ Gates, Alexander J.; Rocha, Luis M. (2016-04-18). "Control of complex networks requires both structure and dynamics". Scientific Reports. Springer Science and Business Media LLC. 6 (1): 24456. arXiv: 1509.08409 . Bibcode:2016NatSR...624456G. doi: 10.1038/srep24456 . ISSN 2045-2322. PMC 4834509 . PMID 27087469.
1 2 3 4 5 Banerjee, SJ; Roy, S (2012). "Key to Network Controllability". arXiv: 1209.3737 [physics.soc-ph].
1 2 C.-T. Lin, IEEE Trans. Auto. Contr.19 (1974).
↑ R. W. Shields and J. B. Pearson, IEEE Trans. Auto. Contr.21 (1976).
↑ K. Glover and L. M. Silverman, IEEE Trans. Auto. Contr.21 (1976).
↑ L. Zdeborová and M. Mezard, J. Stat. Mech.05 (2006).
↑ Burgarth, Daniel; Giovannetti, Vittorio (2007-09-05). "Full Control by Locally Induced Relaxation". Physical Review Letters. 99 (10): 100501. arXiv: 0704.3027 . Bibcode:2007PhRvL..99j0501B. doi:10.1103/physrevlett.99.100501. ISSN 0031-9007. PMID 17930379. S2CID 6560929.
↑ Burgarth, Daniel; D'Alessandro, Domenico; Hogben, Leslie; Severini, Simone; Young, Michael (2013). "Zero forcing, linear and quantum controllability for systems evolving on networks". IEEE Transactions on Automatic Control. 58 (9): 2349–2354. arXiv: 1111.1475 . doi:10.1109/TAC.2013.2250075. MR 3101617. S2CID 6939245.
↑ S. O'Rourke, B. Touri, https://arxiv.org/abs/1511.05080 Archived 2016-10-18 at the Wayback Machine .

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Sharma, Ankush; Cinti, Caterina; Capobianco, Enrico (2017). "Multitype Network-Guided Target Controllability in Phenotypically Characterized Osteosarcoma: Role of Tumor Microenvironment". Frontiers in Immunology. 8: 918. doi: 10.3389/fimmu.2017.00918 . ISSN 1664-3224. PMC 5536125 . PMID 28824643.

[Liu-Nature-11-2] 1 2 3 4 5 6 7 8 9 10 11 12 13 Liu, Yang-Yu; Slotine, Jean-Jacques; Barabási, Albert-László (2011). "Controllability of complex networks". Nature. Springer Science and Business Media LLC. 473 (7346): 167–173. Bibcode:2011Natur.473..167L. doi:10.1038/nature10011. ISSN 0028-0836. PMID 21562557. S2CID 4334171.

[gates_rocha_scirep-3] Gates, Alexander J.; Rocha, Luis M. (2016-04-18). "Control of complex networks requires both structure and dynamics". Scientific Reports. Springer Science and Business Media LLC. 6 (1): 24456. arXiv: 1509.08409 . Bibcode:2016NatSR...624456G. doi: 10.1038/srep24456 . ISSN 2045-2322. PMC 4834509 . PMID 27087469.

[Arxiv_Close_Betw-4] 1 2 3 4 5 Banerjee, SJ; Roy, S (2012). "Key to Network Controllability". arXiv: 1209.3737 [physics.soc-ph].

[Lin-74-5] 1 2 C.-T. Lin, IEEE Trans. Auto. Contr.19 (1974).

[Shields-76-6] R. W. Shields and J. B. Pearson, IEEE Trans. Auto. Contr.21 (1976).

[Glover-76-7] K. Glover and L. M. Silverman, IEEE Trans. Auto. Contr.21 (1976).

[Zdeborova-06-8] L. Zdeborová and M. Mezard, J. Stat. Mech.05 (2006).

[BG-07-9] Burgarth, Daniel; Giovannetti, Vittorio (2007-09-05). "Full Control by Locally Induced Relaxation". Physical Review Letters. 99 (10): 100501. arXiv: 0704.3027 . Bibcode:2007PhRvL..99j0501B. doi:10.1103/physrevlett.99.100501. ISSN 0031-9007. PMID 17930379. S2CID 6560929.

[BDHSY-13-10] Burgarth, Daniel; D'Alessandro, Domenico; Hogben, Leslie; Severini, Simone; Young, Michael (2013). "Zero forcing, linear and quantum controllability for systems evolving on networks". IEEE Transactions on Automatic Control. 58 (9): 2349–2354. arXiv: 1111.1475 . doi:10.1109/TAC.2013.2250075. MR 3101617. S2CID 6939245.

[OT-15-11] S. O'Rourke, B. Touri, https://arxiv.org/abs/1511.05080 Archived 2016-10-18 at the Wayback Machine .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]