Paper Info
Title
Detecting urban black holes based on human mobility data.
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.
Year
DOI
Venue
2015
10.1145/2820783.2820811
SIGSPATIAL/GIS
Keywords
Field
DocType
Urban computing, Spatio-temporal graph, Black hole detection
Geospatial analysis,Data mining,Traffic flow,Vertex (geometry),Computer science,Directed graph,Black hole,Urban computing,Inflow,Outflow
Conference
Citations 
PageRank 
References 
24
0.96
23
Authors
5
Name
Order
Citations
PageRank
Liang Hong119333.79
Yu Zheng28939432.87
Duncan Yung3241.30
Jingbo Shang48815.88
Lei Zou5116168.43