Input node placement restricting the longest control chain in controllability of complex networks

Area of Science:

• Network science
• Control theory
• Graph theory

Background:

• Network controllability is often measured by the minimum number of input nodes.
• A trade-off exists between minimizing input nodes and the energy required for network control.
• Reducing the longest control chain (maximum distance from input nodes) significantly lowers control energy.

Purpose of the Study:

• To investigate the trade-off between input minimization and control energy by constraining the longest control chain.
• To develop and validate a method for identifying minimum input sets under longest control chain constraints.

Main Methods:

• Formulating the longest control chain-constrained minimum input problem as a joint maximum matching and minimum dominating set problem.
• Demonstrating the NP-completeness of this graph combinatorial problem.
• Developing and validating a heuristic approximation algorithm.

Main Results:

• The problem of finding a minimum input set with a constrained longest control chain is NP-complete.
• A heuristic approximation algorithm was developed and validated.
• Analysis of real and model networks shows that reducing the longest control chain often requires minimal or no additional inputs, primarily necessitating input node rearrangement.

Conclusions:

• Constraining the longest control chain is an effective strategy for reducing control energy in networks.
• The developed heuristic algorithm provides a practical approach to solving this NP-complete problem.
• Network structure plays a crucial role in determining the impact of longest control chain constraints on input requirements.