PaperlayerView exact revision on arXiv

Source-linked AI summary

Structure-based control of complex networks with nonlinear dynamics

Jorge G. T. Zañudo, Gang Yang, Réka Albert

arXiv:1605.08415v3cond-mat.dis-nneess.SYphysics.soc-phq-bio.MN

TL;DR

The paper asks how far nonlinear network control can be inferred from wiring structure when system functions and parameters are unknown. It adapts feedback vertex set control to include source-node dynamics, applies it to real networks and Drosophila models, and finds that feedback structure governs override demand while model-specific controls can be smaller than the general prescription.

  • Problem

    Network structure is often known without the nonlinear functions and parameters needed for full control analysis, while general attractor-based controller design remains difficult and unsolved.

  • Method

    The paper adapts feedback vertex set control to source-node dynamics and uses source-node plus feedback-vertex-set overrides to target natural attractors.

  • Results

    Feedback structure, especially SCCs and short cycles, determines FC demand; in Drosophila models, 16 (12) nodes suffice for continuous (discrete) control versus 52 (14) general FC nodes.

  • Takeaways & Limitations

    FC provides realizable node overrides applicable with structural information alone and robust to changes in model parameters and functions.

  • Takeaways & Limitations

    General attractor-based controller design for nonlinear systems remains difficult and depends strongly on the specific functions Fi.

Abstract

from arXiv · show

What can we learn about controlling a system solely from its underlying network structure? Here we adapt a recently developed framework for control of networks governed by a broad class of nonlinear dynamics that includes the major dynamic models of biological, technological, and social processes. This feedback-based framework provides realizable node overrides that steer a system towards any of its natural long term dynamic behaviors, regardless of the specific functional forms and system parameters. We use this framework on several real networks, identify the topological characteristics that underlie the predicted node overrides, and compare its predictions to those of structural controllability in control theory. Finally, we demonstrate this framework's applicability in dynamic models of gene regulatory networks and identify nodes whose override is necessary for control in the general case, but not in specific model instances.

STRUCTURE-BASED NETWORK CONTROL WITH NONLINEAR DYNAMICS

Feedback vertex set control extends structure-based control to nonlinear networks with source-node dynamics, steering arbitrary initial states toward desired natural attractors without requiring specific functions or parameters.

  • System dynamics: The framework models source variables independently from internal variables, while internal dynamics include nonlinear responses and decay that bounds state growth.Source-node dynamics can represent external stimuli or fixed initial or boundary conditions.
  • Control framework: Feedback vertex set control overrides nodes intersecting every feedback loop, ensuring asymptotic convergence to a selected dynamical attractor for the nonlinear model class.The framework applies to bounded dynamics of the stated form, including examples from biochemical and contagion processes.
  • Scope: Attractor-based control remains difficult to design as a general nonlinear controller when the specific functions governing the system are part of the problem.The structure-based framework addresses this setting by providing a realizable node-override prescription.
  • Control framework: Source nodes must also be controlled because their states can alter which dynamical attractors are available to the system.Steady states may merge, appear, or disappear when an external stimulus represented by a source node changes.
  • Control framework: The required override set is determined by the network’s input layer and cycle structure: acyclic networks need only source-node control, whereas cyclic networks additionally require an FVS.Simple examples include a linear chain controlled at its source and a source-plus-cycle network requiring the source and a cycle node.

FEEDBACK VERTEX SET CONTROL OF REAL NETWORKS

Across diverse real networks, feedback vertex set control demand is chiefly associated with strongly connected and short-cycle structure rather than degree sequence alone.

  • Network-wide control: FC difficulty was measured as n_FC = N_FC/N across biological, technological, and social networks ranging from dozens to millions of nodes.The control fraction separates source-node and FVS contributions.
  • Topological determinants: Networks with larger SCC fractions tend to have larger FVS contributions and larger FC node sets.Networks with n_FC > 0.5 generally have n_SCC > 0.93, whereas most networks with n_FC < 0.25 have n_SCC < 0.4.
  • Randomization tests: Real networks generally require more FC nodes than degree-preserving randomized networks, with food-web and citation networks as notable exceptions.The exceptions have acyclic or nearly acyclic structure and therefore fewer cycles and SCC nodes than their randomized counterparts.
  • Randomization tests: Degree-preserving randomizations that preserve SCCs show strong agreement with real-network FC node-set sizes.This supports the role of cycle organization beyond degree sequence in determining FC demand.
  • Randomization tests: Preserving cycles of length 4 or less also reproduces FC node-set sizes well, except in near-acyclic food-web and citation networks.Short cycles do not capture the near-acyclic structure of those exceptions.
  • Conclusion: The number of nodes needing override is determined specifically by SCCs and short cycles within the network’s cycle structure.These structures account for the principal variation in FC demand across the studied networks.

