2016
Journal article
Open Access
Unveiling mobility complexity through complex network analysis
Guidotti R., Monreale A., Rinzivillo S., Pedreschi D., Giannotti F.
Mobility Complexity Mobility Data Analytics Computer Science Applications Media Technology Information Systems Community Discovery Human-Computer Interaction Communication
The availability of massive digital traces of individuals is offering a series of novel insights on the understanding of patterns characterizing human mobility. Many studies try to semantically enrich mobility data with annotations about human activities. However, these approaches either focus on places with high frequencies (e.g., home and work), or relay on background knowledge (e.g., public available points of interest). In this paper, we depart from the concept of frequency and we focus on a high level representation of mobility using network analytics. The visits of each driver to each systematic destination are modeled as links in a bipartite network where a set of nodes represents drivers and the other set represents places. We extract such network from two real datasets of human mobility based, respectively, on GPS and GSM data. We introduce the concept of mobility complexity of drivers and places as a ranking analysis over the nodes of these networks. In addition, by means of community discovery analysis, we differentiate subgroups of drivers and places according both to their homogeneity and to their mobility complexity.
Source: Social Network Analysis and Mining 6 (2016). doi:10.1007/s13278-016-0369-2
Publisher: Springer, Vienna
Agrawal R, Imielin´ski T, Swami A (1993) Mining association rules between sets of items in large databases. ACM SIGMOD Rec 22:207-216
Ankerst M, Breunig MM, Kriegel HP, Sander J (1999) Optics: ordering points to identify the clustering structure. ACM Sigmod Rec 28:49-60
Ashbrook D, Starner T (2003) Using GPS to learn significant locations and predict movement across multiple users. Pers Ubiquit Comput 7(5):275-286
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):10,008
Brilhante IR, Berlingerio M, Trasarti R, Renso C, de Macedo JAF, Casanova MA (2012) Cometogether: discovering communities of places in mobility data. In: IEEE 13th international conference on mobile data management (MDM), pp 268-273
Caldarelli G, Cristelli M, Gabrielli A, Pietronero L, Scala A, Tacchella A (2011) Ranking and clustering countries and their products: a network analysis. arXiv preprint arXiv:1108.2590
Caldarelli G, Cristelli M, Gabrielli A, Pietronero L, Scala A, Tacchella A (2012) A network analysis of countries' export flows: firm grounds for the building blocks of the economy. PLoS ONE 7(10):e47278. doi:10.1371/journal.pone.0047278
Cao L, Luo J, Gallagher A, Jin X, Han J, Huang TS (2010) A worldwide tourism recommendation system based on geotaggedweb photos. In: IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), pp 2274-2277
Coscia M, Rossetti G, Giannotti F, Pedreschi D (2012) Demon: a local-first discovery method for overlapping communities. In: ACM 18th SIGKDD international conference on Knowledge discovery and data mining, pp 615-623
Eubank S, Guclu H, Kumar VA, Marathe MV, Srinivasan A, Toroczkai Z, Wang N (2004) Modelling disease outbreaks in realistic urban social networks. Nature 429(6988):180-184
Furletti B, Cintia P, Renso C, Spinsanti L (2013) Inferring human activities from gps tracks. In: ACM 2nd SIGKDD International Workshop on Urban Computing, p 5
Galton F (1886) Regression towards mediocrity in hereditary stature. J Anthropol Inst Great Br Irel 15:246-263
Giannotti F, Nanni M, Pedreschi D, Pinelli F, Renso C, Rinzivillo S, Trasarti R (2011) Unveiling the complexity of human mobility by querying and mining massive trajectory data. Int J Very Large Data Bases 20(5):695-719
Guidotti R, Monreale A, Rinzivillo S, Pedreschi D, Giannotti F (2014) Retrieving points of interest from human systematic movements. In: Canal C, Idani A (eds) Software engineering and formal methods. Lecture Notes in Computer Science, vol 8938. Springer, pp 294-308
Guidotti R, Trasarti R, Nanni M (2015) TOSCA: two-steps clustering algorithm for personal locations detection. In: ACM 23nd SIGSPATIAL international conference on advances in geographic information systems
Hidalgo CA, Hausmann R (2009) The building blocks of economic complexity. Proc Natl Acad Sci 106(26):10570-10575
Hidalgo CA, Hausmann R (2010) Inferring macroeconomic complexity from country-product network data. In: 2010 AAAI Spring Symposium Series
Hossmann T, Spyropoulos T, Legendre F (2011) A complex network analysis of human mobility. In: IEEE conference on Computer communications workshops (INFOCOM WKSHPS), pp 876-881
Jiang S, Ferreira J, Gonza´lez MC (2012) Clustering daily patterns of human activities in the city. Data Min Knowl Disc 25(3):478-510
Kaluza P, Ko¨lzsch A, Gastner MT, Blasius B (2010) The complex network of global cargo ship movements. J R Soc Interface 7(48):1093-1103
Kleinberg JM , Kumar R, Raghavan P, Rajagopalan S, Tomkins AS (1999) The web as a graph: measurements, models, and methods. In: Asano T, Imai H, Lee DT, Nakano S-i, Tokuyama T (eds) Computing and combinatorics. Lecture Notes in Computer Science, vol 1627. Springer Berlin, Heidelberg, pp 1-17
Lafferty J, McCallum A, Pereira FC (2001) Conditional random fields: probabilistic models for segmenting and labeling sequence data. In: 8th International conference on machine learning, ICML 2001, Morgan Kaufmann Publishers Inc. pp 282-289
Lanczos C (1950) An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Governm, Press Office, Los Angeles
McPherson M, Smith-Lovin L, Cook JM (2001) Birds of a feather: homophily in social networks. Ann Rev Sociol 27:415-444. doi:10.1146/annurev.soc.27.1.415
Monreale A, Pinelli F, Trasarti R, Giannotti F (2009) Wherenext: a location predictor on trajectory pattern mining. In: ACM 15th SIGKDD international conference on Knowledge discovery and data mining, pp 637-646
Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web. Technical Report, Stanford InfoLab. http://ilpubs.stanford.edu:8090/422/1/1999- 66.pdf
Pang-Ning T, Steinbach M, Kumar V, et al (2006) Introduction to data mining. In: Library of Congress, p 74
Pappalardo L, Rinzivillo S, Qu Z, Pedreschi D, Giannotti F (2013) Understanding the patterns of car travel. Eur Phys J Spec Top 215(1):61-73
Pappalardo L, Simini F, Rinzivillo S, Pedreschi D, Giannotti F, Baraba´si A-L (2015) Returners and explorers dichotomy in human mobility. Nat Commun 6:8166. doi:10.1038/ ncomms9166
Pennacchioli D, Coscia M, Rinzivillo S, Pedreschi D, Giannotti F (2013) Explaining the product range effect in purchase data. In: IEEE international conference on big data, pp 648-656
Rinzivillo S, Gabrielli L, Nanni M, Pappalardo L, Pedreschi D, Giannotti F (2014) The purpose of motion: learning activities from individual mobility networks. In: IEEE international conference on data science and advanced analytics (DSAA), pp 312-318
Rosvall M, Bergstrom CT (2011) Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PloS One 6(4):e18,209
Trasarti R, Pinelli F, Nanni M, Giannotti F (2011) Mining mobility user profiles for car pooling. In: ACM 17th SIGKDD international conference on Knowledge discovery and data mining, pp 1190-1198
Zheng VW, Zheng Y, Xie X, Yang Q (2010) Collaborative location and activity recommendations with gps history data. In: ACM 19th international conference on world wide web, pp 1029-1038
Zheng Y, Xie X (2010) Learning location correlation from gps trajectories. In: IEEE 11th international conference on mobile data management (MDM), pp 27-32
Zhou C, Frankowski D, Ludford P, Shekhar S, Terveen L (2004) Discovering personal gazetteers: an interactive clustering approach. In: ACM 23rd annual international workshop on geographic information systems, pp 266-273
Ankerst M, Breunig MM, Kriegel HP, Sander J (1999) Optics: ordering points to identify the clustering structure. ACM Sigmod Rec 28:49-60
Ashbrook D, Starner T (2003) Using GPS to learn significant locations and predict movement across multiple users. Pers Ubiquit Comput 7(5):275-286
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):10,008
Brilhante IR, Berlingerio M, Trasarti R, Renso C, de Macedo JAF, Casanova MA (2012) Cometogether: discovering communities of places in mobility data. In: IEEE 13th international conference on mobile data management (MDM), pp 268-273
Caldarelli G, Cristelli M, Gabrielli A, Pietronero L, Scala A, Tacchella A (2011) Ranking and clustering countries and their products: a network analysis. arXiv preprint arXiv:1108.2590
Caldarelli G, Cristelli M, Gabrielli A, Pietronero L, Scala A, Tacchella A (2012) A network analysis of countries' export flows: firm grounds for the building blocks of the economy. PLoS ONE 7(10):e47278. doi:10.1371/journal.pone.0047278
Cao L, Luo J, Gallagher A, Jin X, Han J, Huang TS (2010) A worldwide tourism recommendation system based on geotaggedweb photos. In: IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), pp 2274-2277
Coscia M, Rossetti G, Giannotti F, Pedreschi D (2012) Demon: a local-first discovery method for overlapping communities. In: ACM 18th SIGKDD international conference on Knowledge discovery and data mining, pp 615-623
Eubank S, Guclu H, Kumar VA, Marathe MV, Srinivasan A, Toroczkai Z, Wang N (2004) Modelling disease outbreaks in realistic urban social networks. Nature 429(6988):180-184
Furletti B, Cintia P, Renso C, Spinsanti L (2013) Inferring human activities from gps tracks. In: ACM 2nd SIGKDD International Workshop on Urban Computing, p 5
Galton F (1886) Regression towards mediocrity in hereditary stature. J Anthropol Inst Great Br Irel 15:246-263
Giannotti F, Nanni M, Pedreschi D, Pinelli F, Renso C, Rinzivillo S, Trasarti R (2011) Unveiling the complexity of human mobility by querying and mining massive trajectory data. Int J Very Large Data Bases 20(5):695-719
Guidotti R, Monreale A, Rinzivillo S, Pedreschi D, Giannotti F (2014) Retrieving points of interest from human systematic movements. In: Canal C, Idani A (eds) Software engineering and formal methods. Lecture Notes in Computer Science, vol 8938. Springer, pp 294-308
Guidotti R, Trasarti R, Nanni M (2015) TOSCA: two-steps clustering algorithm for personal locations detection. In: ACM 23nd SIGSPATIAL international conference on advances in geographic information systems
Hidalgo CA, Hausmann R (2009) The building blocks of economic complexity. Proc Natl Acad Sci 106(26):10570-10575
Hidalgo CA, Hausmann R (2010) Inferring macroeconomic complexity from country-product network data. In: 2010 AAAI Spring Symposium Series
Hossmann T, Spyropoulos T, Legendre F (2011) A complex network analysis of human mobility. In: IEEE conference on Computer communications workshops (INFOCOM WKSHPS), pp 876-881
Jiang S, Ferreira J, Gonza´lez MC (2012) Clustering daily patterns of human activities in the city. Data Min Knowl Disc 25(3):478-510
Kaluza P, Ko¨lzsch A, Gastner MT, Blasius B (2010) The complex network of global cargo ship movements. J R Soc Interface 7(48):1093-1103
Kleinberg JM , Kumar R, Raghavan P, Rajagopalan S, Tomkins AS (1999) The web as a graph: measurements, models, and methods. In: Asano T, Imai H, Lee DT, Nakano S-i, Tokuyama T (eds) Computing and combinatorics. Lecture Notes in Computer Science, vol 1627. Springer Berlin, Heidelberg, pp 1-17
Lafferty J, McCallum A, Pereira FC (2001) Conditional random fields: probabilistic models for segmenting and labeling sequence data. In: 8th International conference on machine learning, ICML 2001, Morgan Kaufmann Publishers Inc. pp 282-289
Lanczos C (1950) An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Governm, Press Office, Los Angeles
McPherson M, Smith-Lovin L, Cook JM (2001) Birds of a feather: homophily in social networks. Ann Rev Sociol 27:415-444. doi:10.1146/annurev.soc.27.1.415
Monreale A, Pinelli F, Trasarti R, Giannotti F (2009) Wherenext: a location predictor on trajectory pattern mining. In: ACM 15th SIGKDD international conference on Knowledge discovery and data mining, pp 637-646
Page L, Brin S, Motwani R, Winograd T (1999) The PageRank citation ranking: bringing order to the web. Technical Report, Stanford InfoLab. http://ilpubs.stanford.edu:8090/422/1/1999- 66.pdf
Pang-Ning T, Steinbach M, Kumar V, et al (2006) Introduction to data mining. In: Library of Congress, p 74
Pappalardo L, Rinzivillo S, Qu Z, Pedreschi D, Giannotti F (2013) Understanding the patterns of car travel. Eur Phys J Spec Top 215(1):61-73
Pappalardo L, Simini F, Rinzivillo S, Pedreschi D, Giannotti F, Baraba´si A-L (2015) Returners and explorers dichotomy in human mobility. Nat Commun 6:8166. doi:10.1038/ ncomms9166
Pennacchioli D, Coscia M, Rinzivillo S, Pedreschi D, Giannotti F (2013) Explaining the product range effect in purchase data. In: IEEE international conference on big data, pp 648-656
Rinzivillo S, Gabrielli L, Nanni M, Pappalardo L, Pedreschi D, Giannotti F (2014) The purpose of motion: learning activities from individual mobility networks. In: IEEE international conference on data science and advanced analytics (DSAA), pp 312-318
Rosvall M, Bergstrom CT (2011) Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PloS One 6(4):e18,209
Trasarti R, Pinelli F, Nanni M, Giannotti F (2011) Mining mobility user profiles for car pooling. In: ACM 17th SIGKDD international conference on Knowledge discovery and data mining, pp 1190-1198
Zheng VW, Zheng Y, Xie X, Yang Q (2010) Collaborative location and activity recommendations with gps history data. In: ACM 19th international conference on world wide web, pp 1029-1038
Zheng Y, Xie X (2010) Learning location correlation from gps trajectories. In: IEEE 11th international conference on mobile data management (MDM), pp 27-32
Zhou C, Frankowski D, Ludford P, Shekhar S, Terveen L (2004) Discovering personal gazetteers: an interactive clustering approach. In: ACM 23rd annual international workshop on geographic information systems, pp 266-273
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:366785,
title = {Unveiling mobility complexity through complex network analysis},
author = {Guidotti R. and Monreale A. and Rinzivillo S. and Pedreschi D. and Giannotti F.},
publisher = {Springer, Vienna},
doi = {10.1007/s13278-016-0369-2},
journal = {Social Network Analysis and Mining},
volume = {6},
year = {2016}
}
0000-0003-3099-3835CNR ExploRA
ISTI Repository
DOIAlso available from
ISTI Repository
DOIAlso available from
