PaperlayerView exact revision on arXiv

Source-linked AI summary

Controllability Metrics, Limitations and Algorithms for Complex Networks

Fabio Pasqualetti, Sandro Zampieri, Francesco Bullo

arXiv:1308.1201v3eess.SYmath.OCphysics.data-an

TL;DR

The paper addresses how to select control nodes and design inputs that steer complex networks to target states. It measures controllability through worst-case energy, derives energy–node-count bounds, and proposes a partition-based open-loop distributed strategy. The results identify exponential energy growth with few control nodes, constant-energy regimes in certain networks, and cluster-dependent control in clustered networks.

  • Problem

    Controlling complex networks requires jointly selecting control nodes and designing inputs, while the relation between network topology and controllability remains largely unexplored.

  • Method

    The paper uses the smallest eigenvalue of the controllability Gramian, derives dynamics-dependent energy–node-count bounds, and develops a partition-based open-loop distributed control strategy.

  • Results

    For stable and symmetric networks, constant control-node counts can yield exponentially increasing energy, whereas certain networks achieve dimension-independent constant energy; clustered networks can reduce control to cluster properties and coupling strength.

  • Takeaways & Limitations

    Network topology, weights, clustering, and the number of control nodes jointly determine control difficulty, while the decoupled strategy offers a scalable distributed solution with performance guarantees.

Abstract

from arXiv · show

This paper studies the problem of controlling complex networks, that is, the joint problem of selecting a set of control nodes and of designing a control input to steer a network to a target state. For this problem (i) we propose a metric to quantify the difficulty of the control problem as a function of the required control energy, (ii) we derive bounds based on the system dynamics (network topology and weights) to characterize the tradeoff between the control energy and the number of control nodes, and (iii) we propose an open-loop control strategy with performance guarantees. In our strategy we select control nodes by relying on network partitioning, and we design the control input by leveraging optimal and distributed control techniques. Our findings show several control limitations and properties. For instance, for Schur stable and symmetric networks: (i) if the number of control nodes is constant, then the control energy increases exponentially with the number of network nodes, (ii) if the number of control nodes is a fixed fraction of the network nodes, then certain networks can be controlled with constant energy independently of the network dimension, and (iii) clustered networks may be easier to control because, for sufficiently many control nodes, the control energy depends only on the controllability properties of the clusters and on their coupling strength. We validate our results with examples from power networks, social networks, and epidemics spreading.

I. INTRODUCTION

The paper frames complex-network control as jointly choosing control nodes and designing inputs, then quantifies control difficulty through energy, derives topology-dependent tradeoffs, and proposes a scalable distributed strategy.

  • The control problem jointly selects control nodes and designs a control law to steer a network from the origin to a target state.
  • The paper uses worst-case control energy, quantified by the smallest eigenvalue of the controllability Gramian, as a network controllability metric.
  • It characterizes tradeoffs between control energy and the number of control nodes using network dynamics, including topology and weights.
  • For stable and symmetric networks, maintaining constant control energy requires the number of control nodes to grow linearly with network dimension.
  • The decoupled control strategy partitions the network, selects control nodes, and designs an open-loop distributed control law with performance guarantees.
  • Numerical examples from power networks, social networks, and epidemics report that the decoupled strategy outperforms existing techniques while remaining scalable and distributed.
  • The bounds and techniques apply to diagonalizable networks and become simpler and tighter for normal weighted adjacency matrices.

II. NETWORK MODEL AND PRELIMINARY RESULTS

The paper models network control through discrete-time linear dynamics, defines controllability via control nodes and full-rank reachability, and quantifies control difficulty using worst-case energy. It also illustrates that controllability can require exponentially increasing energy and contrasts alternative controllability metrics.

  • Network model: The network dynamics are discrete-time, linear, and time-invariant, with independently controlled nodes injecting control signals through an input matrix.
  • Network model: Controllability means steering the network from the zero state to any target configuration using external controls.
  • Controllability conditions: A network is controllable in T steps exactly when its controllability matrix has full row rank, equivalently when its controllability Gramian is positive definite.
  • Energy-based controllability: 2^-2n+2 is the smallest Gramian eigenvalue in a chain controlled at one node, so the required control energy grows exponentially with network size despite controllability.
  • Energy-based controllability: The smallest controllability-Gramian eigenvalue measures worst-case control difficulty, because small values imply very large energy for certain target states.
  • Alternative metrics: Trace(W^-1_K,T) measures average control energy, determinant measures reachable-state volume, and maximizing Trace(W_K,T) may fail to ensure controllability or good worst-case energy.

III. CONTROL NODES AND CONTROL ENERGY

