Abstract
Target control of directed networks, which aims to control only a target subset instead of the entire set of nodes in large natural and technological networks, is an outstanding challenge faced in various real world applications. We address one fundamental issue regarding this challenge, i.e., for a given target subset, how to allocate a minimum number of control sources which provide input signals to the network nodes. This issue remains open in general networks with loops. We show that the issue is essentially a path cover problem and can be further converted into a maximum network flow problem. A method termed "Maximum Flow based Target Path-cover" (MFTP) with complexity $O(|V|^{1/2}|E|)$ in which $|V|$ and $|E|$ denote the number of network nodes and edges is proposed. It is also rigorously proven to provide the minimum number of control sources on arbitrary directed networks, whether loops exist or not. We anticipate that this work would serve wide applications in target control of real-life networks, as well as counter control of various complex systems which may contribute to enhancing system robustness and resilience.
Introduction
In the study of complex systems—from the neural pathways of the brain to the sprawling grids of our power infrastructure—a recurring challenge is "controllability." While previous research focused on controlling every single node in a network, this work tackles a more practical and difficult question: How do we control just a specific subset of nodes using the absolute minimum number of resources?
Traditionally, researchers aimed for full structural controllability, but in massive real-world networks, this is often unnecessary or physically impossible. We usually only care about a "target set"—specific genes in a regulatory network or key routers in a communication web. However, target control is mathematically trickier than full control, especially when networks contain feedback loops. Before this study, finding the minimum number of "driver nodes" for a target set in a general directed network with loops remained an open challenge.
Methodology: The MFTP Algorithm
The authors bridge the gap between control theory and graph theory through a multi-step transformation termed the Maximum Flow based Target Path-cover (MFTP) algorithm. The process involves mapping the control problem to a network flow challenge:
- Path Cover Mapping: Target control is shown to be essentially a "path cover" problem. To control a target set, nodes must be covered by a combination of directed paths (requiring external signals) and circles (which can be self-sustaining).
- Graph Transformation (Node Splitting): A "node splitting" technique is used where each node $v$ is split into an "in-node" ($v_{in}$) and an "out-node" ($v_{out}$), connected by an edge.
- Network Flow Formulation: By adding a virtual source and sink and setting specific capacities and lower bounds on edges, the search for the minimum number of control paths is transformed into a Maximum Network Flow problem.
- Optimization: The Dinic algorithm is used to solve the flow problem, achieving a computational complexity of $O(|V|^{1/2}|E|)$, making it efficient for large-scale networks.
Results and Discussion
The MFTP algorithm was validated on both synthetic (Erdos-Renyi and Scale-Free) and real-world networks, including the C. elegans neural network and various communication grids.
Key Insights
- Optimality: The authors rigorously prove that MFTP provides the absolute minimum number of control sources required for any directed network, regardless of the presence of loops.
- The "Circle" Advantage: A major insight is that nodes in closed loops (circles) do not necessarily need dedicated external control sources if they are part of a larger controllable structure. MFTP exploits these loops to minimize inputs.
- Topology Matters: Scale-Free networks generally require more control sources than Erdos-Renyi networks for the same target set size. This is attributed to the higher proportion of low-degree nodes in SF networks, which are harder to reach through internal structure.
- Consistency: When the target set is the entire network, MFTP is consistent with standard Maximum Matching (MM) algorithms, proving it is a more general solution.
Conclusion and Future Work
This work provides a robust framework for the target control of complex directed networks. While the current approach assumes Linear Time-Invariant (LTI) systems and focuses on structural controllability, it sets a foundation for managing large-scale systems efficiently. Future research may extend this flow-based framework to networks with nonlinear dynamics or explore multi-layer networks where control is distributed across different connection types. Such advancements will be vital for enhancing the robustness and resilience of critical infrastructure and biological systems.
Summary updated