# Directed Network Disassembly Method Based on Non-Backtracking Matrix
## 4 Method
### Disassemble the Objective Function  
In this section, we consider the general case of dividing a network in two modules of equal size according to the nature of the edges, minimizing the number of edges between two different modules. The non-backtracking matrix is used to store the edge adjacency information in the directed network, because in the disassembly problem, we will eventually remove all overlapping nodes on different edge modules, and the weight of the edge does not affect the selection of the minimum node set; therefore, we set the weight of each edge as the unit weight. We divide \(m\) edges in the edge network into two equal-sized \(\frac{m}{2}\) modules according to the corresponding characteristic. We define an index variable \(s_{i\to j}\in\mathbf{R}^{m}\) for any directed edge \(i\to j,i,j\in\mathbf{N}\) in the network, and assume that if this edge \(i\to j\) belongs to partition module 1, then \(s_{i\to j}=1\); if edge \(i\to j\) belongs to partition module 2, then \(s_{i\to j}=-1\). So, we obtain  
\[\frac{1}{2}\Big{(}s_{i\to j}s_{j\to k}+1\Big{)}=\begin{cases}1,&\text{If two connected edges}\\ &i\to j,j\to k(i\
eq k)\text{ belong to}\\ &\text{the same edge module}\\ 0,&\text{other cases}\end{cases} \tag{2}\]  
Equation (2) is used to determine whether two connected edges belong to the same module. Combined with Equation (2), we use the non-backtracking matrix as an operator to obtain the objective function of the minimum number of disassembled edges, which is used to find a set of edges that connect two different modules with the smallest number:  
\[\begin{split}\min:& R=\sum_{i\to j\
eq k \to l}\mathbf{B}_{i\to j,k\to l}-\sum_{i\to j,k\to l}\frac{1}{2}\Big{(}s_{i\to j}s_{k \to l}+1\Big{)}\mathbf{B}_{i\to j,k\to l}\\ &=\frac{1}{2}\sum_{i\to j,k\to l}\Big{(}1-s_{i\to j}s_{k \to l}\Big{)}\mathbf{B}_{i\to j,k\to l}\\ &=\frac{1}{2}\sum_{i\to j,k\to l}\Big{(}d_{i\to j}s_{k \to l,i\to j}-\mathbf{B}_{i\to j,k\to l}\Big{)}s_{i\to j}s_{k \to l}\\ &=\frac{1}{2}s^{T}\mathbf{B}^{\prime}s\\ &\text{s.t.}\ \left\{\begin{array}{l}1^{T}s=0,\\ s_{i\to j}\in R,i\to j\in E\end{array}\right.\end{split} \tag{4}\]  
where \(\mathbf{B}^{\prime}=\mathbf{D_{B}}-\mathbf{B},\mathbf{D_{B}}\) is a diagonal matrix, \((\mathbf{D_{B}})_{i\to j,i\to j}=\sum_{k\to l}\mathbf{B}_{i\to j,k\to l}\). Equation (3) represents the difference obtained by the logarithm of the minimized total connected edges minus the logarithm of the edges connected inside the edge module. When two connected edges are divided into different edge modules, \(s_{i\to j}s_{j\to k}=-1,\mathbf{B}_{i\to j,j\to k}=1\), the nodes connecting the two edges needs to be removed; on the contrary, when two connected edges are divided into the same edge module, the nodes connecting the two edges do not need to be removed. Finally, the set of nodes that need to be removed corresponding to the set of partitions that minimize \(R\) is the minimum disassembly set. We specify the number of nodes whose disassembly cost is the minimum disassembly set.  
\(1^{T}s=0\) in Equation (4) ensures that the two modules are of equal size. Unfortunately, this optimization problem is an NP-hard problem. For this problem, the approximate solution can be found by relaxing constraint \(s_{i\to j}\in\{-1,1\}\) to \(s_{i\to j}\in R\). According to the Courant--[PERSON] theory[24], the solution of this relaxation constraint minim optimization problem can be found by analyzing the eigenvector \(v^{(2)}\) corresponding to the second smallest eigenvalue \(\lambda_{2}\) of \(\mathbf{B}^{\prime}\). So, if node \(j\) connects two edges \(i\to j,j\to k(i\
eq k)\) corresponding to the value of the second smallest eigenvector, one of the second smallest eigenvectors are non-negative \(\left(v^{(2)}_{i\to j}\geq 0\right)\), and the other's second smallest eigenvector is negative \(\left(v^{(2)}_{i\to j}<0\right)\); this node will be removed. Removing all such nodes in the network can decompose the network into two sub-parts.