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

Samie Alizadeh, Márton Pósfai, Abdorasoul Ghasemi

Research output: Contribution to journalArticlepeer-review

Abstract (may include machine translation)

The minimum number of inputs needed to control a network is frequently used to quantify its controllability. Control of linear dynamics through a minimum set of inputs, however, often has prohibitively large energy requirements and there is an inherent trade-off between minimizing the number of inputs and control energy. To better understand this trade-off, we study the problem of identifying a minimum set of input nodes such that controllabililty is ensured while restricting the length of the longest control chain. The longest control chain is the maximum distance from input nodes to any network node, and recent work found that reducing its length significantly reduces control energy. We map the longest control chain-constraint minimum input problem to finding a joint maximum matching and minimum dominating set. We show that this graph combinatorial problem is NP-complete, and we introduce and validate a heuristic approximation. Applying this algorithm to a collection of real and model networks, we investigate how network structure affects the minimum number of inputs, revealing, for example, that for many real networks reducing the longest control chain requires only few or no additional inputs, only the rearrangement of the input nodes.

Original languageEnglish
Article number3752
JournalScientific Reports
Volume13
Issue number1
DOIs
StatePublished - Dec 2023

Fingerprint

Dive into the research topics of 'Input node placement restricting the longest control chain in controllability of complex networks'. Together they form a unique fingerprint.

Cite this