@inproceedings{detecting-urban-black-holes-based-on-human-mobility-data, author = {Hong, Liang and Zheng, Yu and Yung, Duncan and Shang, Jingbo and Zou, Lei}, title = {Detecting Urban Black Holes Based on Human Mobility Data}, booktitle = {}, year = {2015}, month = {November}, abstract = { Many types of human mobility data, such as flows of taxicabs, card swiping data of subways, bike trip data and Call Details Records (CDR), can be modeled by a Spatio-Temporal Graph (STG). STG is a directed graph in which vertices and edges are associated with spatio-temporal properties (e.g. the traffic flow on a road and the geospatial location of an intersection). In this paper, we instantly detect interesting phenomena, entitled black holes and volcanos, from an STG. Specifically, a black hole is a subgraph (of an STG) that has the overall inflow greater than the overall outflow by a threshold, while a volcano is a subgraph with the overall outflow greater than the overall inflow by a threshold (detecting volcanos from an STG is proved to be equivalent to the detection of black holes). The online detection of black holes/volcanos can timely reflect anomalous events, such as disasters, catastrophic accidents, and therefore help keep public safety. The patterns of black holes/volcanos and the relations between them reveal human mobility patterns in a city, thus help formulate a better city planning or improve a system’s operation efficiency. Based on a well-designed STG index, we propose a two-step black hole detection algorithm: The first step identifies a set of candidate grid cells to start from; the second step expands an initial edge in a candidate cell to a black hole and prunes other candidate cells after a black hole is detected. Then, we adapt this detection algorithm to a continuous black hole detection scenario. We evaluate our method based on Beijing taxicab data and the bike trip data in New York, finding urban anomalies and human mobility patterns. }, publisher = {ACM SIGSPATIAL 2015}, url = {https://www.microsoft.com/en-us/research/publication/detecting-urban-black-holes-based-on-human-mobility-data/}, address = {}, pages = {}, journal = {}, volume = {}, chapter = {}, isbn = {}, }