|
|
|
Co-occurrence prediction in a large location-based social network |
Rong-Hua LI1( ), Jianquan LIU2,3, Jeffrey Xu YU1, Hanxiong CHEN2, Hiroyuki KITAGAWA2 |
| 1. Department of System Engineering and EngineeringManagement, The Chinese University of Hong Kong, Hong Kong, China; 2. Faculty of Engineering, Information and systems, University of Tsukuba, Ibaraki 305-8577, Japan; 3. Cloud System Research Laboratories, NEC Corporation, Tokyo 108-8001, Japan |
|
|
|
|
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
|
|
Corresponding Author(s):
LI Rong-Hua,Email:rhli@se.cuhk.edu.hk
|
|
Issue Date: 01 April 2013
|
|
| 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
doi: 10.1073/pnas.1006155107
|
| 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
doi: 10.1007/s10588-005-3939-9
|
| 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
doi: 10.1126/science.167.3924.1461
|
| 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
doi: 10.1109/MNET.2010.5578914
|
| 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
doi: 10.1002/asi.20591
|
| 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
doi: 10.1145/1553374.1553447
|
| 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
doi: 10.1145/1835804.1835855
|
| 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
doi: 10.1145/1835804.1835837
|
| 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
doi: 10.1145/1864349.1864380
|
| 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
doi: 10.1109/TKDE.2008.97
|
| 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
doi: 10.1145/1835804.1835942
|
| 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
doi: 10.1109/JSTSP.2010.2049513
|
| 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
doi: 10.1145/1978542.1978566
|
| 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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
