# Cooperative Multi-UAV Collision Avoidance Based on a Complex Network
## 3 Core Algorithm Analysis
### Key Node Selection
#### Variables:  
\(l(\text{G})\): The average distance of graph G.  
\(u_{i}\): Node that is chosen to be removed. First, the UAV group is modelled, the UAV is replaced by a node, and the threatened UAV pairs are connected. Subsequently, the complex network can be represented by \(G=(U,C)\) where \(G\) is an undirected connected graph. We assume \(n\) nodes and \(m\) edges exist, and we represent \(n\) UAVs and \(m\) threats among them, respectively. The threat coefficient \(\omega_{ij}=v_{ij}/d_{ij}\) shows the degree of threat between \(UAV_{i}\) and \(UAV_{j}\), where \(v_{ij}\) represents the projection value of the relative speed between \(UAV_{i}\) and \(UAV_{j}\) on its relative position, and \(d_{ij}\) represents the relative position between \(UAV_{i}\) and \(UAV_{j}\). **Definition 1**. : \(\omega_{ij}\) _is defined as follows:_  
\[\omega_{ij}=\left\{ \begin{array}{c}\stackrel{{ \rightarrow}}{{v}}_{ij}\stackrel{{\rightarrow}}{{d}}_{ij}, \quad\quad\quad\stackrel{{\rightarrow}}{{v}}_{ij}\stackrel{{ \rightarrow}}{{d}}_{ij}\\ \boxed{d}_{ij}\boxed{d}_{ij}\end{array} \right\}>0 \tag{11}\]  
_The adjacency matrix of graph G is represented by \(H=[h_{ij}]\); it contains \(n\) rows and \(n\) columns. The element \(h_{ij}\) is defined as follows:_  
\[h_{ij}=\left\{ \begin{array}{cc}1,&0<d_{ij}<\infty\\ 0,&d_{ij}=\infty\end{array} \right. \tag{12}\]  
_The network cohesion is defined below. The degree of network cohesion depends on the connectivity of each node in the network, calculated using the arithmetic mean of the shortest distance between all pairs of nodes. The degree of network cohesion is still related to the density of the network; this is because in the UAV network, the more the number of UAVs, the greater is the threat of the entire network and the greater is the network cohesion._  
_The cohesion of graph G is defined as follows:_  
\[\partial[G]=\frac{\omega}{n\cdot l}=\frac{\sum\limits_{i\
eq j\in U}\omega_{ ij}}{n\cdot\frac{\sum\limits_{i\
eq j\in U}d_{ij}}{n(n-1)}}=\frac{(n-1)\cdot\sum \limits_{i\
eq j\in U}\omega_{ij}}{\sum\limits_{i\
eq j\in U}d_{ij}} \tag{13}\]The following equation shows the importance of node \(u_{i}\)[38]:  
\[IM(u_{i})=1-\frac{\partial[G]}{\partial[G-u_{i}]}=1-\frac{\frac{\omega_{n}}{n!( G)}}{\frac{\omega_{n+k_{i}}}{(n-k_{i})!(G-u_{i})}}=\frac{n\cdot l(G)\cdot \omega_{n-k_{i}}-(n-k_{i})\cdot l(G-u_{i})\cdot\omega_{n}}{n\cdot l(G)\cdot \omega_{n-k_{i}}} \tag{14}\]  
Because \(l(G-u_{i})<l(G)\), \(k_{i}>1\), \(\omega_{n}<\omega_{n-k_{i}}\), the following inequality \(0<IM(u_{i})<1\) can be achieved. The algorithm is as follows: [38]:  
Input: \(H\), \(W\)  
Output: \(IM\)  
Step 1: Calculate the shortest relation distance matrix \(D=[d_{ij}]\) for all pairs of UAV nodes;  
Step 2: Calculate the initial cohesion of the UAV network;  
Step 3: Assess the node importance of all UAV nodes. Step 4: Calculate the network cohesion \(\partial[G-u_{i}]\) after the node \(u_{i}\) shrinks by calculating the shortest distance matrix \(D_{i}\) and the threat matrix \(W_{i}\) between the node pairs after contraction, thereby obtaining \(IM(u_{i})\). As shown in the algorithm steps above, the time complexity of the whole algorithm depends on the calculation of the shortest distance matrix \(D\) between all pairs of nodes after the node shrinks, because the calculation of the threat matrix \(W_{i}\) only requires the deletion of the nodes around the current node \(u_{i}\). Because the time complexity of the Floyd algorithm is \(O(n^{3})\), the complexity of the algorithm will reach \(O(n^{4})\), owing to the need to shrink the operation of each node. The algorithm for calculating \(D_{i}\) given below is based on the initial matrix; the calculation can be completed with a small number of operations, and the time complexity of the entire algorithm will reduce to \(O(n^{3})\). The direct distance matrix \(S=\left[s_{ij}\right]_{n\times m}\) can be obtained by the adjacency matrix \(H=[h_{ij}]\).