# Detecting Dynamic Communities in Vehicle Movements Using Ant Colony Optimization
## 2 Methods
### Identification of Dynamic Communities  
After the communities at each snapshot were obtained, the evolution of communities needed to be further identified. The similarity between two communities identified at continuous snapshots was measured using the Jaccard coefficient:  
\[A\big{(}\mathbf{C},\mathbf{C}^{\prime}\big{)}=\frac{|\mathbf{C}_{t}\cap\mathbf{C}^{\prime}_{t+ 1}|}{|\mathbf{C}_{t}\cup\mathbf{C}^{\prime}_{t+1}|} \tag{6}\]  
where \(\mathbf{C}_{t}\) and \(\mathbf{C}_{t+1}\) represent two communities identified at snapshots \(t\) and \(t+1\), respectively, \(|\mathbf{C}_{t}\cap\mathbf{C}_{t+1}|\) is the number of common nodes in \(\mathbf{C}_{t}\) and \(\mathbf{C}_{t+1}\), and \(|\mathbf{C}_{t}\cup\mathbf{C}_{t+1}|\) is the number of nodes in the union of \(\mathbf{C}_{t}\) and \(\mathbf{C}_{t+1}\).  
There are usually seven kinds of community evolution processes [12]: continuation, splitting, merging, growth, contraction, birth, and death (Figure 2). In this study, we defined different rules to identify these community evolution processes.  
1. Continuation means that a community remains almost unchanged at the next time snapshot. If the similarity between two communities identified at continuous snapshots is greater than 0.9, then the evolution process is identified as continuation.
2. Splitting means that a community is split into multiple communities at the next time snapshot. If the sum of the similarity between multiple communities at \(t+1\) and a community at \(t\) is greater than 0.9, then the evolution process is identified as splitting.
3. Merging indicates that multiple communities merge into one community at the next time snapshot. If the sum of the similarity between a community at \(t\) and multiple communities at \(t-1\) is greater than 0.9, then the evolution process is identified as merging.
4. Growth indicates that the size of a community increases obviously at the next time snapshot. If the similarity between a community at \(t-1\) (\(\mathbf{C}_{t-1}\)) and a community at \(t(\mathbf{C}_{t})\) is greater than 0.75, and the size of \(\mathbf{C}_{t}\) is larger than that of \(\mathbf{C}_{t-1}\), then the evolution process is identified as growth.
5. Contraction means that the size of a community decreases obviously at the next snapshot. If the similarity between \(\mathbf{C}_{t}\) and \(\mathbf{C}_{t+1}\) is greater than 0.75, and the size of \(\mathbf{C}_{t+1}\) is smaller than that of \(\mathbf{C}_{t}\), then the evolution process is identified as contraction.
6. Birth occurs when a new community emerges without a predecessor. The unmatched communities at the next snapshot are identified as birth communities.
7. Death occurs when a community disappears without a successor. The unmatched communities at the previous snapshot are identified as death communities.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameter** & **Name** & **Value** \\ \hline Number of ants & \(N_{att}\) & Number of candidate edges \\ Number of elite ants & \(N_{e}\) & 20 \\ Maximum number of iterations & \(N_{ite}\) & 500 \\ Pheromone evaporation coefficient & \(M_{pe}\) & 0.1 \\ Significance level for identifying spatial communities & \(\alpha\) & 0.05 \\ Significance level for identifying & \(\beta\) & 0.1 \\ candidate road segments & \(N_{np}\) & 99 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Explanation of the parameters and their values used for ant colony optimization.