# Blind Spoofing GNSS Constellation Detection Using a Multi-Antenna Snapshot Receiver +
## 4 System of Detections
### Clustering and Community Based Detection  
As spatial spoofing detection evaluates the similarity of the array steering vectors, a simple expansion thereupon is to attempt to cluster the array steering vectors together. This is a measure of how well the satellites can be grouped. The Louvian clustering algorithm is an iterative algorithm that optimizes the modularity of a data set [48; 49]. The data set consists of several nodes and edges (links) between these nodes. Highly connected nodes are grouped into communities by this algorithm. This means that correlated nodes would be grouped in communities making this algorithm ideal for identifying \"spoofing communities\". This allows the algorithm to identify which subset of satellites are spoofed and which are the real GNSS signals. At the same time, the modularity of the data set is an indication of the connectedness of the nodes. Hence, high modularity indicates that the nodes can be grouped efficiently into communities, whereas low modularity indicates that the data is highly random and not simply grouped into communities. Further, as the nodes are grouped into communities, the possibility to detect multiple spoofing transmitters is also possible (i.e., where a spoofer uses two or more antennas to transmit a subset of the signals). However, this phenomenon requires further investigation and is suggested for future research. This algorithm requires a matrix \(\mathbf{A}\) which contains the weight of the edges between each of the nodes. The higher values in this matrix corresponds to stronger links between the nodes. This is represented by the column and row of the matrix. Further, this algorithm requires a vector \(\mathbf{c}\) which contains a list of the different communities. Maximizing the modularity of the data set achieves effective clustering. The modularity \(Q\) is defined as:  
\[Q=\frac{1}{2m}\sum_{i,j}\left(A_{ij}-\frac{k_{i}k_{j}}{2m}\right)\delta(c_{i},c_{ j})\,, \tag{32}\]  
where \(m\) is the total connectedness between all of the nodes:  
\[m=\frac{1}{2}\sum_{i,j}A_{ij}\,, \tag{33}\]  
and \(k_{i}\) is the connectedness of the \(i\)-th node to the other nodes and is defined as:  
\[k_{i}=\sum_{j}A_{ij}\,. \tag{34}\]  
Lastly, \(\delta(\cdot)\) is a modified Dirac function and is defined as:  
\[\delta(c_{i},c_{j})=\left\{ \begin{array}{ll}1,&\mbox{if }c_{i}=c_{j}\\ 0,&\mbox{otherwise}\end{array} \right.\,. \tag{35}\]  
At the start of the clustering process, all of the nodes are placed in separate communities. The initial modularity \(Q\) for the system is calculated. Systematically, each node is then moved to different communities. The community which results in the greatest increase of system modularity \(Q\) for each node is then selected as the new community for that node. When all of the nodes have been adjusted to the optimal community clustering, a new system is formed by grouping nodes from the same community. Thereby, implicitly reducing the dimensions of the matrix \(\mathbf{A}\) in each iteration. Thereafter, the process is repeated until no improvement of the modularity \(Q\) is achievable. As the algorithm iterates, similar communities are clustered together to form new and larger communities. To apply the Louvain algorithm to the spoofing values, the normalized correlation matrix \(\mathbf{C}_{\mathrm{norm}}\) or the detection matrix \(\mathbf{D}\) can be selected as the edge matrix \(\mathbf{A}\). Using the normalized correlation matrix \(\mathbf{C}_{\mathrm{norm}}\) will have more dynamics and information about the values; however, it would require more processing. Using detection matrix \(\mathbf{D}\) will be faster, but as small matrices are used (the Louvain algorithm was developed to address millions of nodes), this improvement in processing requirements is negligibly small. The modularity \(Q\) of the system, the number of communities that are formed, and the difference in community sizes within a system, are possible metrics that can be exploited for detector development. The most promising one seems to be the modularity \(Q\).