Co-occurrence prediction in a large location-based social network

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 cooccurrences and social ties, and the results show that the cooccurrences 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.

Keywords

location-based social networks / Gowalla / cooccurrence

References

[1] Hey T, Tansley S, Tolle K M. The fourth paradigm: data-intensive scientific discovery. Microsoft Research, 2009

[2] 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

[3] 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

[4] 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

[5] Milgram S. The experience of living in cities. Science, 1970, 167(3924): 1461-1468

[6] Li Q, Zheng Y, Xie X, Chen Y, Liu W, Ma W Y. 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

[7] Christopher D, Manning P R, Schütze H. Introduction to Information Retrieval. Cambridge University Press, 2008

[8] 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

[9] 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

[10] Li N, Chen G. Sharing location in online social networks. IEEE Network, 2010, 24(5): 20-25

[11] 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

[12] 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

[13] 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

[14] 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

[15] 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

[16] 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

[17] 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

[18] 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

[19] 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

[20] Backstrom L, Leskovec J. Supervised random walks: predicting and recommending links in social networks. In: Proceedings of the 4th ACMInternational Conference onWeb Search and DataMining. 2011, 635-644

[21] 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

[22] 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

[23] 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

[24] 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

[25] Verhein F. Mining complex spatio-temporal sequence patterns. In: Proceedings of the 2009 SIAM International Conference on Data Mining. 2009, 605-617

[26] 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

[27] 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

[28] 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. 02006, 533-542

[29] 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

[30] 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

[31] Li P, König A C. Theory and applications of b-bit minwise hashing. Communications of the ACM, 2011, 54(8): 101-109

[32] 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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg