# Detecting Dynamic Communities in Vehicle Movements Using Ant Colony Optimization
## 2 Methods
### Evolutionary Ant Colony Optimization Method  
In this study, we aimed to detect communities at each snapshot based on the idea of evolutionary clustering. Evolutionary clustering requires that the communities on each timestamp should remain faithful to the current data as much as possible, and should be similar to the communities discovered in the previous snapshot [18]. To balance both partition quality and temporal partition coherence at each snapshot, we developed an evolutionary ant colony optimization method based on ACOScan. First, the statistically significant spatial communities at the initial snapshot were identified using ACOScan. Ant colony optimization [31] is a typical swarm intelligence method inspired by the foraging behavior of ants; some ants leave chemicals (called pheromones) on the ground to mark paths that are favorable for other colony members to follow [32]. Connecting road segments to form communities can be regarded as the identification of the optimal path found by ants. In ACOScan, the spatial scan statistic described in Section 2.1 was used as the objective function for community detection. To narrow the search space and increase the stability for community detection, we first identified significant road segments as candidate road segments. For each road segment, we calculated \(P(W(\mathbf{Z})\geq W(\mathbf{N}_{i}))\) using Equations (2) and (3); if the value was less than the significance level \(\beta\) (\(\beta=0.1\)), then that road segment was identified as a candidate road segment. The edge connecting two candidate road segments was identified as a candidate edge. The candidate edges were used as basic units for detecting communities. ACO was used as the heuristic method for searching communities. Second, the communities identified at the initial snapshot were considered to detect communities at the current snapshot. ACO and spatial scan statistic were also used as the heuristic method and the objective function for community detection, respectively. Pheromones play a key role in searching communities using ACO [31; 33]. Therefore, we proposed two pheromone reward strategies to consider the effect of communities identified at the initial snapshot on those identified at the current snapshot:  
1. For each edge in community \(C_{N}\) identified at the initial snapshot, we added an additional pheromone value \(L_{n}/L_{s}\) at the current snapshot, where \(L_{n}\) is the likelihood ratio value of \(C_{n}\) at the initial snapshot, and \(L_{s}\) is the sum of the likelihood ratio values of all communities at the initial snapshot. 2. When we determined whether two edges \(r_{i}\) and \(r_{j}\) should be combined at the current snapshot, a connectivity indicator \(\delta(r_{i},r_{j})\) was defined. If \(r_{i}\) and \(r_{j}\) were in the same community at the initial snapshot, \(\delta(r_{i},r_{j})=1\); otherwise, \(\delta(r_{i},r_{j})=0\). Based on the above two strategies, the initial pheromone (\(Tr\)) of each edge at the current snapshot can be defined as follows:  
\[Tr=M_{ip}+\frac{L_{n}}{L_{s}}+\gamma\times\delta(r_{i},r_{j}) \tag{5}\]  
where \(M_{ip}\) is the pheromone of each edge determined based on the weight of that edge at the current snapshot, and \(\gamma\) is a balance coefficient. The first term of Equation (5) was used to consider the quality of communities identified at the current snapshot. The last two terms of Equation (5) were used to consider the temporal partition coherence between two consecutive snapshots. To search communities at the current snapshot, a candidate edge was randomly selected as the starting edge for each ant, and the roulette-wheel selection method [34] was used to select the spatially adjacent candidate edges according to \(Tr\). Each ant stopped walking until the number of candidate edges in the community reached \(L\) (\(L\) is the maximum size of a spatial community). The paths of each ant formed a community.