Abstract
Models of urban mobility patterns are key inputs to urban analytics, e.g., planning the transportation infrastructure. Typically, only limited data about mobility is available, due to privacy and data collection challenges. Here, we study the problem of reconstructing mobility traces for all individuals from flow measurements on transportation network links. We formalize this as the constrained label sequence problem (denoted by CLS). CLS is the problem of constructing labeled sequences with constraints that correspond to flows. The proposed formulation is quite general and allows us to consider bounds on the total flow through a set of links, instead of an individual link.
We show that CLS is computationally hard to solve exactly, and design an algorithm with rigorous approximation guarantees. We also study the complexity of counting and sampling from the set of mobility traces consistent with such measurements. Finally, we demonstrate our results using transportation flows across zones around Washington DC and data from the American Community Survey Commuting Flows.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Barbosa, H., Barthelemy, M., Ghoshal, G., James, C.R., Lenormand, M., Louail, T., Menezes, R., Ramasco, J.J., Simini, F., Tomasini, M.: Human mobility: models and applications. Phys. Rep. 734, 1–74 (2018)
Barrett, C.L., Beckman, R.J., Khan, M., Anil Kumar, V.S., Marathe, M.V., Stretz, P.E., Dutta, T., Lewis, B.: Generation and analysis of large synthetic social contact networks. In: Winter Simulation Conference, pp. 1003–1014. Winter Simulation Conference (2009)
USÂ Census Bureau: American Community survey: Commuting flows. https://www.census.gov/topics/employment/commuting/guidance/flows.html. Accessed 11 Oct 2019
Eubank, S., Guclu, H., Anil Kumar, V.S., Marathe, M., Srinivasan, A., Toroczkai, Z., Wang, N.: Modelling disease outbreaks in realistic urban social networks. Nature 429, 180–184 (2004)
Gonzalez, M.C., Hidalgo, C., Barabasi, A.-L.: Understanding individual human mobility patterns. Nature 453, 779–82 (2008)
Isaacman, S., Becker, R., Cáceres, R., Martonosi, M., Rowland, J., Varshavsky, A., Willinger, W.: Human mobility modeling at metropolitan scales. In: Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services, MobiSys 2012, pp. 239–252. ACM, New York (2012)
Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V.: Global wire routing in two-dimensional arrays. Algorithmica 2(1–4), 113–129 (1987)
Schneider, C.M., Belik, V., Couronné, T., Smoreda, Z., González, M.C.: Unravelling daily human mobility motifs. J. R. Soc. Interface 10(84), 20130246 (2013)
Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Heidelberg (2003)
Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82(1), 93–133 (1989)
Toch, E., Lerner, B., Ben-Zion, E., Ben-Gal, I.: Analyzing large-scale human mobility data: a survey of machine learning methods and applications. Knowl. Inf. Syst. 58(3), 501–523 (2019)
Yoon, J., Noble, B.D., Liu, M., Kim, M.: Building realistic mobility models from coarse-grained traces. In: Proceedings of the 4th International Conference on Mobile Systems, Applications and Services, MobiSys 2006, pp. 177–190. ACM, New York (2006)
Yuan, N.J., Wang, Y., Zhang, F., Xie, X., Sun, G.: Reconstructing individual mobility from smart card transactions: a space alignment approach. In: 2013 IEEE 13th International Conference on Data Mining, pp. 877–886. IEEE (2013)
Acknowledgments
This work has been partially supported by the following grants: NSF CRISP 2.0 Grant 1832587, DTRA CNIMS (Contract HDTRA1-11-D-0016-0001), NSF DIBBS Grant ACI-1443054, NSF EAGER Grant CMMI-1745207, and NSF BIG DATA Grant IIS-1633028.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Eubank, S., Marathe, M., Mortveit, H., Vullikanti, A. (2020). Modeling Urban Mobility Networks Using Constrained Labeled Sequences. In: Cherifi, H., Gaito, S., Mendes, J., Moro, E., Rocha, L. (eds) Complex Networks and Their Applications VIII. COMPLEX NETWORKS 2019. Studies in Computational Intelligence, vol 882. Springer, Cham. https://doi.org/10.1007/978-3-030-36683-4_76
Download citation
DOI: https://doi.org/10.1007/978-3-030-36683-4_76
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36682-7
Online ISBN: 978-3-030-36683-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)