# Detecting Dynamic Communities in Vehicle Movements Using Ant Colony Optimization
## 1 Introduction
For example, the global optimization update strategy [16] first defines a global objective function (e.g., modularity), and then uses the communities found at time \(t-1\) as seeds to optimize the communities at \(t\). The rule-based update strategy [17] defines a series of rules (e.g., addition/deletion of nodes/edges) to determine how the communities evolve when the network changes. The evolutionary clustering strategy [18; 19; 20] attempts to balance both partition quality and temporal partition coherence at each snapshot. Temporal trade-off methods do not require a complete knowledge of the network history; therefore, they are useful for real-time community detection [6]. However, without spatial contiguity constraints, existing temporal trade-off methods are usually not robust [21]. In addition, the statistical significance of the identified communities at each snapshot cannot be ensured; therefore, these methods are very likely to identify some spurious communities [22]. Unlike the instant optimal and temporal trade-off methods, cross-time methods aim to find dynamic communities from all snapshots. These kinds of methods are suitable for detecting communities that are coherent over the long-term, but are not suitable for identifying real-time dynamic communities [6]. Cross-time methods first transform networks at all snapshots into a single network, and then identify dynamic communities from the single network using existing static community detection methods. There are two kinds of edges in this single network, i.e., the relationships between nodes at the same snapshot, and the relationships between nodes belonging to adjacent snapshots. Dynamic communities can be discovered using different constraints, i.e., (1) fixed memberships and fixed properties [23], where communities remain the same throughout the studied period; (2) fixed memberships and evolving properties [24], where communities can be non-homogeneous over time, e.g., the interactions among nodes in a community may increase or decrease over time; (3) evolving memberships and fixed properties [25], where node memberships can be varied over time; and (4) evolving memberships and evolving properties [4; 26], where during the studied period, communities can appear or disappear, node memberships can be varied, and the densities of communities can also change. In this study, we aim to identify real-time dynamic communities from vehicle movements. Although existing instant optimal methods and temporal trade-off methods can be used to detect real-time dynamic communities, the discovery of irregular-shaped and statistically significant dynamic communities in vehicle movements is still challenging. To overcome this challenge, we propose an evolutionary ant colony optimization method (EACO) for detecting dynamic communities in vehicle movements. The main contributions of this study include the following three aspects:  
1. We propose a new pheromone initialization strategy to upgrade an ant-colony-optimization-based spatial scan statistic (ACOScan) [15] to identify dynamic communities in vehicle movements. The proposed method can not only balance both partition quality and temporal partition coherence at each snapshot, but also identify irregular-shaped communities. 2. We construct a significance test to evaluate the statistical significance of the identified dynamic communities. Therefore, some weakly interacting or spurious communities can be eliminated. 3. The proposed method can be regarded as a spatial extension of evolutionary clustering. Compared with existing spatial community detection methods (e.g., ACOScan), the proposed method is useful for understanding spatiotemporal interactions in a city. The effectiveness and superiority of EACO were verified using both simulated and Beijing taxi trajectories data. The dynamic communities identified by EACO are of great value for understanding the evolution of urban spatial structure. The rest of this paper is organized as follows: Section 2 describes the proposed method in detail.