The paper quantifies network controllability through worst-case control energy and derives bounds linking that energy to network dynamics and the number of control nodes. For stable symmetric networks, these bounds reveal exponential energy growth with fixed control-node counts and linear control-node requirements for bounded energy.

  • Control metric: Worst-case control energy measures the difficulty of steering a network from the origin to a target state.The paper relates this metric to the smallest eigenvalue of the controllability Gramian.
  • General bounds: Theorem 3.1 bounds the smallest Gramian eigenvalue using the eigenvalue distribution of A and the eigenvector-matrix condition number.Equivalently, it lower-bounds the worst-case energy required to reach arbitrary unit-norm states.
  • Scope and extensions: The bound applies as a performance limitation independently of the control strategy, although it can become conservative as ρ increases.The theorem also extends quantitatively to observability through the observability Gramian.
  • Stable symmetric networks: For stable symmetric networks, Corollary 3.2 provides sharper energy-versus-control-node bounds because the eigenvector matrix is orthonormal.Symmetry yields cond(V) = 1.
  • Asymptotic consequences: Constant control-node counts imply controllability energy grows at least exponentially with network size.This conclusion follows for stable and symmetric networks as n increases.
  • Asymptotic consequences: A fixed lower bound ε on the Gramian's smallest eigenvalue requires a control set whose size is at least Rεnµ.For stable symmetric networks, this becomes a linear requirement in the total number of nodes.

IV. DECOUPLED CONTROL OF COMPLEX NETWORKS

The proposed solution jointly selects control nodes and designs an open-loop control law by exploiting network structure. It targets scalability and guarantees that existing combinatorial or heuristic approaches do not generally provide.

  • IV. DECOUPLED CONTROL OF COMPLEX NETWORKS: The approach jointly selects control nodes and designs an open-loop control law amenable to distributed implementation.It exploits the network structure rather than treating node selection and control design separately.
  • IV. DECOUPLED CONTROL OF COMPLEX NETWORKS: Existing methods are often combinatorial and non-scalable or heuristic without guarantees on control energy.The proposed strategy is motivated by these limitations in large-network control-node selection.

A. Setup and definition of the decoupled control strategy

The decoupled strategy partitions an undirected network into clusters, selects boundary-inclusive control sets that make each cluster controllable, and combines local optimal inputs with inter-cluster feedback.

  • Network partitioning: The network is partitioned into N disjoint clusters, producing interconnected subsystem dynamics.Each cluster has its own internal matrix and control-input matrix.
  • Selection of the control nodes: Control sets must include every cluster's boundary nodes and make each local pair (Ai, Bi) controllable.Boundary nodes connect a cluster to nodes in other clusters.
  • Selection of the control nodes: Boundary nodes alone may not guarantee controllability of every cluster.Additional control nodes can therefore be required.
  • Partitioning limitation: The performance depends on the chosen partitioning scheme, and designing an optimal partitioning algorithm remains an open problem.The implementation only requires partitioning into strongly connected components, while the paper uses a Fiedler-eigenvector spectral method in Section V-A.
  • Decoupled control law: The decoupled control law requires a sufficiently large horizon so each local controllability Gramian is positive definite.It uses the minimum-energy input for each isolated cluster toward its component of the target state.
  • Implementation: Each cluster's open-loop signal depends only on local dynamics, while feedback signals are exchanged with neighboring cluster control centers.This supports distributed computation and scalable implementation.

B. Analysis of the decoupled control law

The decoupled law reaches the target through local minimum-energy controls and admits an energy bound determined by cluster controllability and interconnection gains. Under stable clusters, this bound can remain independent of total network size.

  • Analysis of the decoupled control law: The local minimum-energy inputs steer every cluster to its target component, so the full network reaches the target state.The resulting dynamics are a collection of decoupled subsystems.
  • Assumptions: The analysis assumes every cluster matrix Ai is Schur stable and leaves unstable networks for future investigation.For Schur-stable nonnegative A, the cluster matrices inherit stability and satisfy λmax(Ai) ≤ λmax(A).
  • Energy bound: Theorem 4.1 bounds the energy of the decoupled control law when boundary nodes are controlled, clusters are stable, and each local pair is controllable.The bound uses a local energy matrix and an L2 gains matrix.
  • Energy bound: Clustered-network controllability depends on isolated-cluster controllability through Λ and interconnection strength through Γ.The result explicitly separates local energy properties from coupling effects.
  • Network-size dependence: The decoupled control energy need not depend on total network dimension when the relevant interconnection gains remain bounded.Bounded network weights and node degrees are given as one condition ensuring bounded matrix norms.
  • Network-size dependence: The strategy is best suited to inherently clustered networks composed of weakly coupled components.Partition quality can therefore affect the resulting control-energy bound.

C. An example of network control via decoupled control law

