Exploring timeliness for accurate recommendation in location-based social networks

Yi Xu; Qing Yang; Dianhui Chu

doi:10.3934/mfc.2018002

Article Contents

2018, Volume 1, Issue 1: 11-48. Doi: 10.3934/mfc.2018002

This issue Previous Article Network(graph) data research in the coordinate system Next Article L(2, 1)-labeling of the Cartesian and strong product of two directed cycles

Exploring timeliness for accurate recommendation in location-based social networks

1.
Gianforte School of Computing, Montana State University, Bozeman, MT 59717, USA
2.
Department of Computer Science and Engineering, University of North Texas, Denton, TX 76207, USA
3.
School of Computer Science and Technology, Harbin Institute of Technology, Weihai, Shandong 264209, China

Received: September 2017

Revised: November 2017

Published: February 2018

Abstract Full Text(HTML) Figure(13) / Table(2) Related Papers Cited by

Abstract

An individual's location history in the real world implies his or her interests and behaviors. This paper analyzes and understands the process of Collaborative Filtering (CF) approach, which mines an individual's preference from his/her geographic location histories and recommends locations based on the similarities between the user and others. We find that a CF-based recommendation process can be summarized as a sequence of multiplications between a transition matrix and visited-location matrix. The transition matrix is usually approximated by the user's interest matrix that reflect the similarity among users, regarding to their interest in visiting different locations. The visited-location matrix provides the history of visited locations of all users, which is currently available to the recommendation system. We find that recommendation results will converge if and only if the transition matrix remains unchanged; otherwise, the recommendations will be valid for only a certain period of time. Based on our analysis, a novel location-based accurate recommendation (LAR) method is proposed, which considers the semantic meaning and category information of locations, as well as the timeliness of recommending results, to make accurate recommendations. We evaluated the precision and recall rates of LAR, using a large-scale real-world data set collected from Brightkite. Evaluation results confirm that LAR offers more accurate recommendations, comparing to the state-of-art approaches.

Keywords:

Mathematics Subject Classification: Primary: 68T20, 68T37; Secondary: 68U01.

Citation:

Full Text(HTML)

Figure 1. Overview a location-based social network

Download: Full-size image PowerPoint slide

Figure 2. Influence of training size to the precision

Download: Full-size image PowerPoint slide

Figure 3. Cosine similarity between the transition and similarity matrix

Download: Full-size image PowerPoint slide

Figure 4. Average number of new visited location changes through each month

Download: Full-size image PowerPoint slide

Figure 5. Cumulative distribution function (CDF) of time interval between timelinesss

Download: Full-size image PowerPoint slide

Figure 6. Precision and recall of CF with or without K-means clustering and SVD

Download: Full-size image PowerPoint slide

Figure 7. Influence of data sparsity and category to the recommendation rate (recall ratio) where number of recommendations $k = 20$

Download: Full-size image PowerPoint slide

Figure 8. Influence of constant and dynamic similarity to the recommendation rate (precision ratio) where $N$ is number of multiplications

Download: Full-size image PowerPoint slide

Figure 9. Recommendation timeliness comparison for constant similarity matrix and dynamic similarity matrix

Download: Full-size image PowerPoint slide

Figure 10. Similarity of the eigenvector of transition matrix and similarity matrix comparisons of our method and the three benchmarks

Download: Full-size image PowerPoint slide

Figure 11. The recommendation rate of our method and the three baseline varying in the recommendation timeliness (month)

Download: Full-size image PowerPoint slide

Figure 12. The empirical CDF of time intervals of our method and the three benchmarks except CF varying in the recommendation period time (month)

Download: Full-size image PowerPoint slide

Figure 13. Precisions and recalls of LAR, CF, LGS and GeoSoCa

Download: Full-size image PowerPoint slide

Table 1. An example of user-item matrix

	Apple	Pear	Grape	Watermelon
Alice	Like	Like	Dislike	Dislike
Bob		Dislike	Like	Like
Chris		Dislike	Like
Tony	Like		Dislike

| Show Table

DownLoad: CSV

Table 2. A summary of precision and recall ratios of the four approaches

