Source-linked AI summary
Realistic Control of Network Dynamics
Sean P. Cornelius, William L. Kath, Adilson E. Motter
TL;DR
Complex networks can converge to undesirable states even when desirable stable states exist, while real interventions are constrained. The paper develops an iterative nonlinear-control framework that moves systems into target basins using admissible perturbations, and demonstrates network reprogramming and rescue applications, including cancer-signaling interventions and power-grid recovery.
Problem
The paper addresses how to steer a complex network from an undesirable state to a desired one when allowed interventions are constrained and the target is not directly accessible.
Method
The framework iteratively constructs physically admissible compensatory perturbations using network dynamics to move the system into the desired state’s basin of attraction.
Results
The method solved 100% of benchmark cases with existing compensatory perturbations, rescued 67% of 10,000 sampled pre-cancerous states, and controlled 27 of 43 failing power-grid cases.
Takeaways & Limitations
The framework supports network reprogramming and real-time rescue, with applications to associative memory, cancer-signaling intervention, and power-grid desynchronization.
Takeaways & Limitations
The approach addresses systems whose attraction basins lack general identification methods and assumes constrained perturbations represented by vector equalities and inequalities.
Abstract
from arXiv · showhide
The control of complex networks is of paramount importance in areas as diverse as ecosystem management, emergency response, and cell reprogramming. A fundamental property of networks is that perturbations to one node can affect other nodes, potentially causing the entire system to change behavior or fail. Here, we show that it is possible to exploit the same principle to control network behavior. Our approach accounts for the nonlinear dynamics inherent to real systems, and allows bringing the system to a desired target state even when this state is not directly accessible due to constraints that limit the allowed interventions. Applications show that this framework permits reprogramming a network to a desired task as well as rescuing networks from the brink of failure---which we illustrate through the mitigation of cascading failures in a power-grid network and the identification of potential drug targets in a signaling network of human cancer.
Results
The approach iteratively identifies physically admissible perturbations that move a network into a desired state's basin of attraction, even when direct access to that state is constrained. It succeeds when such perturbations exist and is computationally more tractable than directly mapping high-dimensional basins.
- Control strategy for networks.: A desired target can be reached by finding a constrained perturbation that places the system inside its basin of attraction.Once inside that basin, the system evolves spontaneously toward the target.
- Control strategy for networks.: Constraints can prohibit modifying some nodes or increasing others, making the target directly unreachable while still permitting access to its attraction basin.The feasible perturbation region may lie outside the target state and the accessible-node subspace.
- Systematic identification of compensatory perturbations.: The framework remains effective with minor modification for stochastic or parameter-uncertain systems departing from idealized deterministic models.The main formulation assumes deterministic network dynamics.
- Systematic identification of compensatory perturbations.: The method constructs compensatory perturbations iteratively from small increments propagated through the network’s variational dynamics.The implemented intervention is the sum of all incremental perturbations.
- Systematic identification of compensatory perturbations.: 100% of randomly generated benchmark cases with theoretically existing compensatory perturbations were solved by the approach.The method also handled trajectories crossing multiple attraction basins and cases with complex basin boundaries.
- Systematic identification of compensatory perturbations.: The algorithm has theoretical running time O(n^2.5), compared with O(exp(n)) for direct fixed-resolution sampling of the basin.Here n is the number of dynamical variables, and only one compensatory perturbation must be identified.
Application to the identification of therapeutic interventions.
The framework was applied to a validated 60-node T-cell survival-signaling model to identify constrained interventions that rescue cancer-like states. It found that many sampled pre-cancerous states could be rescued using small, multi-target control sets involving recurrent candidate genes.
- Application to the identification of therapeutic interventions.: The study models T-LGL leukemia with a validated 60-node signaling network whose stable states represent normal and cancer conditions.Nodes represent proteins, transcripts, inputs, and cellular concepts, with continuous states between 0 and 1.
- Application to the identification of therapeutic interventions.: 67% of 10,000 uniformly sampled pre-cancerous states were successfully rescued when all 31 accessible nodes could be perturbed.Accessible-node states were constrained between 0 and 1, while other nodes remained unchanged.
- Application to the identification of therapeutic interventions.: The same pre-cancerous states were rescued with an average of 3.4 nodes, with a standard deviation of 3.7 nodes.The reduced interventions were multi-target and involved a small number of genes.
- Application to the identification of therapeutic interventions.: GZMB and FasT participated in nearly half of the reduced control sets, while FasT and Fas alone were predicted to rescue over 13% of cases.IAP and Fas were also identified as frequently occurring candidate nodes for experimental verification.
Reprogramming in associative memory networks.
In an associative-memory network, the framework identifies constrained perturbations that transition the system between memorized patterns while changing only oscillators representing off pixels. Even when direct target access is forbidden, the procedure reaches the target or a closely similar pattern.
- Reprogramming in associative memory networks.: The associative-memory model uses coupled oscillators whose stable phase-locked states correspond uniquely to binary patterns.The network stores seven letter patterns forming “NETWORK” in an example with N = 64 and ε = 0.8.
- Reprogramming in associative memory networks.: The control task transitions between memorized patterns while changing only oscillators representing off pixels, preserving the existing pattern’s on pixels.The constraints forbid directly reaching the target state for every tested consecutive-letter pair.
- Reprogramming in associative memory networks.: The procedure succeeds for every tested consecutive-letter transition, reaching the target or a similar pattern with a small number of binary errors.The number of errors is expected to decrease in larger networks.
- Reprogramming in associative memory networks.: The example shows that a network can be driven toward a similar desired pattern even when no eligible perturbation reaches the target’s basin directly.Thus, approximate pattern reprogramming remains possible under stricter intervention constraints.
Control of desynchronization instabilities in power-grid networks.
The framework controls post-fault power-grid dynamics by perturbing generator frequencies, even when generator phases cannot be directly modified. In the New England model, it rescues many desynchronizing faults and illustrates broader network-rescue and reprogramming applications.
- Motivation: Desynchronization instabilities are implicated in cascading failures underlying major blackouts, motivating control of generator synchrony.The paper connects this application to potential rescue of networks before failure becomes temporarily or permanently irreversible.
- Control results: Iterative control maintains bounded generator oscillations after a fault and eventually drives the perturbed network to the desired target state.A naive frequency reset delays but does not prevent loss of synchrony because it does not account for the full 2N-dimensional state space.
- Broader implications: The approach is effective when interventions are limited to a small node subset and the target state is inaccessible, because the target basin can extend into the feasible perturbation region.This basin-based mechanism also supports network rescue and movement between stable states, described as network reprogramming.
Identification of compensatory perturbations.
The procedure iteratively moves the current initial state toward the target by optimizing the orbit at its closest approach, then tests whether the updated state reaches the target basin.
- Closest approach: The system is integrated over a finite window to find the orbit time tc that minimizes its distance from the target.The closest-approach time is defined as tc ≡ arg min|x∗−x(t)|.
- Perturbation selection: The variational equation is integrated to tc to obtain M(tc), which predicts how an incremental initial perturbation changes the orbit.The resulting perturbation is selected subject to eligibility and magnitude constraints.
- Perturbation selection: A nonlinear optimization chooses δx0 to minimize the distance between the perturbed orbit and target x∗ at tc.The initial condition is then updated by x′0 → x′0 + δx0.
- Success test: After each update, long-time integration tests whether the new initial state reaches a radius-κ neighborhood of x∗ within time τ.If it does, x0 − x′0 is recognized as a compensatory perturbation; otherwise the procedure repeats up to I iterations.
Constraints on incremental perturbations.
Incremental perturbations are constrained to remain small and dynamically valid, while unstable and stable-subspace components can amplify the required initial intervention.
- Constraint effects: Stable-subspace components in δx(tc) can make the required initial perturbation δx0 larger by up to O(exp |λtcs(tc−t0)|).λtcs is the finite-time Lyapunov exponent associated with the eigenvalue having the smallest-magnitude real part.
- Constraint effects: Components along unstable directions can produce |δx(tc)| ≫ ϵ1, after which the perturbation vectors may be rescaled.This handles large predicted changes at the closest-approach time while retaining the incremental-control procedure.
- Iteration safeguards: The optimization requires consecutive increments δx0 to have positive inner product, preventing back-and-forth oscillations.The iterative approximation remains effective when the actual orbit change differs from the linear prediction by O(|δx0|^2).
- Iteration safeguards: Proper choices of ϵ0 and ϵ1 assure the required approximation, and performance remains effective across a wide parameter range.The method does not critically depend on highly accurate single-iteration forecasts if each step moves the orbit closer to the target.
Nonlinear optimization.
Each control step is formulated as a constrained nonlinear program that minimizes target distance while enforcing admissibility and incremental-step constraints.
- Optimization formulation: The optimization minimizes the remaining distance between target x∗ and orbit x(t) at the closest-approach time tc.Constraints define both eligible perturbations and the magnitude of δx0.
- Optimization formulation: The problem is a nonlinear programming task complicated by nonconvex constraints.The cited formulation includes constraints (7)–(10), with nonconvexity specifically identified for constraint (9) and possibly (7) and (8).
- Numerical solution: Sequential quadratic programming solves the constrained problem, implemented through the SciPy scientific programming package.The paper uses SQP for all calculations.
- Numerical solution: Dimensionless distances are used, including frequency normalization by target frequency in the power-grid model.This normalization avoids disparate scales between frequency and phase variables.
Values of parameters.
The T-cell signaling model uses 60 nodes, including 54 dynamical nodes and 6 static inputs, with continuous activity values in [0,1]. Its dynamics continuously approximate Boolean updates using interpolated logical rules and sigmoidal input processing.
- Network model: The network contains 60 nodes: 54 dynamical state nodes and 6 static input nodes.The static inputs are Stimuli, TAX, CD45, PDGF, Stimuli2, and IL15.
- State representation: State variables represent node activities continuously on the interval [0,1].The Boolean network is translated into an equivalent continuous formulation.
- Dynamics: Each node follows ˙x_i = B_i(f(x_1), . . . , f(x_N)) − x_i, combining a continuous Boolean update with relaxation toward its updated value.B_i is obtained by multilinear interpolation, while f is a sigmoidal Hill-type function.
- Dynamics: The function B_i interpolates the discrete Boolean rule across the corners of the N-dimensional unit cube.The original rule takes all node states as inputs and returns node i’s next state.
Additional information
The paper supplements its control framework with schematic, application, and supporting materials covering constrained interventions, signaling-network rescue, associative-memory control, power-grid recovery, and supplementary methods.
- Network control problem: Figure 1 illustrates steering an uncontrolled trajectory toward a target by perturbing an accessible control set under equality and inequality constraints.The target may lie outside the directly reachable perturbation region.
- Cancer signaling network: The cancer-network analysis identifies small control sets by ranking perturbed nodes and using bisection to search for the smallest successful set.The reported average control-set size is 3.4 nodes with standard deviation 3.7.
- Cancer signaling network: Figure 3 summarizes node-wise intervention orientation and magnitude across 10,000 pre-cancerous states, including 6,731 successful rescues.Colors encode whether node activity is increased or decreased and the associated perturbation characteristics.
- Associative memory: Figure 4 shows compensatory transitions among seven memorized letter patterns in a 64-oscillator associative-memory network.The examples concern transitions between successive letters in “NETWORK.”
- Power grid: Figure 5 compares uncontrolled, naive, and compensatory responses of a 10-generator New England power-grid model after a line fault.The compensatory intervention maintains bounded short-term oscillations and leads to the synchronous target state.
- Supplementary material: The supplementary materials include author information, parameter values, random-network construction, two-dimensional control illustrations, and analyses of riddled basins, stochasticity, and parameter uncertainty.These materials are listed under Supplementary Information.
Supplementary Figures
The supplementary figures examine stochastic robustness, compensatory perturbations near basin boundaries, fractal and riddled basins, random-network control, and computational scaling across initial and target states.
- Stochasticity: With noise, perturbations that succeed deterministically may fail when the perturbed state lies near the target basin boundary.A further perturbation can move the state deeper into the target basin and increase the likelihood of reaching the target.
- Noise robustness: Supplementary Figure S2 compares success rates for original and modified perturbations under noisy dynamics.The modified procedure places perturbations further inside the target basin and preserves effectiveness across mechanical and random-network examples.
- Parameter uncertainty: Supplementary Figure S3 evaluates robustness of original and modified compensatory perturbations to parameter uncertainty across random networks.The comparison uses success rates for candidate perturbations under uncertain parameters.
- Basin geometry: Supplementary Figures S4–S6 illustrate iterative control and compensatory perturbations for ordinary, fractal, and riddled basin geometries.The examples show how initial states and target attractors determine the constructed perturbations.
- Random networks: Supplementary Figures S7–S8 demonstrate control in large random genetic networks and compare alternate initial-target state combinations.The computational time scales approximately as N^5/2, while the number of iterations has sublinear dependence on network size.
Supplementary Table
Supplementary Table S1 lists the numerical parameters governing integration, convergence testing, iteration limits, incremental perturbation sizes, and target-approach detection.
- Control procedure parameters: Table S1 specifies τ, κ, I, ϵ_0, ϵ_1, and T for the control procedure.These parameters govern integration time, convergence tolerance, iteration limits, incremental perturbation bounds, and the time window for identifying closest target approach.
Supplementary Methods
The supplementary methods specify termination conditions, network-generation details, and comparisons with alternative state-space search procedures. The approach stops on target proximity, detected non-progress, or failure to find a compensatory perturbation.
- Termination criteria: The procedure terminates when the updated initial condition approaches within distance κ of the target within τ time units.
- Termination criteria: If no compensatory perturbation is found after I iterations, the search terminates; I is generally chosen on the order of L/ϵ0.
- Termination criteria: When no solution can be found, the orbit stops moving closer to the target and eventually oscillates within the feasible region.
- Network generation: The supplementary networks grow from a d-node connected seed by probabilistically attaching new nodes, with unweighted undirected connections and rejection of disconnected outcomes.
- Method comparison: The proposed method is compared with backward integration and shooting methods, while tracking the variational matrix requires integrating n^2 additional differential equations per iteration.
Supplementary Discussion
The method identifies admissible perturbations that move nonlinear network dynamics into a desired attractor basin, enabling transitions even when the target is not directly reachable. Across systems with complicated basin structures, large networks, noise, and parameter uncertainty, the reported tests show high effectiveness and computational efficiency.
- The iterative method finds admissible perturbations that move a system into the target basin, after which autonomous dynamics carry it to the desired state.It can use compensatory perturbations directed away from the target when constraints forbid direct access.
- The method achieved 100% success in a 1,000-sample test that moved unbounded trajectories into the basin of a chaotic attractor with a riddled basin.Only two coordinates were perturbed, and the chosen point on the attractor was not directly reachable by an eligible perturbation.
- 100% of 10,000 tested networks with 10 to 100 nodes were successfully controlled from network state x⃗A to x⃗B.The tested network class has three stable homogeneous states and guaranteed compensatory perturbations between them.
- The computation time grows polynomially with network size, while the number of iterations grows as the square root of N.Each iteration integrates O(N^2) equations when the average degree remains essentially constant; the reported overall computation-time scaling is N^5/2.
- Prior methods for attractor transitions generally require information about global state-space features, limiting their applicability to low-dimensional systems and special cases.The paper’s approach is designed to avoid reliance on such global information, although basin identification remains difficult in high-dimensional spaces.
- Existing control and optimization methods can optimize an already identified compensatory perturbation, but cannot identify alternatives until one eligible target-basin state is known.This distinguishes the paper’s basin-entry problem from methods that optimize a specified cost functional.
- Moving the endpoint further inside the predicted target basin makes interventions resilient to noise and parameter uncertainty.The adjustment systematically minimizes the time to reach the target; under noise, success remained nearly 100% up to near maximum noise strength even as network size increased.