The circulant-network example partitions nodes into equal-sized clusters and controls each cluster through its two boundary nodes. The resulting decoupled law can achieve constant-energy control as the network grows under this scaling.

  • Network construction: The network has n = nbN nodes partitioned into N clusters of nb nodes, with the first and last node of each cluster selected for control.Thus, the control set contains 2N boundary nodes.
  • Energy scaling: 2N control nodes and fixed cluster size yield constant energy for the decoupled control law as network cardinality grows.The number of control nodes grows with the number of clusters while cluster size remains fixed.
  • Energy scaling: Randomly selected control nodes do not maintain the constant-energy property as the network cardinality grows.
  • Energy scaling: With a fixed number of clusters and growing cluster size, the controllability-Gramian eigenvalue and bound (14) degrade at the same rate.Random control-node selection requires more energy in this regime.
  • Performance guarantee: For circulant networks, bound (14) captures constant-energy control of any unit-norm target state independently of network dimension.The decoupled control law achieves this performance in distributed form.

V. EXAMPLES OF CONTROL OF COMPLEX NETWORKS

The examples section evaluates the decoupled control law through partition-based node selection and comparisons with alternative control schemes. Its stated purpose is to assess effectiveness on complex networks.

  • Section purpose: The evaluation first selects control nodes using network partitioning, then compares the decoupled control law with alternative schemes.
  • Algorithm 1: Algorithm 1 takes a network G and a requested number of control nodes m, and outputs a control-node set K.
  • Algorithm 1: The algorithm begins with one trivial partition and no boundary nodes, then iteratively partitions clusters while fewer than m control nodes have been selected.
  • Algorithm 1: If partitioning produces too many controls, the algorithm removes boundary nodes from the last partition; if too few, it adds the remaining required nodes.

A. Selection of the control nodes

The paper selects control nodes by recursively partitioning a network through Fiedler eigenvectors and choosing partition boundaries, then uses modal controllability heuristics within clusters.

  • Partition-based selection: A connected network is split by the Fiedler eigenvector, and boundary nodes of recursively partitioned subnetworks are selected as control nodes.
  • Heuristic selection: The within-cluster heuristic selects nodes by maximizing the smallest controllability parameter φ_i for a specified cardinality k.
  • Heuristic selection: The parameter φ_i aggregates a node's controllability across all network modes, while small modal entries indicate poorly controllable modes from that node.
  • Computational aspect: The circulant-network maximization problem was numerically solved only for nb = 4 and N ∈ {2, . . . , 6} because of computational complexity.
  • Computational aspect: The heuristic can be solved by ordering φ_i values, with computational difficulty comparable to computing each cluster's eigenvectors.

B. Illustrative examples

The paper illustrates control of power, social, and epidemic networks using domain-specific dynamical models and numerical comparisons of control-node selections. The experiments report threshold effects and advantages for the decoupled control law.

  • Power network: The power-network model approximates linearized swing dynamics with a first-order equation and discretizes it using Euler accuracy h.
  • Social network: The social-network example constructs a consensus system on the Klavzar bibliography network by assigning random nonzero weights to its edges.
  • Consensus networks: Connected consensus networks have a unit eigenvalue, so infinite-horizon controllability is defined on the subspace orthogonal to the consensus space where A is Schur stable.
  • Example networks: The examples include the IEEE 118-bus power network, the 86-node Klavzar bibliography network, and the 105-node GD99c Pajek network.Figure 4 provides their network representations.
  • Epidemics spreading: The epidemic example discretizes an approximation of the N-intertwined SIS model, where infection can be controlled by distributing vaccines.
  • Epidemics spreading: In the unstable GD99c epidemic simulation, h = 10^-2 and the finite control horizon is n/2 control steps.
  • Numerical findings: The smallest Gramian eigenvalue rises abruptly beyond a control-node threshold, equivalently producing an abrupt decrease in control energy.
  • Computational scope: For large networks, replacing Fiedler partitioning with a linear-complexity method such as Louvain can make the overall method linear-complexity.The decoupled law then requires inversion only of local Gramians whose dimensions are independent of network cardinality.

VI. CONCLUSION

The paper measures network controllability through worst-case control energy, relates that energy to the number of control nodes and network dynamics, and proposes a partitioning-based strategy with performance guarantees. It identifies several directions for strengthening bounds, measures, partitioning, and controller extensions.

  • The smallest eigenvalue of the controllability Gramian measures worst-case control energy for steering the network to a target state.
  • The paper characterizes tradeoffs between the number of control nodes and control energy as a function of network dynamics.
  • The proposed strategy selects control nodes through network partitioning and provides performance guarantees.
  • Further work includes tighter network-dependent bounds, alternative controllability measures, efficient partitioning, and extensions to optimal H2 feedback controllers.

APPENDIX

The appendix derives a closed-form solution for selecting control nodes to maximize the controllability Gramian's trace in symmetric networks. The solution selects indices corresponding to the largest diagonal entries of the relevant matrix.

  • The appendix focuses on symmetric networks, while noting that analogous results hold for asymmetric networks.
  • The node-selection problem maximizes the trace of the controllability Gramian.
  • A solution is the set K* containing the indices of the m largest diagonal entries of the relevant matrix.
Loading 1308.1201v3…