Models	Precision	Recall	Avg.Precision	Avg.Recall
CF	0.51	0.69	0.3573	0.6395
LGS	0.59	0.77	0.3682	0.6762
GeoSoCa	0.58	0.76	0.3657	0.6684
LAR	0.62	0.83	0.4582	0.7523

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	T. A. Adomavicius G, Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions, IEEE Trans Knowl Data Eng, (), 734-749.
[2]	N. L. Anastasios Noulas Salvatore Scellato and C. Mascolo, Mining user mobility features for next place prediction in location-based services, IEEE 12th International Conference on Data Mining, (), 1038-1043.
[3]	D. M. H. T. N. S. Arase Y Xie X, A game based approach to assign geographical relevance to web images, Proceedings of the 18th international conference on World wide web, (), 811-820.
[4]	H. T. N. S. Arase Y Xie X, Mining people's trips from large scale geo-tagged photos, Proceedings of the international conference on multimedia, (), 133-142.
[5]	L. J. Backstrom L, Supervised random walks: Predicting and recommending links in social networks, ACM, (), 635-644.
[6]	J. K. Badrul Sarwar George Karypis and J. Riedl, Item-based collaborative filtering recommendation algorithms, WWW.
[7]	M. M. Bao J Zheng Y, Location-based and preference-aware recommendation using sparse geo-social networking data, ACM SIGSPATIAL.
[8]	B. Berjani and T. Strufe, A recommendation system for spots in location-based online social networks, Proceedings of the 4th Workshop on Social Network Systems, (2011), Article No. 4. doi: 10.1145/1989656.1989660.
[9]	T. G. D. Brockmann L, Hufnagel, The scaling laws of human travel, Nature, 439 (2006), 462-465.
[10]	J. L. Z. Cai, M. Yan and Y. Li, Using crowdsourced data in location-based social networks to explore influence maximization, in Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on, IEEE, 2016, 1-9. doi: 10.1109/INFOCOM.2016.7524471.
[11]	J. C. Cao X Cong G, Mining significant semantic locations from gps data, Proc VLDB Endowment, (), 1009-1020.
[12]	M. K. Cowles and B. P. Carlin, Markov chain monte carlo convergence diagnostics: A comparative review, Journal of the American Statistical Association, 91 (1996), 883-904. doi: 10.1080/01621459.1996.10476956.
[13]	M. M. Chow and C. -Y. Bao J, Towards location-based social networking services, ACM SIGSPATIAL international workshop on location based social networks.
[14]	W.-C. P. I.-J. S. Chun-Ta Lu Po-Ruey Lei, A framework of mining semantic regions from trajectories, Springer, (), 193-207.
[15]	V. W. Z. Dingqi Yang Daqing Zhang and Z. Yu, Modeling user activity preference by leveraging user spatial temporal characteristics in lbsns, IEEE Transactions on Systems, Man, and Cybernetics: Systems, (), 129-142.
[16]	D. L. -X. X. Fuzheng Zhang Nicholas Jing Yuan and W. -Y. Ma, Collaborative knowledge base embedding for recommender systems, KDD.
[17]	B. Smith, G. Linden and J. York, Amazon.com recommendations item-to-item collaborative filtering, IEEE Computer Society, 7 (2013), 76-80. doi: 10.1109/MIC.2003.1167344.
[18]	A. B. J. L. Herlocker J, J. A. Konstan and J. Riedl, An algorithmic framework for performing collaborative filtering, SIGIR, (), 230-237.
[19]	L. C. Z. H. Hongzhi Yin Bin Cui and X. Zhou, Dynamic user modeling in social media systems, ACM Transactions on Information Systems (TOIS), 33 (2015), 10pp.
[20]	Y. S. Z. H. Hongzhi Yin Bin Cui and L. Chen, Lcars: A spatial item recommender system, ACM Transactions on Information Systems (TOIS), 32 (2014), 11pp.
[21]	S. H. K. L. S. J. K. Injong Rhee Minsu Shin and S. Chong, On the levy-walk nature of human mobility, IEEE/ACM transactions on networking (TON).
[22]	R. W. Jason Weston Chong Wang and A. Berenzweig, Latent collaborative retrieval, Proceedings of the 29th International Conference on Machine Learning, (), 9-16.
[23]	C.-Y. Chow, J.-D. Zhang and Y. Zheng, Orec: An opinion-based point-of-interest recommendation framework, Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, (2015), 1641-1650. doi: 10.1145/2806416.2806516.
[24]	Y. Zheng and J. Bao, Location-based and preference-aware recommendation using sparse geo-social networking data, SIGSPATIAL '12 Proceedings of the 20th International Conference on Advances in Geographic Information Systems, (2012), 199-208. doi: 10.1145/2424321.2424348.
[25]	Y. Zheng, J. Yuan and X. Xie, Discovering regions of different functions in a city using human mobility and POIs, Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, (2012), 186-194. doi: 10.1145/2339530.2339561.
[26]	T. Mei, J. Sang and C. Xu, Activity sensor: Check-in usage mining for local recommendation, ACM Transactions on Intelligent Systems and Technology (TIST), 6 (2015), Article No. 41. doi: 10.1145/2700468.
[27]	X. G. K. Kodama, Y. Iijima and Y. Ishikawa, Skyline queries based on user locations and preferences for making location-based recommendations, ACM, (), 916.
[28]	X. Li, Q. Yang, X. Lin, S. Wu and M. Wittie, itrust: Interpersonal trust measurements from social interactions, IEEE Network, 30 (2016), 54-58. doi: 10.1109/MNET.2016.7513864.
[29]	Y. Liang, Z. Cai, Q. Han and Y. Li, Location privacy leakage through sensory data, Security and Communication Networks, 2017 (2017), Article ID 7576307, 12 pages. doi: 10.1155/2017/7576307.
[30]	T.-K. H. J. G. S. Liang Xiong Xi Chen and J. G. Carbonell, Temporal collaborative filtering with bayesian probabilistic tensor factorization, Siam International Conference on Data Mining, (), 211-222.
[31]	G. Liu, Q. Chen, Q. Yang, B. Zhu, H. Wang and W. Wang, Opinionwalk: An efficient solution to massive trust assessment in online social networks, in INFOCOM 2017-IEEE Conference on Computer Communications, IEEE, IEEE, 2017, 1-9.
[32]	G. Liu, Q. Yang, H. Wang, X. Lin and M. P. Wittie, Assessment of multi-hop interpersonal trust in social networks by three-valued subjective logic, in INFOCOM, 2014 Proceedings IEEE, IEEE, 2014,1698-1706. doi: 10.1109/INFOCOM.2014.6848107.
[33]	G. Liu, Q. Yang, H. Wang, S. Wu and M. P. Wittie, Uncovering the mystery of trust in an online social network, in Communications and Network Security (CNS), 2015 IEEE Conference on, IEEE, 2015,488-496.
[34]	W. -C. L. Mao Ye Peifeng Yin and D. -L. Lee, Exploiting geographical influence for collaborative point-of-interest recommendation, ACM AIGIR.
[35]	I. H. T. P. S. P. S. Masoud Sattari Murat Manguoglu and Y. Manolopoulos, Geo-activity recommendations by using improved feature combination, Proceedings of the 2012 ACM Conference on Ubiquitous Computing, (), 996-1003.
[36]	A. E. Mohamed Sarwat Justin J. Levandoski and M. F. Mokbel, Lars^: An efficient and scalable location-aware recommender system, Transactions on Knowledge and Data Engineering*, 6 ().
[37]	C. M. A. Noulas S. Scellato and M. Pontil, Exploiting semantic annotations for clustering geographic areas and users in location-based social networks, Fifth International AAAI Conference on Weblogs and Social Media.
[38]	G. C. Quan Yuan and A. Sun, Graph-based point-of-interest recommendation with geographical and temporal influences, Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, (2014), 659-668. doi: 10.1145/2661829.2661983.
[39]	Y. Z. Ran Cheng Jun Pang, Inferring friendship from check-in data of location-based social networks, ASONAM.
[40]	L. Rossi and M. Musolesi, It's the way you check-in: Identifying users in location-based social networks, COSN, (2014), 215-226. doi: 10.1145/2660460.2660485.
[41]	H. Y. M. R. L. Shenglin Zhao Tong Zhao and I. King, Stellar: Spatial-temporal latent ranking for successive point-of-interest recommendation, Thirtieth AAAI Conference on Artificial Intelligence.
[42]	I. K. Shenglin Zhao and M. R. Lyu, Capturing geographical influence in poi recommendations, International Conference on Neural Information Processing, (2013), 530-537. doi: 10.1007/978-3-642-42042-9_66.
[43]	X. Su and T. M. Khoshgoftaar, A survey of collaborative filtering techniques, Advances in Artificial Intelligence, 2009 (2009), Article ID 421425, 19pp. doi: 10.1155/2009/421425.
[44]	Z. Su, Y. Hui and Q. Yang, The next generation vehicular networks: A content-centric framework, IEEE Wireless Communications, 24 (2017), 60-66. doi: 10.1109/MWC.2017.1600195WC.
[45]	Z. Su, Q. Xu, F. Hou, Q. Yang and Q. Qi, Edge caching for layered video contents in mobile social networks, IEEE Transactions on Multimedia, 19 (2017), 2210-2221. doi: 10.1109/TMM.2017.2733338.
[46]	X. Xie, Q. Yang, V. W. Zheng and Y. Zheng, Collaborative location and activity recommendations with gps history data, Proceeding: WWW '10 Proceedings of the 19th International Conference on World Wide Web, (2010), 1029-1038. doi: 10.1145/1772690.1772795.
[47]	Y. Wang, G. Yin, Z. Cai, Y. Dong and H. Dong, A trust-based probabilistic recommendation model for social networks, Journal of Network and Computer Applications, 55 (2015), 59-67. doi: 10.1016/j.jnca.2015.04.007.
[48]	D. S. WR Gilks S Richardson, Markov chain monte carlo in practice, 2-15.
[49]	V. E. Johnson, Studying convergence of markov chain monte carlo algorithms using coupled sample paths, Journal of the American Statistical Association, 91 (1996), 154-166. doi: 10.1080/01621459.1996.10476672.
[50]	Q. L. X. X. Xiangye Xiao Yu Zheng, Finding similar users using category-based location history, GIS.
[51]	Q. Yang, A. Lim, X. Ruan and X. Qin, Location privacy protection in contention based forwarding for vanets, in Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, IEEE, 2010, 1-5. doi: 10.1109/GLOCOM.2010.5684166.
[52]	Q. Yang, A. Lim, X. Ruan, X. Qin and D. Kim, Location-preserved contention-based routing in vehicular ad hoc networks, Security and Communication Networks, 9 (2016), 886-898. doi: 10.1002/sec.1008.
[53]	Q. Yang and H. Wang, Toward trustworthy vehicular social networks, IEEE Communications Magazine, 53 (2015), 42-47.
[54]	Q. Yang, B. Zhu and S. Wu, An architecture of cloud-assisted information dissemination in vehicular networks, IEEE Access, 4 (2016), 2764-2770. doi: 10.1109/ACCESS.2016.2572206.
[55]	P. L. W. -C. Ye M. ; Yin and D. -L. Lee, Exploiting geographical influence for collaborative point-of-interest recommendation, ACM SIGIR conference on Research and development in Information Retrieval, 325-334.
[56]	Z. Zheng, Y. Zhang and M. R. Lyu, Wspred: A time-aware personalized qos prediction framework for web services, Software Reliability Engineering (ISSRE), (2011), 210-219. doi: 10.1109/ISSRE.2011.17.
[57]	D. L. L. X. X. X. E. C. Yingzi Wang Nicholas Jing Yuan and Y. Rui, Regularity and conformity: Location prediction using heterogeneous mobility data, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (), 1275-1284.
[58]	Y. Yu and X. Chen, A survey of point-of-interest recommendation in location-based social networks, Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence.
[59]	X. Xie, Y. Zheng, L. Zhang and W.-Y. Ma, Mining correlation between locations using human location history, Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems, (2009), 472-475. doi: 10.1145/1653771.1653847.
[60]	C. G. M. Z. S. A. Yuan Q. and N. M. Thalmann, Time-aware point-of-interest recommendation, ACM SIGIR.
[61]	C. Zhang J. ; Chow and Y. Li, igeorec: A personalized and efficient geographical location recommendation framework, IEEE Transaction on Service Computing.
[62]	J.-D. Zhang and C.-Y. Chow, Geosoca: Exploiting geographical, social and categorical correlations for point-of-interest recommendations, SIGIR, (2015), 443-452. doi: 10.1145/2766462.2767711.
[63]	J.-D. Zhang and C.-Y. Chow, igslr: Personalized geo-social location recommendation: a kernel density estimation approach, n Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, (2013), 334-343. doi: 10.1145/2525314.2525339.
[64]	W. Zhang and J. Wang, Location and time aware social collaborative retrieval for new successive point-of-interest recommendation, Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, (2015), 1221-1230. doi: 10.1145/2806416.2806564.
[65]	X. Zheng, Z. Cai, J. Li and H. Gao, Location-privacy-aware review publication mechanism for local business service systems, in INFOCOM 2017-IEEE Conference on Computer Communications, IEEE, IEEE, 2017, 1-9. doi: 10.1109/INFOCOM.2017.8056976.