Detecting spatial community structure in movements

This paper presents a new methodology and evaluation experiments on the detection of spatial community structure in movements, which can reveal unknown spatial constructs and boundaries. While there are numerous existing approaches for community structure detection in spatial networks using either general-purpose methods or spatially modified extensions, they are usually designed and applied without controlled evaluation and understanding of their robustness in finding the underlying spatial communities. Towards addressing this challenge, we develop a new approach, Spatial Tabu Optimization for Community Structure (STOCS), which transforms trajectory data to a spatial network, integrates different community structure measures (e.g. modularity or edge ratio), and partitions the network into geographic regions to discover spatial communities in movements. We systematically evaluate and compare the new approach with existing methods using synthetic datasets that have known spatial community structures. Evaluation results show that general-purpose (non-spatial) methods are not robust for detecting spatial structures - their outcomes vary dramatically for the same data with different levels of spatial aggregation (resolution), data sampling, or data noise. STOCS is substantially more robust in discovering underlying spatial structures. Last, we present two case studies with animal movements and urban population movements to demonstrate the application of the approach.