LoCaTe: Influence Quantification for Location Promotion in Location-based Social Networks

1 Introduction

With GPS 1 becoming pervasive within smartphones, location-based social networks (LBSNs) such as Foursquare and Facebook places have gained popularity. These networks allow users to share their check-in information with their friends enabling LBSN users to be aware of their friend's check-ins. This, combined with other factors, can influence the check-in preferences of users [Cho et al., 2011; Ye et al., 2011]. Quantifying the user-to-user influence -often modelled probabilistically [Goyal et al., 2010; Zhang et al., 2012]- is an essential building block in understanding the effects of information diffusion in LBSNs.

Influence maximization [Bouros et al., 2014; Li et al., 2014; Wu and Yeh, 2013] in social networks addresses the problem of finding a set of users who have a strong influence in the social network; these users are potentially good

1 https://en.wikipedia.org/wiki/Global Positioning System

Srikanta Bedathur

IBM-Research Lab, Delhi, India sbedathur@in.ibm.com

Deepak P.

Queen's University Belfast Northern Ireland, UK deepaksp@acm.org

seed users to run promotion campaigns that target to maximize the reach of the campaign. Research interest in LBSNs has sparked interest in using geo-locations for influence maximization, leading to the location promotion problem [Zhu et al., 2015]. The location promotion problem is of significant importance for launching effective campaigns to help businesses gather more customers. This task instantiates the influence maximization task on a specified target location/venue (e.g., a particular restaurant), with the intent of finding a set of seed users who are well-positioned for the promotion of their business [Zhu et al., 2015]. Once a set of seed users is identified, it can be used to issue targeted special offers.

From the perspective of location promotion, the worth of a user - or the user's "seedness" - is quantified as the number of users she can influence to visit a location, after her visit. The necessary step for the location promotion problem is thus a method to assess the likelihood that other users would visit the location following the candidate seed user's visit. Influence quantification can factor in a variety of information that a LBSN offers: (i) geographic features: user's mobility over different locations, (ii) semantic features: type/category of location (e.g., restaurant, cafe), (iii) social correlation: the relationship between users in the social network, and (iv) temporal correlation: the degree to which a user's movement is correlated with another user's. Previous work on influence quantification for location promotion has mostly focused on modelling geographic features and social correlation [Zhu et al., 2015]. Studies on semantic features such as category have been limited primarily since datasets containing such information have been scarce [Gao et al., 2012; Cho et al., 2011]; such deficiencies have been recently addressed by methods such as approximate spatial joins [Likhyani et al., 2015]. Thus, because of unavailability of category information intrinsically, the use of location semantics have not been explored in previous work. In this work, we join datasets from multiple sources to make location category usage possible.

The temporal correlation of users behavior has been modeled previously in online social networks, but not in LBSN as we do in this paper. The socially induced followship based on temporal correlation has been of interest in LBSN studies in other contexts [Pham and Shahabi, 2016].

In this paper, we address this research gap and make twofold contribution: first, exploitation of the hitherto unexplored information, that of location categories, for influence quantification; second, we develop a novel model LoCaTe that incorporates:

1. Location affinity: The mobility patterns of users that hold cues to whether they frequent the proximity of the target location.
2. Category affinity: The affinity of a user to the category or type of the location.
3. Temporal correlation: The temporal correlation of movements between the user and the candidate seedset, thus modelling time-conditioned social followship.

As is the case of any influence quantification method, our model easily fits into any location promotion setting[Li et al., 2014; Zhu et al., 2015]. We empirically evaluate our approach over both publicly available real-world LBSN data as well as our own long-term crawl of Foursquare check-ins spanning more than one year. Overall, the proposed LoCaTe model can outperform state-of-the-art methods by more than 50% in AUC (Area Under the Curve of ROC[Bradley, 1997]).

2 RelatedWork

While influence maximization has been a well-studied problem (e.g., [Kempe et al., 2003; 2005; Chen et al., 2010; Goyal et al., 2010]), the geo-seeded instantiation motivated by LBSNs has gathered only recent attention [Li et al., 2014; Zhu et al., 2015; Bouros et al., 2014; Zhang et al., 2012; Pham and Shahabi, 2016]. Apart from the location promotion problem where we start with a specific target location, there have been studies on region promotion, where the target is a larger geo-region [Bouros et al., 2014]. Users' geo-location affinities have been modeled by either associating one specific geo-location with each user (usually the most frequently one visited by the user) [Li et al., 2014; Zhang et al., 2012] or a set of geolocations or only the social network structure [Bouros et al., 2014; Zhu et al., 2015]. In a similar way, the user-user pairwise influence propagation probabilities are estimated either using just the (social) network structure [Bouros et al., 2014; Li et al., 2014; Zhang et al., 2012] or taking into consideration the seed location/region [Zhu et al., 2015]. To the best of our knowledge only the recent work in [Pham and Shahabi, 2016], have looked at defining user-user pairwise influence in spatiotemporal context, but for identifying followship. For our empirical evaluation, we compare against the most recent work by Zhu et al. [Zhu et al., 2015], that associates a set of locations for each user and considers the influence between two users to be dependent on the location.

