Abstract
The rapid inclusion of tracking technologies in our personal devices opened the doors to the analysis and visualization of large sets of geo-spatial mobility data, in particular GPS traces.
In this tutorial we will present a concise and intuitive overview on both fundamental modeling principles of human mobility, and machine learning models applicable to specific mobility-related problems.
In particular, we will review the state of the art of four main aspects in human mobility: (1) the human mobility data landscape; (2) the privacy issues with human mobility data; (3) key metrics
and measures; (4) generative and phenomenological models at the level of individual, population and mixture of the two; (5) machine learning models for next location prediction.
The availability of geo-spatial mobility data (e.g., GPS traces) is a trend that will grow in the near future. In particular, this will happen when the shift from traditional vehicles to autonomous,
self-driving, vehicles, will transform our society, the economy and the environment. For this reason, understanding and modeling human mobility is of paramount importance for many present and
future applications such as traffic forecasting, urban planning, estimating migratory flows, and epidemic modeling.
In this tutorial we will present a concise and intuitive overview on both fundamental modeling principles of human mobility, and machine learning models applicable to specific mobility-related problems.
In particular, we will review the state of the art of four main aspects in human mobility:
Just a basic knowledge of data mining techniques and statistical modeling is required from the audience.
- The human mobility data landscape, from GPS traces to location-based social network data;
- Key metrics and measures, as well as a short overview of the fundamental physics behind human mobility;
- Generative and phenomenological models at the level of individual, population and mixture of the two;
- Machine learning models, with a particular focus on deep learning, for next location prediction.
Just a basic knowledge of data mining techniques and statistical modeling is required from the audience.
- The human mobility data landscape
A natural starting point is to describe the nature of empirical data which has been used in mobility research. In this part, we outline the main sources available for mobility research and the relevant information that can be extracted from them. - Measures of individual and collective mobility
In this part, we will review some of the fundamental metrics and representations used to characterize mobility, such as trip distance [11, 15], radius of gyration [15, 28, 27], mobility entropy [37, 20], origin-destination matrix [10], mobility motifs [33, 16]. - Generative models of human mobility: from mechanisms to algorithms
This part will review the state of the art for generative models at two different levels: individual level (i.e., generation of individual spatio-temporal trajectories) [28, 25, 26, 4, 36] and population (i.e., generation of mobility fluxes) [34, 17, 8, 41, 35, 27]. - Where’s next? Machine Learning models for human mobility
After a short review of various machine learning models for human mobility [45, 22, 23, 39] we will review recent advances based on deep learning, with particular focus on next location prediction [19, 46, 43, 42, 14].
Materials
Slides from ECML/PKDD 2018 available here.
Speakers
- Filippo Simini
Lecturer in the department of Engineering Mathematics at the University of Bristol, UK. He combines methods from statistical physics, complex systems and data science to discover and characterise the distinctive statistical patterns of a system and to develop mathematical models to describe the system’s dynamics and emergent properties. He is particularly interested in interdisciplinary problems and applications, including collective and individual human mobility, transportation, ecological networks and population dynamics. He has publications in Nature, PNAS, and Nature Communications and his work has impact and applications on epidemic modelling, the assessment of future mobility scenarios and emergency planning. - Gianni Barlacchi
PhD candidate in Computer Science at the University of Trento (Italy). His primary research focuses on developing novel machine learning models and neural networks to predict people’s activities from textual and geo-spatial data. Gianni has been a visiting scholar at Telefonica I+D and IBM Research. He has been awarded in 2017 by the ACM CIKM Analyticup 2017 competition on mobility, and awarded by IBM in 2015 for the Watson Services Challenge. His PhD is supported with a fellowship by TIM (Telecom Italia). - Luca Pappalardo
Post-doc at the Institute of Information Science and Technologies (ISTI) at the Italian National Research Council (CNR) in Pisa. His research focuses on the analysis of Big Data sources describing human mobility, such as mobile phone data, GPS traces from private vehicles, checkins from location-based social networks. He has published over 20 papers on human mobility analysis and modeling in top conferences and journals relevant to the field, such as ACM TIST, Data Mining and Knowledge Discovery (DMKD), ACM CIKM, IEEE ICDM, IEEE DSAA, IEEE BigData and Nature Communications. He has been awarded in 2017 by the ACM CIKM Analyticup 2017 competition on human mobility analysis, and awarded by Google in 2014 at a contest on innovative ideas on the usage of Big Data sources as support for official statistics.
References
[1] Abul, O., Bonchi, F., and Nanni, M. Never walk alone: Uncertainty for anonymity in moving objects databases. In Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, April 7-12, 2008, Cancún, México (2008), pp. 376–385.
[2] Balcan, D., Colizza, V., Gonçalves, B., Hu, H., Ramasco, J. J., and Vespignani, A. Multiscale mobility networks and the spatial spreading of infectious diseases. Proceedings of the National Academy of Sciences 106, 51 (2009), 21484–21489.
[3] Barbosa, H., Barthelemy, M., Ghoshal, G., James, C. R., Lenormand, M., Louail, T., Menezes, R., Ramasco, J. J., Simini, F., and Tomasini, M. Human mobility: Models and applications. Physics Reports (2018).
[4] Barbosa, H., de Lima-Neto, F. B., Evsukoff, A., and Menezes, R. The effect of recency to human mobility. EPJ Data Science 4, 1 (2015), 21.
[5] Barlacchi, G., De Nadai, M., Larcher, R., Casella, A., Chitic, C., Torrisi, G., Antonelli, F., Vespignani, A., Pentland, A., and Lepri, B. A multi-source dataset of urban life in the city of milan and the province of trentino. Scientific data 2 (2015), 150055.
[6] Barlacchi, G., Perentis, C., Mehrotra, A., Musolesi, M., and Lepri, B. Are you getting sick? predicting influenza-like symptoms using human mobility behaviors. EPJ Data Science 6, 1 (2017), 27.
[7] Basu, A., Monreale, A., Corena, J. C., Giannotti, F., Pedreschi, D., Kiyomoto, S., Miyake, Y., Yanagihara, T., and Trasarti, R. A privacy risk model for trajectory data. In Trust Management VIII, J. Zhou, N. Gal-Oz, J. Zhang, and E. Gudes, Eds., vol. 430 of IFIP Advances in Information and Communication Technology. Springer Berlin Heidelberg, 2014, pp. pp 125–140.
[8] Beiró, M. G., Panisson, A., Tizzoni, M., and Cattuto, C. Predicting human mobility through the assimilation of social media traces into mobility models. EPJ Data Science 5, 1 (2016), 30.
[9] Blondel, V. D., Decuyper, A., and Krings, G. A survey of results on mobile phone datasets analysis. EPJ Data Science 4, 1 (2015), 10.
[10] Bonnel, P., Hombourger, E., Olteanu-Raimond, A.-M., and Smoreda, Z. Passive mobile phone dataset to construct origin-destination matrix: Potentials and limitations. Transportation Research Procedia 11 (2015), 381 – 398.
[11] Brockmann, D., Hufnagel, L., and Geisel, T. The scaling laws of human travel. Nature 439, 7075 (01 2006), 462–465.
[12] Cho, E., Myers, S. A., and Leskovec, J. Friendship and mobility: User movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2011), KDD ’11, ACM, pp. 1082– 1090.
[13] de Montjoye, Y.-A., Hidalgo, C. A., Verleysen, M., and Blondel, V. D. Unique in the crowd: The privacy bounds of human mobility. Scientific Reports 3 (2013).
[14] Feng, J., Li, Y., Zhang, C., Sun, F., Meng, F., Guo, A., and Jin, D. Deepmove: Predicting human mobility with attentional recurrent networks.
[15] Gonzalez, M. C., Hidalgo, C. A., and Barabasi, A.-L. Understanding individual human mobility patterns. Nature 453, 7196 (2008), 779.
[16] Jiang, S., Yang, Y., Gupta, S., Veneziano, D., Athavale, S., and González, M. C. The timegeo modeling framework for urban mobility without travel surveys. Proceedings of the National Academy of Sciences 113, 37 (2016), E5370–E5378.
[17] Kang, C., Liu, Y., Guo, D., and Qin, K. A generalized radiation model for human mobility: Spatial scale, searching direction and trip constraint. PLoS ONE 10, 11 (11 2015), 1–11.
[18] Lin, M., and Hsu, W.-J. Mining gps data for mobility patterns: A survey. Pervasive and Mobile Computing 12 (2014), 1–16.
[19] Liu, Q., Wu, S., Wang, L., and Tan, T. Predicting the next location: A recurrent model with spatial and temporal contexts. In AAAI (2016), pp. 194–200.
[20] Lu, X., Wetter, E., Bharti, N., Tatem, A. J., and Bengtsson, L. Approaching the limit of predictability in human mobility. Scientific Reports 3 (10 2013).
[21] Lv, Y., Duan, Y., Kang, W., Li, Z., and Wang, F.-Y. Traffic flow prediction with big data: a deep learning approach. IEEE Transactions on Intelligent Transportation Systems 16, 2 (2015), 865–873.
[22] Mathew, W., Raposo, R., and Martins, B. Predicting future locations with hidden markov models. In Proceedings of the 2012 ACM conference on ubiquitous computing (2012), ACM, pp. 911–918.
[23] Monreale, A., Pinelli, F., Trasarti, R., and Giannotti, F. Wherenext: a location predictor on trajectory pattern mining. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (2009), KDD’09, ACM, pp. 637–646.
[24] Monreale, A., Rinzivillo, S., Pratesi, F., Giannotti, F., and Pedreschi, D. Privacy-by-design in big data analytics and social mining. EPJ Data Science 3, 1 (2014).
[25] Pappalardo, L., Rinzivillo, S., and Simini, F. Human mobility modelling: Exploration and preferential return meet the gravity model. Procedia Computer Science 83 (2016), 934 – 939. The 7th International Conference on Ambient Systems, Networks and Technologies (ANT 2016) / The 6th International Conference on Sustainable Energy Information Technology(SEIT-2016) / Affiliated Workshops.
[26] Pappalardo, L., and Simini, F. Modelling individual routines and spatio-temporal trajectories in human mobility. arXiv preprint arXiv:1607.05952 (2016).
[27] Pappalardo, L., and Simini, F. Data-driven generation of spatio-temporal routines in human mobility. Data Mining and Knowledge Discovery (2017), 1–43.
[28] Pappalardo, L., Simini, F., Rinzivillo, S., Pedreschi, D., Giannotti, F., and Barabasi, A.-L. Returners and explorers dichotomy in human mobility. Nature Communications 6 (2015).
[29] Pellungrini, R., Pappalardo, L., Pratesi, F., and Monreale, A. A data mining approach to assess privacy risk in human mobility data. ACM Trans. Intell. Syst. Technol. 9, 3 (Dec. 2017), 31:1–31:27.
[30] Polson, N. G., and Sokolov, V. O. Deep learning for short-term traffic flow prediction. Transportation Research Part C: Emerging Technologies 79 (2017), 1–17.
[31] Rubinstein, I. S. Big data: The end of privacy or a new beginning? International Data Privacy Law (2013).
[32] Santi, P., Resta, G., Szell, M., Sobolevsky, S., Strogatz, S. H., and Ratti, C. Quantifying the benefits of vehicle pooling with shareability networks. Proceedings of the National Academy of Sciences 111, 37 (2014), 13290–13294.
[33] Schneider, C. M., Belik, V., Couronné, T., Smoreda, Z., and González, M. C. Unravelling daily human mobility motifs. Journal of The Royal Society Interface 10, 84 (2013).
[34] Simini, F., Gonzalez, M. C., Maritan, A., and Barabasi, A.-L. A universal model for mobility and migration patterns. Nature 484, 7392 (04 2012), 96–100.
[35] Simini, F., Maritan, A., and Néda, Z. Human mobility in a continuum approach. Plos one 8, 3 (2013), e60069.
[36] Song, C., Koren, T., Wang, P., and Barabasi, A.-L. Modelling the scaling properties of human mobility. Nature Physics 6, 10 (10 2010), 818–823.
[37] Song, C., Qu, Z., Blumm, N., and Barabási, A.-L. Limits of predictability in human mobility. Science 327, 5968 (2010), 1018–1021.[38] Spinsanti, L., Berlingerio, M., and Pappalardo, L. Mobility and geo-social networks. In Mobility Data: Modeling, Management, and Understanding. 2013, pp. 315–333.
[39] Wang, D., Pedreschi, D., Song, C., Giannotti, F., and Barabási, A. Human mobility, social ties, and link prediction.
In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011 (2011), KDD’11, pp. 1100–1108.
[40] Wang, H., and Li, Z. Region representation learning via mobility flow. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (2017), ACM, pp. 237–246.
[41] Yan, X.-Y., Zhao, C., Fan, Y., Di, Z., and Wang, W.-X. Universal predictability of mobility patterns in cities. Journal of The Royal Society Interface 11, 100 (2014), 20140834.
[42] Yang, C., Sun, M., Zhao, W. X., Liu, Z., and Chang, E. Y. A neural network approach to jointly modeling social networks and mobile trajectories. ACM Transactions on Information Systems (TOIS) 35, 4 (2017), 36.
[43] Yao, S., Hu, S., Zhao, Y., Zhang, A., and Abdelzaher, T. Deepsense: A unified deep learning framework for time-series mobile sensing data processing. In Proceedings of the 26th International Conference on World Wide Web (2017), WWW’17, pp. 351–360.
[44] Yuan, N. J., Zheng, Y., and Xie, X. Discovering functional zones in a city using human movements and points of interest. In Spatial Analysis and Location Modeling in Urban and Regional Systems. Springer, 2018, pp. 33–62.
[45] Zhang, C., Zhang, K., Yuan, Q., Zhang, L., Hanratty, T., and Han, J. Gmove: Group-level mobility modeling using geo-tagged social media. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2016), KDD’16, ACM, pp. 1305–1314.
[46] Zhang, J., Zheng, Y., and Qi, D. Deep spatio-temporal residual networks for citywide crowd flows prediction. In AAAI (2017), pp. 1655–1661.
[47] Zhao, K., Tarkoma, S., Liu, S., and Vo, H. Urban human mobility data mining: An overview. In Big Data (Big Data), 2016 IEEE International Conference on (2016), IEEE, pp. 1911–1920.
[2] Balcan, D., Colizza, V., Gonçalves, B., Hu, H., Ramasco, J. J., and Vespignani, A. Multiscale mobility networks and the spatial spreading of infectious diseases. Proceedings of the National Academy of Sciences 106, 51 (2009), 21484–21489.
[3] Barbosa, H., Barthelemy, M., Ghoshal, G., James, C. R., Lenormand, M., Louail, T., Menezes, R., Ramasco, J. J., Simini, F., and Tomasini, M. Human mobility: Models and applications. Physics Reports (2018).
[4] Barbosa, H., de Lima-Neto, F. B., Evsukoff, A., and Menezes, R. The effect of recency to human mobility. EPJ Data Science 4, 1 (2015), 21.
[5] Barlacchi, G., De Nadai, M., Larcher, R., Casella, A., Chitic, C., Torrisi, G., Antonelli, F., Vespignani, A., Pentland, A., and Lepri, B. A multi-source dataset of urban life in the city of milan and the province of trentino. Scientific data 2 (2015), 150055.
[6] Barlacchi, G., Perentis, C., Mehrotra, A., Musolesi, M., and Lepri, B. Are you getting sick? predicting influenza-like symptoms using human mobility behaviors. EPJ Data Science 6, 1 (2017), 27.
[7] Basu, A., Monreale, A., Corena, J. C., Giannotti, F., Pedreschi, D., Kiyomoto, S., Miyake, Y., Yanagihara, T., and Trasarti, R. A privacy risk model for trajectory data. In Trust Management VIII, J. Zhou, N. Gal-Oz, J. Zhang, and E. Gudes, Eds., vol. 430 of IFIP Advances in Information and Communication Technology. Springer Berlin Heidelberg, 2014, pp. pp 125–140.
[8] Beiró, M. G., Panisson, A., Tizzoni, M., and Cattuto, C. Predicting human mobility through the assimilation of social media traces into mobility models. EPJ Data Science 5, 1 (2016), 30.
[9] Blondel, V. D., Decuyper, A., and Krings, G. A survey of results on mobile phone datasets analysis. EPJ Data Science 4, 1 (2015), 10.
[10] Bonnel, P., Hombourger, E., Olteanu-Raimond, A.-M., and Smoreda, Z. Passive mobile phone dataset to construct origin-destination matrix: Potentials and limitations. Transportation Research Procedia 11 (2015), 381 – 398.
[11] Brockmann, D., Hufnagel, L., and Geisel, T. The scaling laws of human travel. Nature 439, 7075 (01 2006), 462–465.
[12] Cho, E., Myers, S. A., and Leskovec, J. Friendship and mobility: User movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2011), KDD ’11, ACM, pp. 1082– 1090.
[13] de Montjoye, Y.-A., Hidalgo, C. A., Verleysen, M., and Blondel, V. D. Unique in the crowd: The privacy bounds of human mobility. Scientific Reports 3 (2013).
[14] Feng, J., Li, Y., Zhang, C., Sun, F., Meng, F., Guo, A., and Jin, D. Deepmove: Predicting human mobility with attentional recurrent networks.
[15] Gonzalez, M. C., Hidalgo, C. A., and Barabasi, A.-L. Understanding individual human mobility patterns. Nature 453, 7196 (2008), 779.
[16] Jiang, S., Yang, Y., Gupta, S., Veneziano, D., Athavale, S., and González, M. C. The timegeo modeling framework for urban mobility without travel surveys. Proceedings of the National Academy of Sciences 113, 37 (2016), E5370–E5378.
[17] Kang, C., Liu, Y., Guo, D., and Qin, K. A generalized radiation model for human mobility: Spatial scale, searching direction and trip constraint. PLoS ONE 10, 11 (11 2015), 1–11.
[18] Lin, M., and Hsu, W.-J. Mining gps data for mobility patterns: A survey. Pervasive and Mobile Computing 12 (2014), 1–16.
[19] Liu, Q., Wu, S., Wang, L., and Tan, T. Predicting the next location: A recurrent model with spatial and temporal contexts. In AAAI (2016), pp. 194–200.
[20] Lu, X., Wetter, E., Bharti, N., Tatem, A. J., and Bengtsson, L. Approaching the limit of predictability in human mobility. Scientific Reports 3 (10 2013).
[21] Lv, Y., Duan, Y., Kang, W., Li, Z., and Wang, F.-Y. Traffic flow prediction with big data: a deep learning approach. IEEE Transactions on Intelligent Transportation Systems 16, 2 (2015), 865–873.
[22] Mathew, W., Raposo, R., and Martins, B. Predicting future locations with hidden markov models. In Proceedings of the 2012 ACM conference on ubiquitous computing (2012), ACM, pp. 911–918.
[23] Monreale, A., Pinelli, F., Trasarti, R., and Giannotti, F. Wherenext: a location predictor on trajectory pattern mining. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (2009), KDD’09, ACM, pp. 637–646.
[24] Monreale, A., Rinzivillo, S., Pratesi, F., Giannotti, F., and Pedreschi, D. Privacy-by-design in big data analytics and social mining. EPJ Data Science 3, 1 (2014).
[25] Pappalardo, L., Rinzivillo, S., and Simini, F. Human mobility modelling: Exploration and preferential return meet the gravity model. Procedia Computer Science 83 (2016), 934 – 939. The 7th International Conference on Ambient Systems, Networks and Technologies (ANT 2016) / The 6th International Conference on Sustainable Energy Information Technology(SEIT-2016) / Affiliated Workshops.
[26] Pappalardo, L., and Simini, F. Modelling individual routines and spatio-temporal trajectories in human mobility. arXiv preprint arXiv:1607.05952 (2016).
[27] Pappalardo, L., and Simini, F. Data-driven generation of spatio-temporal routines in human mobility. Data Mining and Knowledge Discovery (2017), 1–43.
[28] Pappalardo, L., Simini, F., Rinzivillo, S., Pedreschi, D., Giannotti, F., and Barabasi, A.-L. Returners and explorers dichotomy in human mobility. Nature Communications 6 (2015).
[29] Pellungrini, R., Pappalardo, L., Pratesi, F., and Monreale, A. A data mining approach to assess privacy risk in human mobility data. ACM Trans. Intell. Syst. Technol. 9, 3 (Dec. 2017), 31:1–31:27.
[30] Polson, N. G., and Sokolov, V. O. Deep learning for short-term traffic flow prediction. Transportation Research Part C: Emerging Technologies 79 (2017), 1–17.
[31] Rubinstein, I. S. Big data: The end of privacy or a new beginning? International Data Privacy Law (2013).
[32] Santi, P., Resta, G., Szell, M., Sobolevsky, S., Strogatz, S. H., and Ratti, C. Quantifying the benefits of vehicle pooling with shareability networks. Proceedings of the National Academy of Sciences 111, 37 (2014), 13290–13294.
[33] Schneider, C. M., Belik, V., Couronné, T., Smoreda, Z., and González, M. C. Unravelling daily human mobility motifs. Journal of The Royal Society Interface 10, 84 (2013).
[34] Simini, F., Gonzalez, M. C., Maritan, A., and Barabasi, A.-L. A universal model for mobility and migration patterns. Nature 484, 7392 (04 2012), 96–100.
[35] Simini, F., Maritan, A., and Néda, Z. Human mobility in a continuum approach. Plos one 8, 3 (2013), e60069.
[36] Song, C., Koren, T., Wang, P., and Barabasi, A.-L. Modelling the scaling properties of human mobility. Nature Physics 6, 10 (10 2010), 818–823.
[37] Song, C., Qu, Z., Blumm, N., and Barabási, A.-L. Limits of predictability in human mobility. Science 327, 5968 (2010), 1018–1021.
[39] Wang, D., Pedreschi, D., Song, C., Giannotti, F., and Barabási, A. Human mobility, social ties, and link prediction.
In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011 (2011), KDD’11, pp. 1100–1108.
[40] Wang, H., and Li, Z. Region representation learning via mobility flow. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (2017), ACM, pp. 237–246.
[41] Yan, X.-Y., Zhao, C., Fan, Y., Di, Z., and Wang, W.-X. Universal predictability of mobility patterns in cities. Journal of The Royal Society Interface 11, 100 (2014), 20140834.
[42] Yang, C., Sun, M., Zhao, W. X., Liu, Z., and Chang, E. Y. A neural network approach to jointly modeling social networks and mobile trajectories. ACM Transactions on Information Systems (TOIS) 35, 4 (2017), 36.
[43] Yao, S., Hu, S., Zhao, Y., Zhang, A., and Abdelzaher, T. Deepsense: A unified deep learning framework for time-series mobile sensing data processing. In Proceedings of the 26th International Conference on World Wide Web (2017), WWW’17, pp. 351–360.
[44] Yuan, N. J., Zheng, Y., and Xie, X. Discovering functional zones in a city using human movements and points of interest. In Spatial Analysis and Location Modeling in Urban and Regional Systems. Springer, 2018, pp. 33–62.
[45] Zhang, C., Zhang, K., Yuan, Q., Zhang, L., Hanratty, T., and Han, J. Gmove: Group-level mobility modeling using geo-tagged social media. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2016), KDD’16, ACM, pp. 1305–1314.
[46] Zhang, J., Zheng, Y., and Qi, D. Deep spatio-temporal residual networks for citywide crowd flows prediction. In AAAI (2017), pp. 1655–1661.
[47] Zhao, K., Tarkoma, S., Liu, S., and Vo, H. Urban human mobility data mining: An overview. In Big Data (Big Data), 2016 IEEE International Conference on (2016), IEEE, pp. 1911–1920.
