# Detecting Dynamic Communities in Vehicle Movements Using Ant Colony Optimization
## 2 Methods
### Spatial Scan Statistic for Spatially Embedded Graphs  
In this study, a spatial scan statistic [15] was used for the quantitative assessment of the spatial communities. We denote the strength sequence of a graph \(G\) as \(S=\{S_{1},S_{2},\ldots,S_{N}\}\), where the strength \(S_{i}\) of a vertex \(v_{i}\) is defined as the sum of the weights of the edges connected to \(v_{i}\). For a spatial community \(\mathbf{Z}\subset\mathbf{G}\), the sum of strengths of \(\mathbf{Z}\) can be defined as \(S(\mathbf{Z})=\sum_{v_{i}\in V_{\mathbf{Z}}}S_{i}\). If there is a spatial community \(\mathbf{Z}\subset\mathbf{G}\), we assume that the weights of edges in \(\mathbf{Z}\) and outside \(\mathbf{Z}\) are generated with probability \(p\) and \(q\), respectively. To ensure that \(\mathbf{Z}\) is a significant spatial community, it needs to prove that the null hypothesis (\(H_{0}\): \(p=q\)) is false and the alternative hypothesis (\(H_{1}\): \(p>q\)) is true. The likelihood ratio statistic for a spatial community \(\mathbf{Z}\) can be defined as follows:  
\[LR(\mathbf{Z})=\frac{L(\mathbf{Z},p,q)}{L_{0}}=\left\{ \begin{pmatrix}\frac{W(\mathbf{Z})}{ \mu(\mathbf{Z})}\end{pmatrix} ^{W(\mathbf{Z})} \begin{pmatrix}\frac{W(\mathbf{G})-W(\mathbf{Z})} {\mu(\mathbf{G})-\mu(\mathbf{Z})}\end{pmatrix} ^{W(\mathbf{G})-W(\mathbf{Z})}&\text{if }\frac{W(\mathbf{Z})}{\mu(\mathbf{Z})}>\frac{W(\mathbf{G})-W(\mathbf{Z})}{\mu(\mathbf{G})-\mu(\bm {Z})}\\ 1&\text{otherwise}\end{pmatrix}\right. \tag{1}\]  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Notations** & **Meaning** \\ \hline \(V\) & The set of vertices \\ \(E\) & The set of edges \\ \(W\) & The set of weights \\ \(G\) & A spatially embedded graph \\ \(\mathbf{S}\) & The strength sequence of a graph \\ \(S_{i}\) & The strength of a vertex \(v_{i}\) \\ \(\mathbf{Z}\) & A spatial community in \(\mathbf{G}\) \\ \(S(\mathbf{Z})\) & The sum of strengths of \(\  
where \(L(\mathbf{Z},p,q)\) is the likelihood function under \(H_{1}\), \(L_{0}\) is the likelihood function under \(H_{0}\), \(W(\mathbf{Z})\) is the sum of weights in \(\mathbf{Z}\), \(W(\mathbf{G})\) is the sum of weights in \(\mathbf{G}\), \(\mu(\mathbf{Z})=S^{2}(\mathbf{Z})/4W(\mathbf{G})\) is the expected sum of weights of \(\mathbf{Z}\) under \(H_{0}\), \(\mu(\mathbf{G})\) is the expected sum of weights of graph \(\mathbf{G}\) under \(H_{0}\), and in this study, \(\mu(\mathbf{G})=W(\mathbf{G})\). Detailed derivation of the likelihood ratio statistic can be found in [15]. Under the null hypothesis, for a spatial community \(\mathbf{Z}\subset\mathbf{G}\), the probability that the sum of observed weights of \(\mathbf{Z}\) is equal to or greater than \(W_{i}\) is as follows:  
\[\mathrm{P}(W(\mathbf{Z})\geq W_{i})=1-\sum_{j=0}^{W_{i}-1}\frac{\lambda_{i0}^{j} \mathrm{e}^{-\lambda_{i0}}}{j!} \tag{2}\]  
\[\lambda_{i0}=\frac{W(\mathbf{G})}{\mu(\mathbf{G})}.\mu(\mathbf{Z}) \tag{3}\]  
To evaluate the significance of the spatial communities, we constructed a random graph with a given sequence of expected strengths [28]. To construct a random graph \(\mathbf{G}^{\prime}\) for \(\mathbf{G}\), an inhomogeneous Poisson process \(PI\) (\(PI\) has the same number of vertices and the same sequence of expected strengths as \(\mathbf{G}\)) was used to generate the weights of the edges in \(\mathbf{G}^{\prime}\). The probability that two vertices form an edge is determined by \(PI\), proportional to the strength of the vertices of that edge [29]. The \(p\)-value of each community can be calculated as follows:  
\[p_{\mathbf{Z}}=\frac{\sum_{k=1}^{N_{\mathrm{rep}}}i_{k}}{N_{\mathrm{rep}}} \tag{4}\]  
where \(N_{\mathrm{rep}}\) is the number of random graphs. \(I\) is an indicator variable; in the \(k\)th simulation, if \(LR_{nm}(\mathbf{Z})>LR(\mathbf{Z})\), then \(I_{k}=1\); otherwise \(I_{k}=0\) (\(LR_{nm}(\mathbf{Z})\) is the likelihood ratio value of \(\mathbf{Z}\) calculated in the random graph). The false discovery rate method [30] was used to deal with the multiple hypothesis testing problems in detecting the spatial communities.