Abstract
The main stage for a new generation of cooperative information systems are smart communities such as smart cities and smart nations. In the smart city context in which we position our work, urban planning, development and management authorities and stakeholders need to understand and take into account the mobility patterns of urban dwellers in order to manage the sociological, economic and environmental issues created by the continuing growth of cities and urban population. In this paper, we address the issue of the detection of communities of commuters which is one of the crucial aspects of smart community analysis.
A community of commuters is a group of users of a public transportation network who share similar mobility patterns. Existing techniques for mobility patterns analysis, based on spatio-temporal data clustering, are generally based on geometric similarity metrics such as Euclidean distance, cosine similarity or variations of edit distance. They fail to capture the intuition of mobility patterns, based on recurring visitation sequences, which are more complex than simple trajectories with start and end points.
In this work, we look at visitations as observations for generative models and we explain the mobility patterns in terms of mixtures of communities defined as latent topics which are seen as independent distributions over locations and time. We devise generative models that match and extend Latent Dirichlet Allocation (LDA) model to capture the mobility patterns. We show that our approach, using generative models, is more efficient and effective in detecting mobility patterns than traditional community detection techniques.
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
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
- 4.
Shape parameter is set to 6 and scale parameter is set to 1.2.
References
Gao, H., Liu, H.: Mining human mobility in location-based social networks. Synth. Lect. Data Min. Knowl. Disc. 7(2), 1–115 (2015)
Girvan, M., Newman, M.E.: Community structure in social and biological networks. In: Proceedings of the National Academy of Sciences, pp. 7821–7826 (2002)
Clauset, A., Newman, M.E., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004)
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 10, P10008 (2008)
Fortunato, S.: Community detection in graphs. Physics Reports, pp. 75–174 (2010)
Agrawal, R., Faloutsos, C., Swami, A.: Efficient similarity search in sequence databases. In: Lomet, D.B. (ed.) FODO 1993. LNCS, vol. 730, pp. 69–84. Springer, Heidelberg (1993). doi:10.1007/3-540-57301-1_5
Vlachos, M., Kollios, G., Gunopulos, D.: Discovering similar multidimensional trajectories. In: 18th International Conference on Data Engineering, Proceedings, pp. 673–684. IEEE (2002)
Wang, H., Su, H., Zheng, K., Sadiq, S., Zhou, X.: An effectiveness study on trajectory similarity measures. In: Proceedings of the Twenty-Fourth Australasian Database Conference-vol. 137, pp. 13–22. Australian Computer Society, Inc. (2013)
Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 491–502. ACM (2005)
Zheng, Y., Capra, L., Wolfson, O., Yang, H.: Urban computing: concepts, methodologies, and applications. ACM Trans. Intell. Syst. Technol. (TIST) 5(3), 38 (2014)
Lathia, N., Capra, L.: Mining mobility data to minimise travellers’ spending on public transport. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1181–1189. ACM (2011)
Lathia, N., Capra, L.: How smart is your smartcard?: measuring travel behaviours, perceptions, and incentives. In: Proceedings of the 13th International Conference on Ubiquitous Computing, pp. 91–300. ACM (2011)
Lathia, N., Quercia, D., Crowcroft, J.: The Hidden Image of the City: sensing community well-being from urban mobility. In: Kay, J., Lukowicz, P., Tokuda, H., Olivier, P., Krüger, A. (eds.) Pervasive 2012. LNCS, vol. 7319, pp. 91–98. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31205-2_6
Ferris, B., Watkins, K., Borning, A.: Onebusaway: results from providing real-time arrival information for public transit. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1807–1816. ACM (2010)
Xue, M., Wu, H., Chen, W., Ng, W.S., Goh, G.H.: Identifying tourists from public transport commuters. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1779–1788. ACM (2014)
De Montis, A., Caschili, S., Chessa, A.: Commuter networks and community detection: a method for planning sub regional areas. Eur. Phys. J. Special Topics 215(1), 75–91 (2013)
Al-Ghossein, M., Abdessalem, T.: SoMap: Dynamic clustering and ranking of geotagged posts. In: Proceedings of the 25th International Conference Companion on World Wide Web, International World Wide Web Conferences Steering Committee, pp. 151–154 (2016)
Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent dirichlet allocation. J. Mach. Learn. Res. 3, 993–1022 (2003)
Yuan, J., Zheng, Y., Xie, X.: Discovering regions of different functions in a city using human mobility and pois. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 186–194. ACM (2012)
Hu, B., Jamali, M., Ester, M.: Spatio-temporal topic modeling in mobile social media for location recommendation. In: IEEE 13th International Conference on Data Mining (ICDM), pp. 1073–1078. IEEE (2013)
Long, X., Jin, L., Joshi, J.: Exploring trajectory-driven local geographic topics in foursquare. In: Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 927–934. ACM (2012)
Joseph, K., Tan, C.H., Carley, K.M.: Beyond local, categories and friends: clustering foursquare users with latent topics. In: Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 919–926. ACM (2012)
Cho, Y.S., Ver Steeg, G., Galstyan, A.: Socially relevant venue clustering from check-in data. In: 11th Workshop on Mining and Learning with Graphs, MLG-2013 (2013)
Sizov, S.: Geofolk: latent spatial semantics in web 2.0 social media. In: Proceedings of the Third ACM International Conference on Web Search and Data Mining, pp. 281–290. ACM (2010)
Hu, B., Ester, M.: Spatial topic modeling in online social media for location recommendation. In: Proceedings of the 7th ACM conference on Recommender systems, pp. 25–32. ACM (2013)
Yin, H., Cui, B., Huang, Z., Wang, W., Wu, X., Zhou, X.: Joint modeling of users’ interests and mobility patterns for point-of-interest recommendation. In: Proceedings of the 23rd ACM International Conference on Multimedia, pp. 819–822. ACM (2015)
Yin, H., Zhou, X., Shao, Y., Wang, H., Sadiq, S.: Joint modeling of user check-in behaviors for point-of-interest recommendation. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 1631–1640. ACM (2015)
Liu, Y., Ester, M., Hu, B., Cheung, D.W.: Spatio-temporal topic models for check-in data. In: IEEE International Conference on Data Mining (ICDM), pp. 889–894. IEEE (2015)
Griffiths, T.L., Steyvers, M.: Finding scientific topics. In: Proceedings of the National academy of Sciences, (suppl 1), pp. 5228–5235 (2004)
Nguyen, D.Q.: jLDADMM: a Java package for the LDA and DMM topic models (2015). http://jldadmm.sourceforge.net/
Acknowldgement
This research is funded by research grant R-252-000-622-114 by Singapore Ministry of Education Academic Research Fund (project 251RES1607 - Janus: Effective, Efficient and Fair Algorithms for Spatio-temporal Crowdsourcing) and is a collaboration between the National University of Singapore, Télécom ParisTech and Singapore Agency for Science, Technology and Research.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Dandekar, A., Bressan, S., Abdessalem, T., Wu, H., Ng, W.S. (2016). Detecting Communities of Commuters: Graph Based Techniques Versus Generative Models. In: Debruyne, C., et al. On the Move to Meaningful Internet Systems: OTM 2016 Conferences. OTM 2016. Lecture Notes in Computer Science(), vol 10033. Springer, Cham. https://doi.org/10.1007/978-3-319-48472-3_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-48472-3_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48471-6
Online ISBN: 978-3-319-48472-3
eBook Packages: Computer ScienceComputer Science (R0)