User Mobility Models: We make use of user mobility models in our method drawing inspiration from earlier work on characterizing user behavior in LBSNs. Since LBSN data provides a trail of user's locations, it provides a rich data platform for studying user mobility patterns; such patterns are of interest for tasks such as location prediction and personalized recommendation. In literature, mobility models that mine spatial patterns based on generative models [Gao et al., 2012], Gaussian distributions [Cho et al., 2011] and kernel density estimations [Lichman and Smyth, 2014] have been particularly successful. Accordingly, we use the kernel density mobility model [Lichman and Smyth, 2014] to model and exploit user-location affinities in our method for LBSN location promotion. The baseline technique from [Zhu et al.,

2015], on the other hand, makes use of a distance-based mobility model, DMM, in their influence quantification method.

3 Problem Statement

Now we provide a formal definition of influence quantification problem in an LBSN for location promotion. Table 1 lists a set of notations that will be used. We model a location/venue 2 as having a fixed geographic coordinate as well as a set of categories associated with it. This allows for modeling of locations such as movie multiplexes that would screen movies as well as contain eateries.

Definition 1 (Location Promotion) Given an LBSN G, a target location ℓ, whose category set is Cℓ, the location promotion problem is to select a small set of seed users S, S ⊆ U, who can lure other users to the target location ℓ well. The hyperparameter τ indicates the desired cardinality of S.

Influence quantification, the task of quantifying the likelihood of a user visiting the location given a visit to the same location by another (i.e., seed) user, forms an important building block for location promotion problem as shown in [Zhu et al., 2015]. Given a user-user influence model, the location promotion problem reduces to finding a set of seed users which can collectively influence a large set of users to visit the location in focus.

Definition 2 (Influence quantification.) Influence quantification: Given an LBSN G, a target location ℓ, a seeduser u (usually a user who has previously visited ℓ), the influence quantification problem is to quantify the likelihood P(ℓ, u, v |G), the likelihood that any user v among u's connections is likely to visit ℓ.

As mentioned earlier, influence quantification models typically consider the affinity of the user v to location ℓ independent of the influence from other users, and the influence of the seed user u on v in this decision.

Evaluation: Our evaluation framework follows earlier work in this area (e.g., [Zhu et al., 2015]): from a dataset of LBSN check-ins, we decide on a cut-off timestamp such that there is a sizeable amount of check-ins before and after the cutoff. All data prior to the cut-off timestamp is used as training data to learn the model. The remaining data forms the test set against which the effectiveness of the learned model is measured. Consider a particular instance of the influence quantification problem for location ℓ and a seed-user u; the influence quantification output would be an ordered list of u's connections, ordered in the decreasing (non-increasing) order of estimated likelihood to visit ℓ. This list can be cut-off using a threshold ρ to identify a set of users who are deemed to be highly likely to visit ℓ - this set forms the predicted set, PS(ℓ, u, ρ |G). The ground truth activated set, A(ℓ, u), is the subset of u's connections who have actually visited ℓ after the cut-off timestamp (i.e., from the test set). The match between PS(ℓ, u, ρ | G) and A(ℓ, u) measured at various values of the threshold ρ quantifies the goodness of the influence quantification method employed. Any measure of match between sets can be aggregated over all users (i.e., by iterating u over the set of LBSN users) to get a single goodness value for the combination [ℓ, ρ]. We will use the ROC curve (generated by varying ρ) to compare our method against baselines in our empirical evaluation.

2 We use location and venue interchangeably. Though venue might be more appropriate, location is also used in literature.

4 LoCaTe Influence Quantification

We now outline our influence quantification method, LoCaTe, that estimates Pℓ,u(v|M), a scoring that captures the likelihood that the user v from u's connections would visit the location ℓ using the check-in records in the training part, denoted as M. Figure 1 shows the framework of LoCaTe. LoCaTe combines information from three kinds of features:

