# A Connectivity-Based Clustering Scheme for Intelligent Vehicles
## 4 Proposed Connectivity-Based Clustering Schemes
### Cluster Formation and Cluster Head Selection in the Suggested Routing Scheme  
The reliability metric in [3] considered the duration of vehicles' link with respect to velocity and inter-vehicle spacing while ignoring the relative transmission range and spatial density. Spatial density refers to the number of vehicles in a particular road segment for a given time period. Spectral clustering is semi-convex unsupervised learning, where the classification of data s based on the connectivity of data points. An Eigen gap heuristic approach was used in spectral clustering to measure an optimal number of clusters [3]. The dynamic nature of VANET is an appropriate choice for spectral clustering to divide the vehicles into steerable groups [3]. In spectral clustering, the topological graph \(G\) is converted to the Laplacian matrix \(L=D-Adj\), where \(D\) and \(Adj\) are the diagonal matrix and adjacency matrix, respectively. The \(D\) matrix maintain the degree of each node (i.e., vehicle) on the diagonal.  
\[D=\begin{bmatrix}Deg(V_{1})&0&0&\dots&0\\ 0&Deg(V_{2})&0&\dots&0\\ 0&0&Deg(V_{3})&\dots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\dots&Deg(V_{n})\end{bmatrix}\]  
where \(Deg(V_{1})\) represents the degree of vehicle. The definition of Laplacian matrix is given below:  
\[L=(\sum_{j}Adj_{ij})-Adj_{ij} \tag{8}\]  
In spectral clustering, spectral decomposition is performed to factorize the matrix into Eigenvalues and their subsequent Eigenvectors. The significance of the spectral (Eigen) decomposition is to reduce the computational cost and space complexity. In the literature, many clustering schemes in machine learning are used for the formation of the cluster, but most of them are non-convex, where data size and high dimension give bad results in term of cluster shape and size. In spectral clustering, the Eigen decomposition significantly minimizes the dimensionality (i.e., selects only similar features in the form of Eigen vectors and Eigenvalues) of the vehicles. The selected dimensions represent only important features instead of taking the whole data set. For measuring the optimal number of clusters in highly dynamic networks, the Eigenvalues of the Laplacian graph \(L\) were used as an input. Let \(\lambda_{i}\) be the Eigenvalue, where \(j=\{1,2,3\dots,n\}\) in the ascending order, then based on Eigen gap heuristic, the number of clusters \(N_{c}\) will be as follows:  
\[N_{c}=\arg\max(\lambda_{j+1}-\lambda_{j}) \tag{9}\]The difference in Eigen gap should be greater than 1 to optimally divide the evolving network into clusters. To select an optimal \(CH\), it is necessary to measure the cluster ranking. For this purpose, we calculated the Eigen centrality of each cluster. The Eigenvector centrality matrix \(E\) can be calculated as below:  
\[E=\frac{1}{Eig_{max}}(A\times C) \tag{10}\]  
In Equation (10), \(Eig_{max}\) and \(A\) represent the maximum Eigenvalue and Affinity matrix, respectively. The parameter \(C\) represents the degree matrix of dimension. \(CH\) in a particular cluster \(k\) can be obtained as follows:  
\[CH=\arg\max(C_{k}). \tag{11}\]  
where \(CH\) represents the cluster head of cluster \(k\).