# Detecting Dynamic Communities in Vehicle Movements Using Ant Colony Optimization
## 1 Introduction  
In the era of big data, vast amounts of vehicle movement data (e.g., taxi Global Positioning System (GPS) trajectories) provide new opportunities to understand spatiotemporal interactions between different places in a city [1]. The vehicle movements can be transformed into a weighted, spatially embedded network, where the places (e.g., road segments) in a city are regarded as nodes, and the origin and destination (OD) pairs between the places can be considered as weighted edges [2]. The spatially embedded network usually evolves with time, and can be regarded as a kind of dynamic graph. In this dynamic graph, there are usually some subgraphs or dynamic communities, where the movements (e.g., OD pairs) within each community are significantly more than those between that community and other communities [3]. The dynamic communities discovered in vehicle movements play a crucial role in understanding the dynamic organization of urban structures, which can facilitate urban planning and management [4]. Identifying dynamic communities is also useful for modelling traffic correlation patterns in a city, which are helpful for traffic forecasting and traffic control [5]. Detecting dynamic communities in vehicle movements has been paid more attentions in recent years [4]. Existing studies usually divide the time dimension into a series of snapshots. Therefore, a dynamic graph can be constructed. Three classes of dynamic community detection methods are currently available, i.e., instant optimal, temporal trade-off, and cross-time methods [6]. Instant optimal methods first identify communities at each snapshot using existing static community detection methods (e.g., modularity-based methods [7; 8] and information-theoretic methods [9; 10]), and then match the communities discovered at snapshot \(t\) with those discovered at snapshot \(t-1\). Different strategies have been developed to match the communities discovered at continuous snapshots. For example, the iterative similarity-based methods [11] use a quality function (e.g., the Jaccard coefficient [12]) to measure the similarity between the communities at different snapshots, and consider the communities with high similarity in adjacent timesteps as part of the same dynamic community. The iterative core-nodes-based methods [13] define one or several representative node(s) for each community (e.g., the node with the highest centrality metric value), and identify communities containing the same representative node(s) at adjacent snapshots as the same dynamic community. The multistep matching methods [14] not only match the communities between adjacent snapshots, but also match the communities across several snapshots. Instant optimal methods are easy to implement. However, the instability of existing community detection methods (i.e., the same methods usually discover different communities from the same network) may lead to spurious dynamic communities [6]. In addition, the sizes and geometric shapes of communities in vehicle movements are usually varied [5]; however, existing community detection methods usually assume that the shapes of the communities are approximately circular [15]. To alleviate the instability problem of instant optimal methods, temporal trade-off methods have been developed. These methods assume that communities at snapshot \(t\) not only depend on the network at snapshot \(t\), but also depend on the communities identified at snapshot \(t-1\). By using the previously identified communities, temporal trade-off methods can identify more stable dynamic communities [6]. Temporal trade-off methods involve two iterative steps: initialization and update. Firstly, the communities are discovered at the initial snapshot \(t\), and then, for the next snapshot \(t+1\), the communities are detected using the network at \(t+1\) and the communities at \(t\). Different update strategies have been developed.