where, PL(v, ℓ|M) models the affinity of v to location ℓ, and PC(v,Cℓ|M) models the affinity of v to the categories that are associated with the location ℓ (denoted as Cℓ). These two terms are interpolated using an interpolation parameter α. Further, T(u → v|M) captures the temporal correlation between users u and v, independent of the location. The first two terms quantify users affinity for the location using mobility and categories respectively and are combined using a weighted sum. The third term quantifying location-agnostic user-user socially induced temporal affinity is merged using a product. Thus, the final scoring ensures that users who are strong on both location and temporal aspects score much higher than others.

Pℓ,u(v|M) ranges between [0,1], since we normalize the scores obtained for a list of influenced users v = (v1, ...vm) keeping the seed user u and target location ℓ fixed. Thus

The usage of Location affinity, Category affinity and Temporal correlation lends the name to our method.

4.1 Location Affinity

The mobility of each user is typically restricted to a few key locations, which would typically include the location of stay and work [Cho et al., 2011]. Thus, a user has an inherent preference for some geo-locations. We use kernel density estimates to model mobility patterns and location affinity of users. Kernel density estimates are robust to sharp transitions in spatial densities that human mobility witnesses, especially in contexts involving travels that take users far away from their usual location of residence [Cho et al., 2011; Lichman and Smyth, 2014].

The affinity of v to ℓ based on her own check-in history is modeled as the kernel density estimate (KDE) that quantifies the average weighted similarity between ℓ and each location lj has checked-in using hyper-parameter k,

Kj,k(·, ·) estimates the similarity between locations as inversely related to the Euclidean distance between them:

Here, hj,k is a location-dependent scalar factor that is set to be the Euclidean distance of ℓj to it's k th nearest neighbor, thus ensuring that the similarity computation is sensitive to differential densities of locations in urban and rural areas.

Mixture of Kernel Density models:

To offset for sparsity issues in determining the location affinity using just the user's check-in records, we use corpus smoothing by interpolating the location affinity of a user with those across all users, yielding our final formulation:

where, βv is a user-specific mixing weight, determining the relative influence between the user and global models. We will denote this as PL(., .) when the value of k is clear.

Training:

We have two parameters that need to be estimated. First, the hyper-parameter k is estimated as the value that maximizes the likelihood of check-ins in a chosen validation set, V (which is a held-out part of the check-ins before the cut-off timestamp, but not included in the training). Thus, we set k to the value that maximizes the following:

The distribution of log-likelihood across various values of k are shown in Table 2; accordingly, we chose k = 5 for usage in our method. Second, we choose the user-specific interpolation weights βv as the value that maximizes the likelihood of their check-ins in the training data itself. We do not use the validation set here since there are users who do not have any check-ins in the validation set.

8

9

10

Fsq'16 -2.032 -1.804 -1.704 -1.640 -1.670 -1.687 -1.722 -1.744 -1.817

Fsq'11 -2.711 -2.640 -2.063 -1.726 -0.939 -0.738 -0.677 -0.794 -0.851

Fsq'10 -1.283 -1.251 -1.233 -1.211 -1.225 -1.231 -1.246 -1.260 -1.278

Brightkite -1.915 -1.869 -1.836 -1.789 -1.779 -1.821 -1.850 -1.879 -1.897

Gowalla -1.978 -1.896 -1.847 -1.804 -1.825 -1.854 -1.877 -1.890 -1.931

4.2 Category Affinity

Locations/Venues often record correlated check-in behavior across LBSN users. For example, a restaurant might be better off targeting a user who frequently checks in to food places due to the correlation across various categories of food joints. As an example, consider two users in Figure 2 represented by the word cloud of the categories of their checked-in locations (larger font indicates higher frequency); User A evidently exhibits affinity towards visiting restaurants while user B prefers gym and fitness centers. We use topic modeling to identify such higher-level contexts, and exploit it to model the user-category affinity term, PC(v, Cℓ|M).

Latent Dirichlet allocation [Blei et al., 2003] models semantic matching between text documents by learning topics, each of which is a probability distribution over the set of words. LDA ensures that words that are semantically related would have high probabilities associated with the same topic(s). In our adaptation of LDA for modeling topical contexts across check-in categories, each user v is treated as a document constructed as a bag of categories vC (i.e., each category as a word) of checked-in locations. These documents across the users in the population form a document corpus. We apply LDA on this document corpus, to learn topics which are probability distributions over categories. We then use the learnt topics to estimate the user's affinity to the set of categories associated with the location of interest:

