在基於地理位置社群網路上利用移動行為之地點推薦

Location Promotion based on Human Mobility on Location-based Social Networks

阮清海(Hai, Nguyen Thanh)

指導教授 ： 彭文志

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00033

摘要

Maximizing the spread of influence was recently studied in several models of social networks. For location-based social networks, it also plays an important role, so a further research about this fields is necessary. In this study, based on users’ movement histories and their friendships, we first design the Predicting Mobility in the Near Future (PMNF) model to capture human mobility. Human mobility is inferred from the model by taking into account the following three features: (1) the regular movement of users, (2) the movement of friends of users, (3) hot regions, the most attractive places for all users. Second, from the result of predicting movements of users at each location, we determine influence of each user on friends with the condition that friends are predicted to come to the location. Third, the Influence Maximization (IM) algorithms are proposed to find a set of k influential users who can make the maximum influence on their friends according to either the number of influenced users (IM num) or the total of probability of moving the considered location of influenced users (IM score). The model and algorithms are evaluated on three large datasets collected by from 40,000 to over 60,000 users for each dataset over a period of two years in the real world at over 500,000 checked-in points as well as 400,000 to nearly 2,000,000 friendships also considered. The points are clustered into locations by density-based clustering algorithms such as OPTICS and GRID. As a result, our algorithms give an order of magnitude better performance than baseline approaches like choosing influential users based on the number of check-ins of users and selecting influential users by the number of friends of users. From the result of experiments, we are able to apply to some areas like advertisement to get the most efficient with the minimum costs. We show that our framework reliably determines the most influential users with high accuracy.

關鍵字

地點促銷 ； 影響擴散

並列摘要

Maximizing the spread of influence was recently studied in several models of social networks. For location-based social networks, it also plays an important role, so a further research about this fields is necessary. In this study, based on users’ movement histories and their friendships, we first design the Predicting Mobility in the Near Future (PMNF) model to capture human mobility. Human mobility is inferred from the model by taking into account the following three features: (1) the regular movement of users, (2) the movement of friends of users, (3) hot regions, the most attractive places for all users. Second, from the result of predicting movements of users at each location, we determine influence of each user on friends with the condition that friends are predicted to come to the location. Third, the Influence Maximization (IM) algorithms are proposed to find a set of k influential users who can make the maximum influence on their friends according to either the number of influenced users (IM num) or the total of probability of moving the considered location of influenced users (IM score). The model and algorithms are evaluated on three large datasets collected by from 40,000 to over 60,000 users for each dataset over a period of two years in the real world at over 500,000 checked-in points as well as 400,000 to nearly 2,000,000 friendships also considered. The points are clustered into locations by density-based clustering algorithms such as OPTICS and GRID. As a result, our algorithms give an order of magnitude better performance than baseline approaches like choosing influential users based on the number of check-ins of users and selecting influential users by the number of friends of users. From the result of experiments, we are able to apply to some areas like advertisement to get the most efficient with the minimum costs. We show that our framework reliably determines the most influential users with high accuracy.

並列關鍵字

mobility prediction ； influence spread ； location-based social networks ； influential users ； influenced users ； maximum influence

參考文獻

[4] George Liu, Gerald Maguire, Jr., "A class of mobile motion prediction algorithms for wireless mobile computing and communication," Mobile Networks and Applications - Special issue: routing in mobile communications networks, vol. 1, no. 2, pp. 113-121, 1996.

[7] Long Vu, Quang Do, Klara Nahrstedt, "Jyotish: Constructive approach for context predictions of people movement from joint Wifi/Bluetooth trace," Pervasive and Mobile Computing, vol. 7, no. 6, pp. 690-704, 2011.

[10] Yu Zheng, Lizhu Zhang, Xing Xie, Wei-Ying Ma, "Mining interesting locations and travel sequences from GPS trajectories," in WWW '09 Proceedings of the 18th international conference on World wide web, New York, NY, USA, 2009.

[12] Hao-Hsiang Wu, Mi-Yen Yeh, "Influential Nodes in a One-Wave Diffusion Model for Location-Based Social Networks," in 17th Pacific-Asia Conference, PAKDD 2013, Gold Coast, Australia, 2013.

[16] Ester M., Krie.gel H.-P., Sander J., Xu X., "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise," in Proc. 2nd Int. Conf. on Knowledge , Portland, 1996.