Human Mobility Analysis in Location-based Social Networks

Abstract

The twenty-first century is witnessing a meteoric rise in user generated content. Popular social networks such as Facebook, Twitter, LinkedIn, etc. which are nowadays being commonly used as communication and information sharing platforms are the major sources of user generated content. Advancement of mobile technology has further fuelled the growth of user generated online content. The powerful handheld devices allow people to publicly share content on the online social networks ubiquitously. Thus, the users of these online social networks have shifted from desktop browsing to mobile-based applications. This led to the development of a new category of social networks called the location-based social network (LBSN). Foursquare, Gowalla, Badoo, CitySource, Glympse, Plazes, etc. are few examples of popular social networks of this category. An LBSN allows its users to find local point-of-interests (POIs), leave comments in the form of reviews and ratings on specific places, communicate with friends, find friends or people who are residing in proximity to a location, view discounts given by nearby shops, etc., just by sharing their current location. The human mobility data available in an LBSN can be exploited to develop different real-world services and applications such as, various types of recommendations to the end users, analysing road traffic situation, weather forecasting, etc. Location based social networks provide a facility called ‘check-in’, that enables people to share location information as well as real life activities. However, it has been found that people do not intend to share the privately visited locations and activities in an LBSN. Extrapolating the hidden or unchecked locations from historical data has a wide range of benefits to society. It can help the investigating agencies in identifying possible places visited by a suspect, a marketing company in selecting potential customers for targeted marketing, etc. In this thesis, we propose an associative location prediction model (ALPM) that explores a combination of data mining techniques to infer the privately visited unchecked locations from a published user trajectory. Association rule mining is used to extract how frequently the consecutive check-in pairs occur. We model the published trajectories as a Markov model, with sequence of observed and unobserved states or locations to identify the hidden locations of a user. Thus, the proposed ALPM utilises a unified view of the interplay between associated check-ins, users with similar trajectories and the geographically proximal locations.
Finding similar users based on their location histories help us to understand a user’sbehaviour over time across various social-activities. A stay point is a location where a user stays for a period of time. It plays an important role in identifying neighbours of an active user. In this thesis, a stay point extraction algorithm (SPE) is proposed. We introduce a term called ‘significance’ to overcome the drawbacks of the existing stay point extraction algorithms. A seminal sequential pattern mining algorithm is adopted on the extracted stay points to find the user mobility patterns. Finally, three similarity metrics have been proposed for computing the nearest neighbours of an active user based on their mobility patterns.In addition to this, a ranking metric is introduced to evaluate the goodness of the nearestneighbours in the predicted neighbour list.
Recommendation is an important service in a location-based social network. The taskof recommending point-of-interests (POIs) to a target user is an essential and most popular service. A POI recommender system often fails to learn the user preferences for a new user who has no historical data (widely known as the user cold-start problem). This thesis focuses on developing a POI recommender system for handling various user cold-start scenarios such as, ‘new user’ and ‘new city’. In this regard, a feature and region based POI recommender system (FRRS) has been devised that can effectively provide recommendations to an active user in cold-start scenarios. The proposed FRRS first learns the user preferences and features of POIs from various online content such as ratings and reviews by exploiting the matrix factorization technique. Subsequently, it combines the learnt user preferences, the interests of influential users and the proximity of POIs from the active location for recommending a list of top-K POIs. However, FRRS fails to recommend a newly evolved POI which is relevant to a user. Handling the newly evolved POIs in a city is an important criteria for an effective POI recommender system.
The newly evolved businesses or POIs have no historical user experience data. Thus, a recommender system fails to gather enough knowledge about the new businesses resulting in ignoring them during recommendations (POI cold-start problem). Users never get recommendation of new businesses in a city even though they are relevant to them. Also, from a business owner’s perspective such a recommendation strategy does not help reachability of the business among users. Therefore, a recommendation approach is proposed that can identify the cold-start POIs in a city and also gather relevant information on them by crowdsourcing multiple online social networks. An aspect-based feature extraction algorithm (APIF) is proposed that exploits the sentiments expressed by the users through the online reviews to learn the inherent features at various POIs including the new POIs. To extract the dominating features of each category of POIs, a fuzzy clustering approach is adopted. Finally, the proposed approach recommends top-K relevant POIs to a target user.