where Topics(M) is the set of topics learned as described, and Z represents a topic from the topic-set learned. P(v|Z) and P(Cℓ|Z) quantify how well the category distribution for Z matches against those of the check-ins of v and the categories of ℓ respectively. High values of PC(v,Cℓ|M) are achieved when the user's category distribution and that of the location under consideration are correlated with the same set of topics.

4.3 Temporal User Correlation

We now turn our attention to the temporal correlation term, T(u → v|G), that quantifies the extent of influence that u has over v. This primarily accounts for the socially induced followship in our Influence Quantification model. The task at hand is to quantify the chance that v will follow u in checking-in to a location, such that (u, v) ∈ E. Towards across connections

(a) across userbase

(b) across connections

Figure 4: Time lag probability distribution plot

modeling this, we first analyze the behavior of general interarrival times of users in the LBSN at a given location, without considering whether they are connected to each other in the LBSN network or not; we call this the time lag distribution across userbase. The analogous time lag distribution across connections considers the distribution of the time duration elapsed between two users who are connected to each other, visiting the location in question. A visual depiction of the time lags that go into either of these distributions appears in Figure 3. We collect these time lag distributions across all locations in the LBSN and analyze their frequency distribution using a histogram. As expected, the general across userbase time lag distribution follows a power law distribution, as illustrated in Figure 4(a). However, the across connections time lag distribution in 4(b) does not quite follow a power law distribution despite exhibiting a monotonic decay with increasing values of time lag. It may also be noted that the across connections data is much sparser than across userbase; this is so since there are a significantly fewer number of occurrences of connected users visiting the same location. Drawing cues from the trends across the two time lag distributions, we choose to model the time lag distribution between users using an exponential distribution, given it's popularity in similar contexts [Pham and Shahabi, 2016].

Modeling using exponential distribution

According to the exponential distribution modelling, the weight associated with any value of time lag, denoted δt, would be quantified as the following:

We set λt to be the mean time lag between check-ins by connected users:

where the 〈u, ·, t, ·〉 implies that we consider all check-ins by u at time t irrespective of the location of the check-in or the set of categories associated with the location. This feeds into our user correlation estimate T(u → v|G) which is modelled as the cumulative weight of v checking in at a location visited by u after a time lag of any t ⩾ t min u,v :

As indicated above, we set t min u,v to be the earliest time that v has checked in after u at the same location, according to training data; this ensuring that T (u → v|G) reflects the extent of correlation between u and v, since T (u → v|G) would have a high value for those user pairs where the latter follows the former (temporally) closely.

5 Experiments

5.1 Experimental Setting

We tested over 5 datasets as shown in table 3, of which FSq'16 is the one that we collected using Twitter and FourSquare APIs, and rest are publicly available datasets [Cho et al., 2011; Gao et al., 2012]. The publicly available datasets do not provide category information, and moreover, the locations are also annonymized, they only expose the latitude, longitude information of the location. A recent work uses approximate spatial joins across checked-in locations and map data (available at Foursquare itself) to infer category information for each check-in and the data is made available by the authors [Likhyani et al., 2015]. Such joins provide a large set of categories for each location as there could be multiple types of locations (e.g., cafe, hospital) at the same geo-location. Although another large collection of Foursquare check-in data with category information is released, it does not have the social graph of users essential for the location promotion problem addressed in this paper [Yang et al., 2016]. To the best of our knowledge, there does not exist any publicly available dataset that contain category information of checked-in locations along with the social graph.

Data Collection: We use Twitter for getting check-ins of users, because user's check-in information in Foursquare can only be accessed from her own social circle, and it is not available publicly. However, Foursquare users can choose to post their check-ins via Twitter when they check in at a place. Hence, we capture check-ins by crawling Foursquare-tagged tweets from the Twitter Public Stream API 3 and REST API 4 . The Foursquare-tagged check-in tweet crawled contains a uniqueURL that points to a Foursquare web page containing the geographical information of this check-in location. We parse this web page to get check-in location along with the timestamp. Further to obtain category of this location, we pass this location to FourSquare API 5 and get access of the location information. Lastly, to accquire the social information of users (i.e. friendship links), we again use Twitter, because Foursquare does not provide public access to user's friends list. Thus, we acquired friendship ties that Foursquare users have among them on Twitter, where they are publicly available. To extract the check-in details of friends we again crawl their tweets in the same manner as above. While the resulting social graph is not identical to the original Foursquare graph, it encompasses the subset of users who are on Twitter and have linked their Twitter and FourSquare accounts. In our experiment, we consider the users who have at least 10 checkins. Some key statistics of the dataset are shown in table 3. FSq'16 is the dataset that we curated, rest are public datasets for which we collected only the category information.