COMPARING FEEDBACK VERTEX SET CONTROL AND STRUCTURAL CONTROLLABILITY

FC and structural controllability assess different control objectives and therefore can predict markedly different node-set sizes across network types.

  • Network comparison: Gene regulatory networks require 75% - 96% of nodes in SC but only 1% - 18% in FC.Across several network types, n_SC and n_FC appear inversely related.
  • Conceptual distinction: FC targets natural attractors through node-state overrides, whereas SC targets full control using controller signals and does not independently control cycles.Both methods share control of source nodes but differ in how cycles and chains contribute to the control set.
  • Interpretation: The contrasting predictions reflect different underlying dynamics, control actions, and meanings of control rather than a single common difficulty measure.FC concerns nonlinear attractor control, while SC provides linear full-control conditions.
  • Cycle effects: In networks with many cycles, FC can require more controlled nodes than SC because FC directly controls an FVS while SC can reach cycles from spanning chains.In an acyclic network, FC may require only source nodes while SC may require additional chain-top nodes.

FEEDBACK VERTEX SET CONTROL AND DYNAMIC MODELS OF REAL SYSTEMS

The paper applies feedback vertex set control to continuous and discrete fruit-fly gene-regulatory models, showing both general guarantees and smaller model-specific control sets.

  • FEEDBACK VERTEX SET CONTROL AND DYNAMIC MODELS OF REAL SYSTEMS: The study tests feedback vertex set control on differential-equation and Boolean models of the Drosophila segmentation gene-regulatory network.Both models represent four successive cells as a repeating unit and include intracellular and intercellular interactions.
  • FEEDBACK VERTEX SET CONTROL AND DYNAMIC MODELS OF REAL SYSTEMS: N_FC = 52 (14) for the ODE (discrete) model, with large strongly connected components contributing substantially to the control sets.The reported n_SCC/n_FVS ratios are 0.74/0.35 for the ODE model and 0.5/0.18 for the discrete model.
  • FEEDBACK VERTEX SET CONTROL AND DYNAMIC MODELS OF REAL SYSTEMS: Locking FC nodes to their wild-type attractor trajectory successfully steers each model to the wild-type attractor.This provides an intervention directly linked to the models’ long-term behavior.
  • FEEDBACK VERTEX SET CONTROL AND DYNAMIC MODELS OF REAL SYSTEMS: 16 (12) nodes suffice for the continuous (discrete) model, reducing the general FC control sets by 66% (14%).Thus, subsets of the general FC node set can control a particular model and attractor, while FC supplies an upper limit for model-dependent control sets.

DISCUSSION

The discussion positions attractor-based control as complementary to other network-control approaches and emphasizes FC’s applicability when structure alone, or a parameterized model, is available.

  • DISCUSSION: Network-control methods address complementary questions, so the appropriate method depends on the control objective, dynamics, and domain-specific meaning of control.The discussion specifically distinguishes attractor-based control from methods targeting other control notions.
  • DISCUSSION: FC provides realizable control strategies from structural information alone and remains robust to changes in model parameters and functions when a parameterized model is available.It also provides a benchmark connecting structure-only control with methods requiring both network structure and a dynamic model.

I.A. Previous work on feedback vertex set control

The earlier feedback vertex set framework studies dissipative network dynamics whose long-term behavior is organized by attractors, proving that overriding a feedback vertex set guarantees convergence to a selected attractor.

  • I.A. Previous work on feedback vertex set control: The framework models node states with differential equations whose predecessor sets encode network structure and whose functions satisfy a decay condition.Only positive self-regulation is included among predecessors; negative self-regulation is excluded from the predecessor set.
  • I.A. Previous work on feedback vertex set control: Bounded dissipative dynamics converge from any initial state to a bounded global attractor containing steady states, limit cycles, quasi-periodic orbits, and bounded chaotic trajectories.These attractors represent stable long-term activity patterns in the modeled system.
  • I.A. Previous work on feedback vertex set control: The theorem states that convergence of every pair of solutions for all admissible nonlinearities occurs if and only if the controlled node set is a feedback vertex set.The theorem assumes continuous functions and derivatives together with dissipative dynamics and appropriate self-loop conditions.
  • I.A. Previous work on feedback vertex set control: Overriding every feedback-vertex-set node with the trajectory of a target attractor removes all feedback cycles and makes that attractor the unique attractor of the overridden system.The full feedback vertex set is necessary and sufficient when the guarantee must hold for every admissible choice of nonlinear functions.
  • I.A. Previous work on feedback vertex set control: The framework does not specify the outcome of imperfect overrides; approximately matching the target trajectory is expected to move the system into the target attractor’s basin, but this may depend on the model and attractor.The exact guarantee therefore applies to precise state overrides.

