Abstract
Location-based social network (LBSN) is at the forefront of emerging trends in social network services (SNS) since the users in LBSN are allowed to “check-in” the places (locations) when they visit them. The accurate geographical and temporal information of these check-in actions are provided by the end-user GPS-enabled mobile devices, and recorded by the LBSN system. In this paper, we analyze and mine a big LBSN data, Gowalla, collected by us. First, we investigate the relationship between the spatio-temporal co-occurrences and social ties, and the results show that the co-occurrences are strongly correlative with the social ties. Second, we present a study of predicting two users whether or not they will meet (co-occur) at a place in a given future time, by exploring their check-in habits. In particular, we first introduce two new concepts, bag-of-location and bag-of-time-lag, to characterize user’s check-in habits. Based on such bag representations, we define a similarity metric called habits similarity to measure the similarity between two users’ check-in habits. Then we propose a machine learning formula for predicting co-occurrence based on the social ties and habits similarities. Finally, we conduct extensive experiments on our dataset, and the results demonstrate the effectiveness of the proposed method.
Similar content being viewed by others
References
Hey T, Tansley S, Tolle K M. The fourth paradigm: data-intensive scientific discovery. Microsoft Research, 2009
Crandall D J, Backstrom L, Cosley D, Suri S, Huttenlocher D, Kleinberg J. Inferring social ties from geographic coincidences. Proceedings of the National Academy of Sciences, 2010, 107(52): 22436–22441
Lauw H W, Lim E P, Pang H, Tan T T. Social network discovery by mining spatio-temporal events. Computational & Mathematical Organization Theory, 2005, 11(2): 97–118
Lauw H W, Lim E P, Pang H, Tan T T. Stevent: spatio-temporal event model for social network discovery. ACM Transactions on Information Systems (TOIS), 2010, 28(3): 15:1–15:32
Milgram S. The experience of living in cities. Science, 1970, 167(3924): 1461–1468
Li Q, Zheng Y, Xie X, Chen Y, Liu W, Ma WY. Mining user similarity based on location history. In: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2008, 34–44
Christopher D, Manning P R, Schütze H. Introduction to Information Retrieval. Cambridge University Press, 2008
Ye M, Yin P, Lee W C. Location recommendation for location-based social networks. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2010, 458–461
Li N, Chen G. Analysis of a location-based social network. In: Proccedings of the 2009 International Conference on Computational Science and Engineering. 2009, 263–270
Li N, Chen G. Sharing location in online social networks. IEEE Network, 2010, 24(5): 20–25
Scellato S, Mascolo C, Musolesi M, Latora V. Distance matters: geosocial metrics for online social networks. In: Proceedings of the 3rd Conference on Online Social Networks. 2010, 8–17
Scellato S, Noulas A, Lambiotte R, Mascolo C. Socio-spatial properties of online location-based social networks. In: Proceedings of the 5th International AAAI Conference on Weblogs and Social Media. 2011, 1–8
Scellato S, Noulas A, Mascolo C. Exploiting place features in link prediction on location-based social networks. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011, 1046–1054
Cho E, Myers S A, 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, 1082–1090
Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019–1031
Ito T, Shimbo M, Kudo T, Matsumoto Y. Application of kernels to link analysis. In: Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. 2005, 586–592
Kunegis J, Lommatzsch A. Learning spectral graph transformations for link prediction. In: Proceedings of the 26th Annual International Conference on Machine Learning. 2009, 561–568
Li R H, Yu J X, Liu J. Link prediction: the power of maximal entropy random walk. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. 2011, 1147–1156
Leroy V, Cambazoglu B B, Bonchi F. Cold start link prediction. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010, 393–402
Backstrom L, Leskovec J. Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the 4th ACM International Conference on Web Search and DataMining. 2011, 635–644
Lichtenwalter R N, Lussier J T, Chawla N V. New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010, 243–252
Cranshaw J, Toch E, Hong J, Kittur A, Sadeh N. Bridging the gap between physical location and online social networks. In: Proceedings of the 12th ACM International Conference on Ubiquitous Computing. 2010, 119–128
Mamoulis N, Cao H, Kollios G, Hadjieleftheriou M, Tao Y, Cheung D W. Mining, indexing, and querying historical spatiotemporal data. In: Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2004, 236–245
Cao H, Mamoulis N, Cheung D W. Mining frequent spatio-temporal sequential patterns. In: Proccedings of the 5th IEEE International Conference on Data Mining. 2005, 8–16
Verhein F. Mining complex spatio-temporal sequence patterns. In: Proceedings of the 2009 SIAM International Conference on Data Mining. 2009, 605–617
Celik M, Shekhar S, Rogers J P, Shine J A. Mixed-drove spatiotemporal co-occurrence pattern mining. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(10): 1322–1335
Li Z, Ding B, Han J, Kays R, Nye P. Mining periodic behaviors for moving objects. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010, 1099–1108
Mei Q, Liu C, Su H, Zhai C. A probabilistic approach to spatiotemporal theme pattern mining on weblogs. In: Proceedings of the 15th International Conference on World Wide Web. 2006, 533–542
Farrahi K, Gatica-Perez D. Probabilistic mining of socio-geographic routines from mobile phone data. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(4): 746–755
Farrahi K, Gatica-Perez D. Discovering routines from large-scale human locations using probabilistic topic models. ACM Transactions on Intelligent Systems and Technology, 2011, 2(1): 3:1–3:27
Li P, König A C. Theory and applications of b-bit minwise hashing. Communications of the ACM, 2011, 54(8): 101–109
Li P, Shrivastava A, Moore J L, König A C. Hashing algorithms for large-scale learning. In: Proceedings of the 25th Annual Conference on Neural Information Processing Systems. 2011
Author information
Authors and Affiliations
Corresponding author
Additional information
Rong-Hua LI is pursuing his PhD in Department of System Engineering and Engineering Management, The Chinese University of Hong Kong, China. His research interests include social network analysis and mining, complex network theory, uncertain graphs mining, Monte-Carlo algorithms, and machine learning.
Jianquan LIU received the BE from Shantou University, China, ME and PhD from the University of Tsukuba, Japan, in 2005, 2009, and 2012, respectively. He was a development engineer in Tencent Inc. from 2005 to 2006. He is currently a researcher at the Cloud System Research Laboratories of NEC Corporation, working on the topics of large-scale data processing and cloud computing. His research interests include high-dimensional similarity search, social network analysis, web data mining and information retrieval, cloud storage and computing, and multimedia databases. He is a member of ACM and the Database Society of Japan (DBSJ).
Jeffrey Xu YU received the BE, ME, and PhD in Computer Science from the University of Tsukuba, Japan, in 1985, 1987, and 1990, respectively. He held teaching positions in the Institute of Information Sciences and Electronics, University of Tsukuba, Japan, and the Department of Computer Science, The Australian National University. Currently, he is a professor in the Department of Systems Engineering and Engineering Management, the Chinese University of Hong Kong. His current main research interest includes graph database, graph mining, keyword search in relational databases, and social network analysis. He is a senior member of IEEE, a member of IEEE Computer Society, and a member of ACM.
Hanxiong CHEN received the BS from Zhongshan University, Guangdong, China, in 1985, the MS and the PhD in Computer Science, from the University of Tsukuba, Japan, in 1990 and 1993, respectively. He is currently an assistant professor at Faculty of Engineering, Information and Systems, University of Tsukuba. His research interests include data engineering, knowledge discovery, data mining, and information retrieval. He is a member of ACM, IEEE-CS, and IPSJ.
Hiroyuki KITAGAWA received the BS in Physics and the MS and PhD in Computer Science, all from the University of Tokyo, in 1978, 1980, and 1987, respectively. He is currently a full professor at Faculty of Engineering, Information and Systems, University of Tsukuba. His research interests include data integration, data mining, information retrieval, stream processing, data-intensive computing, XML, and scientific databases. He is an editorial board member of IEEE TKDE and WWWJ, a Fellow of IPSJ and IEICE, Vice Chairperson of the Database Society of Japan, and a member of ACM, IEEE Computer Society, and JSSST.
Rights and permissions
About this article
Cite this article
Li, RH., Liu, J., Yu, J.X. et al. Co-occurrence prediction in a large location-based social network. Front. Comput. Sci. 7, 185–194 (2013). https://doi.org/10.1007/s11704-013-3902-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11704-013-3902-8