3 https://dev.twitter.com/streaming/public

4 https://dev.twitter.com/rest/public

5 https://developer.foursquare.com/docs/

Test Set: For each dataset, we assign a cut-off timestamp, the data prior to it is used for training and rest of the check-ins for testing. The cut-off timestamp is chosen such that 80% of total checkins are used for training. The target locations are identified as locations where a user's check-in precedes its follower's check-ins and both the check-ins are made on or after the cut-off timestamp. The user who checks-in first is the seed user and it's followers who checks-in after him, are the activated users (by the seed user). Section 2 describes ground truth construction set of activated users and also the evaluation. Table 3 shows the number of test cases (A(ℓ, u)), and cut-off timestamp for each dataset. Note that there is a high variability in the number of categories per location across the datasets, thus enabling the empirical evaluation to cover scenarios across a wide spectrum of semantic information availability.

Parameter Estimation: We also construct a validation set in the same manner as test set is built from the training set for learning the parameters βv and α : mixing the kernel density estimations for spatial density and the topic model for category information, respectively. We use EM algorithm to learn this. Table 4 shows values of βv and α : learned for different datasets. The parameter Z (number of topics) is set to 50.

Implementation: We coded all the models including the baselines (DMM Basic and DMM Social), in Java. For KDE we made use of the source code available at UCI Datalab website (http://www.datalab.uci. edu/resources) and for LDA based topic model we made use of the source code available at http://mallet.cs. umass.edu/topics-devel.php. We ran the code on a 6-core 2.5GHz Intel Xeon CPU with 64GB of RAM. The source code and the datasets used are available publicly 6 .

5.2 Comparative Evaluation

We compare our proposed model LoCaTe with two state of the art users' mobility based influence quantification models, viz., the DMM Basic and the DMM Social models proposed in [Zhu et al., 2015] and two baseline methods: GMM (Gaussian Mixture Model) and a baseline method that plugs in mobility, categorical and temporal features in a simplistic manner (described as follows).

DMM Basic: It models the probability of a user moving from visited locations to the target location. Pareto distribution [Newman, 2005] is used for modeling the distances between the checked-in locations of a user.

pu(ℓ) = ΣlP(u is at l) P(u moves distance d(l, ℓ) from l)

DMM Social: It models user's and user's friends mobility patterns using Pareto distribution as above and the resulting model is the mixture of individual's distance density and social distance density as follows:

6 https://goo.gl/ayzehx

where, p(M) and p(S) are mixing components and αM and αS are the Pareto distribution parameters learned using individual and social data, respectively.

GMM: It models user's mobility patterns using the Gaussian Mixture Model. Each user's check-in records are represented using several states, each state modeled using Gaussian distribution. In our experiments we choose two states: home and work [Cho et al., 2011; Zhu et al., 2015].

where, π1...πk, are the mixture weights of the states, µ1...µk, the mean of each state and Σ1...Σk, the variance of each state.

Baseline: In equation (1) in section 4 we pluginMost Frequent Checkins as the location model, Simple Category Distribution as the category model and average time lag based exponential distribution as the temporal model.

where, Iℓ is the number of instances when u has checked-in at ℓ, ICℓ is the number of instances when u has checked-in at category set Cℓ, and ∆tu,v is the average of time lag between u and v check-ins in the training data.

ROC and AUC: Figure 5 shows ROC curves and table 5 shows AUC (area under the curve) of different influence quantification models on different datasets. It can be observed that LoCaTe model outperforms DMM Basic and DMM Social models quite significantly on FSq'16 dataset, where we have a single category with each location. On the other datasets where we have a set of categories with each location, although we observe that LoCaTe model outperforms DMM Basic and DMM Social models, but we are able to leverage the category information better in the case of a single category with each location. The efficacy of the LoCaTe model is not only contributed by additional knowledge we gain from categories, but also the temporal based user-user correlation modelling, and the adaptive KDE based mobility model (Lo). The Lo model provides a better fit to the mobility data as for each testing location the distance around it is determined using the k nearest neighbours (from the training data). On the other hand, the distance based mobility model (DMM) is sensitive to short distances and thus assigns a low probability to locations at larger distances.

6 Conclusion

In this paper, we addressed the problem of influence quantification in the location promotion setting, and proposed a model that incorporates not only the traditional user mobility models but also socially induced temporal correlation of users as well as the affinity of users to a location based on semantics of the location. The resulting LoCaTe model has demonstrated more than 54% improvements over state-ofthe-art methods over a number of real-world LBSN data with a large number of users and spanning more than a year.