The Research On Target Control Based On Minimum Path Cover In Complex Network

The final target of researching complex network is to control complex network. Recent advances focus on controlling the whole complex networks through a minimum driver nodes set(MDS) under the condition that the global topology. However, it is generally neither feasible nor necessary to control the entire network. Instead, it is more realistic and sufficient to achieve target control, that is, controlling a subsystem of network which is essential for system's mission pertaining to a selected task.An greedy alogrithm was proposed in 2014, which can compute the number of driver nodes for controlling all target nodes. As the main idea of greedy alogrithm is constantly using maximum matching alogrithm in every iteration, which can only used in whole network. Further more, different maximum matching set select in every iteration of greedy alogrithm leads to different matching set, that means, the result of greedy alogrithm is affected by the netwrok toplogy and the selection of maximum matching set. Therefore, it is the urgent need for us to propose a new target control.This paper mainly study the target control of complex network. Frist, the concept of minimum path cover(MPC) in graph theory is introduced. It have been proved that the number of MPC of all target nodes is equal to the number of driver nodes needed in target control, and the nodes set made up of every path's start point in MPC can act as an driver nodes set to control all target nodes. Second, this artical propose two alogrithms finding MPC of given target nodes and introduce the upper/lower bound of the number of driver nodes for target control. In order to verify the rationlity and efficiency of this target control based on an minimum cover, the method based on MPC for target control is applied in two model networks and several real networks. Comparing efficiencies of target control of random scheme with that of deliberate scheme. The result indicates that the number of driver nodes calculated by the method based on MPC proposed in this paper is between the upper and lower bound, and the deliberate target control is more efficient than random target control. Finally, the method based on MPC developed in this paper is applied in networks which only knowing their partial topologies and the same results as the global knowledge of network topology are obtained. It is fully demonstrates the method based on MPC for target control can be applied in the networks with any topology, even if only partial topology information of target nodes are given.