# Directed Network Disassembly Method Based on Non-Backtracking Matrix
## 1 Introduction  
In complexity science, a network (denoted by \(G=(V,E)\) in graph theory) is composed of a node set \(V\) consisting of \(n\) nodes and an edge set \(E\) consisting of \(m\) edges between the nodes. Many real-world networks such as the Internet, WWW, large-scale power networks, transportation networks and interpersonal networks can be modeled in this concise way [1]. Using this method, these networks can be regarded as a collection of nodes with independent characteristics interconnected with other individuals. Each individual is regarded as a node in the network, and the connection between nodes is regarded as the edge of the network. This abstract method can intuitively show the topology of the real network, and also provides an effective research method for understanding the state and the function of the real network [2]. However, with the continuous development of technology and society, epidemic viruses [3], computer viruses [4], misinformation [5], or corruption [6] have more serious negative effects in the human world. However, removing or deactivating a part of the key nodes through the network dismantling method in the network to decompose the network into several isolated sub-parts can effectively protect the robustness of the network, control the dynamic behavior of the network, and curb the negative effects in the network mentioned above. Previous studies proved that this method to remove or deactivate the key nodes can effectively curb the spread of epidemics in the population [7], prevent the spread of misinformation through social networks [8] and prevent the spread of viruses in computer networks [9]. Some studies on complex networks choose a set of node subsets \(S\) in the network with an optimal method, and explore the influence of removing \(S\) on the network characteristics. For example, exploring how the maximum connected (strong) subset of the network will change after removing \(5\), in the example of epidemics or networkviruses transmission, if \(S\) is isolated or infected first, the impact on the speed of virus transmission can be determined [10]? In the actual situation, it will produce a certain cost consumption \(C\) when selecting and removing the node subset \(S\) in the network. In the epidemic propagation model, the vaccination of the node requires a certain socioeconomic cost. Removing different node sets in the computer virus or public opinion propagation network consumes different resources in the actual situation. Therefore, a combinatorial optimization problem is generated, whereby under the influence of the constraint removal node subset \(S\) in the network, the removal cost \(C\) is minimized. Additionally, removing nodes will destroy the network structure and affect the function of the network, so it is necessary to remove as few nodes as possible and find a set of nodes with the lowest removal cost \(C\), that is, the minimum disassembly set (we consider the most common situations where the disassembly cost is the unit cost; the minimum disassembly set is the set with the least number of nodes) and remove it. After the network is decomposed into multiple sub-parts that are not connected, network disassembly is achieved [11]. Finding the minimum disassembly set is an NP-hard problem [12]. For this kind of problem, only effective approximation algorithms or heuristic algorithms can be found at present. For the disassembly problem, there have been some recursive algorithms based on the degree or centrality of the nodes. For example, in 2015, a heuristic algorithm called 'collective' influence (CI) [13] was proposed, which determines the ownership of the nodes in an undirected random network according to the degree of nodes and the degree of local neighbor nodes; in 2016, [PERSON] proposed a three-segment minimum sum (hereafter referred to as the Min-Sum) method for dismantling large random undirected networks [11]; for large undirected random networks, this method is a more effective dismantling algorithm.