I.B. Feedback vertex set control for general system dynamics

The paper extends feedback vertex set control to systems with source nodes whose inputs can alter the available attractors, then prescribes overriding source and feedback nodes along a desired attractor trajectory.

  • I.B. Feedback vertex set control for general system dynamics: Source nodes are independent of internal variables and can represent external stimuli or initial-condition variables that change the system’s available attractors.The original theorem cannot be applied directly because source-node dynamics do not obey the same equation as internal nodes.
  • I.B. Feedback vertex set control for general system dynamics: The extension selects the desired attractor and its source-node trajectory, then overrides source states with that trajectory from a chosen starting time.After the override, the internal dynamics can be treated using modified functions and the feedback vertex set framework.
  • I.B. Feedback vertex set control for general system dynamics: Overriding source nodes and the feedback vertex set with their trajectories in the desired attractor guarantees convergence to that attractor as t →∞.The modified system preserves the desired attractor while enabling the feedback vertex set theorem to apply.
  • I.B. Feedback vertex set control for general system dynamics: The FC control set contains all source nodes plus a feedback vertex set, and minimizing it reduces to finding a minimal feedback vertex set.Minimal feedback vertex sets may be nonunique and highly degenerate.
  • I.B. Feedback vertex set control for general system dynamics: The minimal feedback vertex set problem is NP-hard, so large-network control sets require approximate algorithms.GRASP and simulated annealing produced almost identical results across evaluated networks, increasing confidence in the estimates.

I.D. Feedback vertex set control and model-based network

Feedback vertex set control (FC) targets attractors by overriding nodes that intersect feedback loops, whereas stable motif control uses model-specific positive-feedback subnetworks. FC provides an ensemble-level upper bound, while particular models may need fewer controlled nodes.

  • Feedback vertex set control: FC identifies nodes intersecting every feedback loop to drive any initial state toward a chosen dynamical attractor.The framework applies across bounded nonlinear dynamics on the specified network structure.
  • Model specificity: FC gives a sufficient node set for every model sharing a network structure, but a particular model may require a smaller subset.The FC set is therefore an upper bound for attractor control in any specific model instance.
  • Stable motif control: Stable motif control identifies subnetworks that uniquely determine an attractor and fixes selected node states to reach it from any initial state.It is model-based and uses Boolean dynamics, unlike structure-based FC for continuous dynamics.
  • Source nodes: FC and stable motif control treat source nodes similarly, although FC permits source trajectories while stable motif control fixes source states.Both methods require source-node manipulation consistent with the target attractor.
  • Method comparison: FC must manipulate every feedback loop, whereas stable motif control manipulates only selected self-sustaining positive-feedback loops or their intersections.This difference explains why model instances can require only a subset of an FC node set.

I.F. Feedback vertex set control and controllers

FC overrides selected state variables along trajectories specified by target attractors, addressing attractor control without requiring a parameterized nonlinear model. Designing implementable external controller signals remains outside this work and depends on model details.

  • Feedback vertex set control: FC overrides selected state variables so they follow trajectories specified by the target attractor.This differs from control-affine approaches that couple external signals directly into governing equations.
  • Controller design: Designing a general controller that drives nonlinear systems to target attractors is difficult and remains unsolved.Recent attractor-control methods require parameterized models and numerical controller design.
  • Controller design: Override control identifies nodes to control without knowing system-specific controller coupling or a parameterized dynamic model.The paper treats node override as an idealized controller signal and a first step toward driver-signal design.
  • Comparison with structural controllability: Structural controllability targets full control for linear systems, while FC targets attractor control for dissipative nonlinear systems.SC concerns steering between arbitrary states, or locally near nonlinear trajectories; FC steers toward natural attractors.
  • Comparison with structural controllability: SC guarantees existence of an external driver signal, whereas FC specifies controlled-node trajectories but not how a signal produces them.SC signals may require additional constraints for numerical implementability.

II.B. Structural controllability and self-dynamics

