Understanding human mobility is the key problem in many applications such as location-based services and recommen- dation systems. The mobility of a smartphone user can be modeled by a movement graph, in which the nodes repre- sent 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 sum- marization, the movement graph becomes smaller resulting in a reduction in the required time and storage to deploy graph algorithms. We specically investigate the eect of summarization on two algorithms related to human mobil- ity 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-o between accuracy, storage space and speed can be controlled by the compression ratio. As an illustra- tion, if the size of the graph is reduced to half, the similarity algorithm becomes 4 times faster while the correlation be- tween similarities of coarse and original graphs is 0.98.
@inproceedings{sadri2017summarizing,
title={Summarizing movement graph for mobility pattern analysis},
author={Sadri, Amin and Ren, Yongli and Salim, Flora D},
booktitle={Proceedings of the Knowledge Capture Conference},
pages={1--4},
year={2017}
}
© 2021 Flora Salim - CRUISE Research Group.