Summarizing Movement Graph for Mobility Pattern Analysis

Understanding human mobility is the key problem in many applications such as location-based services and recommendation systems. The mobility of a smartphone user can be modeled by a movement graph, in which the nodes represent locations and the edges are distances or traveling times between the locations. However, the resulting graph would be too big to be stored and queried on resource-devices such as smartphones. In this paper, we deploy a state-of-the-art graph summarization method to produce an abstract (coarse) graph easy to be processed and queried. After summarization, the movement graph becomes smaller resulting in a reduction in the required time and storage to deploy graph algorithms. We specifically investigate the effect of summarization on two algorithms related to human mobility mining: location prediction and similarity mining. The location prediction algorithm on the coarse graph causes coarse-grain results. Regarding computing the similarity, summarization reduces the computational cost but at the same time increases the uncertainty of the results. We show that the trade-off between accuracy, storage space and speed can be controlled by the compression ratio. As an illustration, if the size of the graph is reduced to half, the similarity algorithm becomes 4 times faster while the correlation between similarities of coarse and original graphs is 0.98.