Structural controllability (SC) can become uninformative for nonlinear systems with self-dynamics because independent diagonal entries may imply one driver signal regardless of topology. FC and SC also differ in dynamics, objectives, and control actions, so their predictions require careful scope matching.

  • Self-dynamics: A single driver signal can appear sufficient for full control when every node has a self-loop under SC’s independent-entry assumption.This result is a consequence of treating nonzero entries in A and B as independent.
  • Self-dynamics: Fixing self-dynamics changes the SC calculation: with a common fixed self-weight, driver counts equal SC applied after setting diagonal entries to zero.More general fixed diagonals require eigenvalues and geometric multiplicities of A.
  • Self-dynamics: For nonlinear systems with decay, linearization produces nonzero diagonal entries, so SC may predict one driver regardless of the real network topology.The resulting structure-based prediction tells little about topology for these systems.
  • Structural controllability: SC assigns driver nodes through maximum matching, decomposing the network into driver-rooted chains and reachable directed cycles.Its structurally required nodes include source nodes, surplus sink nodes, and internal dilation nodes.
  • Scope of comparison: SC and FC differ in dynamics, control objectives, and actions, so predictions should not be extended beyond their respective applicability.FC specifies target node trajectories but not controller realization; SC guarantees a driver signal without explicitly determining it.

III.B. Notes on the ensembles of randomized real networks

The study randomizes real networks while preserving selected structural features to test which topology explains feedback vertex set sizes. Ensemble sizes vary with computational demands, and some procedures preserve strongly connected components or short cycles.

  • Randomized ensembles: The study uses full, degree-preserving, SCC-preserving, and short-cycle-preserving randomizations to analyze randomized real-network ensembles.These procedures isolate the contributions of degree patterns, strongly connected components, and short cycles.
  • SCC-preserving randomization: SCC-preserving randomization rewires the acyclic portion while retaining edges belonging to strongly connected components.A topological order constrains accepted rewiring steps before SCC edges are restored.
  • Short-cycle-preserving randomization: Short-cycle-preserving randomization retains edges in cycles of length four or less and rejects rewiring that creates cycles of length one or two.Additional rewiring is performed on length-four cycles.
  • Ensemble sampling: The ensemble size is Ω = 100 for Erdős–Rényi and degree-preserving randomizations, and Ω = 50 for SCC-preserving and short-cycle-preserving randomizations.Smaller ensembles are used for properties that are computationally expensive on very large or dense networks.
  • Ensemble sampling: The topological-order generator samples all possible orders but not uniformly, with probability P(O) = 1/C(O).The authors accept this because the objective is to avoid generating ensembles from a single topological order.

III.C. Comparing feedback vertex set control and structural

Compared with structural controllability, feedback vertex set control predicts different control-node fractions across real network types, with the difference explained by network topology.

  • Gene regulatory networks require 75%-96% of nodes under structural controllability but only 1%-18% under feedback vertex set control.
  • Structural and feedback vertex set control-node fractions can be inversely related across network types, including gene regulatory, food web, internet, social trust, and intra-organizational networks.
  • Structural controllability decomposes its node fraction into source, external-dilation, and internal-dilation nodes, whereas feedback vertex set control uses source nodes and feedback-vertex-set nodes.
  • Networks with nSC < nFC are dominated by strongly connected components, while networks with nSC > nFC are commonly dominated by out-components or internal dilations.

IV. Structure-based control of the Drosophila melanogaster segment polarity gene regulatory

The study applies feedback vertex set and structural controllability to continuous and Boolean models of the Drosophila segment polarity gene network, revealing different control requirements and model-dependent outcomes.

  • Structure-based control of the von Dassow et al. differential equation model: The continuous von Dassow et al. model contains 136 nodes, including 4 source and 24 sink nodes, connected by 488 regulatory and interaction edges.
  • Boolean model: The Boolean Albert & Othmer model has 56 nodes and 144 edges, with ten steady states under biologically relevant source-node states.
  • Structure-based control of the von Dassow et al. differential equation model: Feedback vertex set control predicts that 52 nodes, including 4 source nodes and 48 additional nodes, can drive any initial condition to any original attractor.
  • Structure-based control of the von Dassow et al. differential equation model: The same feedback vertex set control strategy was numerically verified to drive any state to a wild type limit-cycle attractor under another benchmark parameter set.
  • Structure-based control of the von Dassow et al. differential equation model: Structural controllability predicts 24 controlled nodes, but requires potentially complicated time-varying driver signals determined separately for each initial condition.

Boolean model

In the Boolean segment-polarity model, feedback vertex set control identifies a larger general control set than structural controllability, whose source-node control is not sufficient for attractor control.

  • Feedback vertex set control predicts that 14 nodes need control: 4 source nodes, 8 self-sustaining wg and PTC nodes, and 2 additional nodes.
  • Structural controllability predicts control of only the four SLP source nodes because the network can be covered by four branches and one loop.
  • With source nodes fixed to their wild type states, six attractors remain reachable and one is wild type; all-OFF or all-ON source states exclude the wild type state.
  • Structural controllability cannot guarantee attractor control here because, for general nonlinear systems, it provides only sufficient conditions for local controllability near a steady state or trajectory.
Loading 1605.08415v3…