Point-Of-Interest Recommendation Using Temporal Orientations of Users and Locations

Abstract

Location Based Social Networks (LBSN) promotes communications among subscribers. Utilizing online check-in data supplied via LBSN, Point-Of-Interest (POI) recommendation systems propose unvisited relevant venues to the users. Various techniques have been designed for POI recommendation systems. However, diverse temporal information has not been studied adequately. From temporal perspective, as visited locations during weekday and weekend are marginally different, we choose weekly intervals to improve effectiveness of POI recommenders. However, our method is also applicable to other similar periodic intervals. People usually visit tourist and leisure spots during weekends and work related places during weekdays. Similarly, some users perform check-ins mostly during weekend, while others prefer weekday predominantly. In this paper, we define a new problem to perform recommendation, based on temporal weekly alignments of users and POIs. We argue that locations with higher popularity should be more influential. Therefore, In order to solve the problem, we develop a probabilistic model which initially detects a user’s temporal orientation based on visibility weights of POIs visited by her. As a step further, we develop a recommender framework that proposes proper POIs to the user according to her temporal weekly preference. Moreover, we take succeeding POI pairs visited by the same user into consideration to develop a more efficient temporal model to handle geographical information. Extensive experimental results on two large-scale LBSN datasets verify that our method outperforms current state-of-the-art recommendation techniques.

1 Introduction

Nowadays, pervasive applications of Location-Based Social Networks (LBSN) assist further communications between online users. For instance, people can easily share relevant data via LBSN check-in services (e.g. Foursquare, Facebook places and Google+). When a user performs a check-in at a venue, she reports the location, time and enclosed artifacts (text, photo, audio or video) [19, 32]. In return, LBSN data facilitates Point-Of-Interest (POI) recommenders to propose attractive locations to the users that are not yet visited by them. Therefore, POI recommendation is beneficial for people as well as industry (e.g. tourism).

The POI recommendation problem has already received increasing research attentions. Some traditional models [21, 24] predict user’s interest on POIs through Random Walk and Restart process on a graph which holds both users’ social links and check-in logs. However, this model is not effective on LBSN, as friendship between users doesn’t reflect similar check-in behaviours [3]. Recently, Collaborative Filtering (CF) methods [25, 26] has achieved promising results in POI recommendation. However, the multi-facet time factor is not yet studied adequately. So, we aim to further promote user-based collaborative filtering through mining temporal properties of both users and POIs.

Intuitively, User-POI matrix reflects the correlation between users (rows) and POIs (columns) in LBSN. The value for each entry can be defined as binary (i.e. 1 if user visits the POI, otherwise 0). The main problem involved in POI recommendation is data sparsity [23]. The reason is that users only visit a small number of POIs which decreases the density of the User-POI matrix. This issue affects majority of CF methods. Therefore, additional information needs to be extracted to improve effectiveness. Ye et al. introduced the concept of Geographical Influence(GI) [25, 26] based on the observation that people tend to visit POIs close to their own previously visited places. Later on, several studies took different kinds of Temporal Influence into consideration. e.g. [5, 26, 27] generate User-POI-time (UTP) matrix through splitting the day into time slots and learn user’s feasibility to check-in at a location in each time slot. Obviously, UTP matrix is even more sparse. So, to alleviate the sparseness, [28] proposes TICRec Framework which applies a density estimation method and [26] computes cosine similarity based on visited locations in related time slots. Moreover, Gao et al. [5] suggest LRT which can be configured to adapt various temporal intervals (e.g. weekly, monthly and etc.). However, in current temporal approaches, the correlations between users and the check-ins are merely considered (i.e. User-POI or UTP matrices) and user-specific and location-specific temporal properties are not appreciated. Hence in our work, we consider such temporal alignments of both users and venues to further improve POI recommendation systems.

Table 1. Sample of weekly oriented POIs visited more than 50 times by varied users

From temporal perspective, while certain venues are visited more during weekday or weekend, some users also show their interest to perform check-ins mainly during either weekday or weekend. We verify this through observations (Sect. 2.1). Intuitively, we can imply two facts: (a) If a user is mostly aligned toward weekday, we should offer her more from weekday oriented POIs. (b) If a group of POIs have the same rank, they should be offered to the user based on her temporal preference. We name User and POI weekly alignments as User Act and POI Act respectively.

The main challenge here is to compute the User/POI Acts through the check-in history and integrate these temporal preferences in recommendation consistently. The naïve approach is to count the number of visits during weekday/weekend and recommend POIs based on the user’s temporal orientation. However, not all the POIs are the same in their impacts. On the other hand, the probabilities for a user to visit different POIs are not the same. Based on [25], three factors of Collaborative Filtering, Geographical Influence and Friendship, determine the visibility weight for a user to check-in at a location. So, POIs should be treated differently based on their visibility weights. Our approach comprises three steps: (i) Firstly it predicts the probability for user i ($u_i \in U$) to visit any POI in her check-in history ($L_i$). (ii) Secondly, we use a probabilistic approach to compute $u_i$’s act which denotes her interest toward weekday/weekend intervals. Consequently, as higher the probability of a POI is, its influence on $u_i$’s act is considered more inflated. (iii) Finally, if the user’s weekly alignment exceeds the threshold, we then apply temporal recommendation approach that initially computes the POI act for any location in primary recommendation list. According to $u_i$’s act, it finally proposes a combined list of neutral and temporally oriented locations. We designate weekly intervals because on one hand, majority of locations visited during the weekdays and weekends are obviously divergent (Table 1) and on the other hand, the visiting pattern repeats frequently. However, our model is applicable to other similar periodic intervals.

In this paper, we also put emphasis on temporal aspect of geographical influence [25] and limit the primary observation to daily consecutive pairs. We confirm that it still follows power law distribution. This makes the cost function minimization quicker. We also employ Normal Equation (NE) instead of the Gradient Descent (GD) which obtains optimized parameters in one round. In short, the contributions of this paper are listed as follows:

• We observe the concept behind weekly oriented users and POIs. We also design a probabilistic model to compute such temporal alignments.

• We propose a recommender framework to discretise continuous stream of LBSN users and suggest them a set of POIs according to their weekly preferences. Our method outperforms the state of the art in POI recommendation.

• Finally, we have also taken subsequent POI pairs visited by the same user into consideration and using relevant temporal observation we have provided an optimized model for geographical influence.

The rest of this paper is formed as follows: Sect. 2 explains primary definitions and insightful observations. Section 3 clarifies our temporal recommendation framework. Section 4 provides empirical concepts about collaborative filtering and geographical influence. Section 5 discusses experimental results. Related research work is surveyed in Sect. 6. In Sect. 7 we close this paper with some conclusive remarks.

2 Temporal Influence

In this section, we setup two observations based on primary definitions. We verify that certain POIs and users are aligned toward either weekday or weekend.

Definition 1

(POI Act). Given a set of POIs $\mathbb {P}=\{p_1, p_2,\dots , p_n\}$, each $p_j$ ($\forall p_j \in \mathbb {P}$) has a POI Act denoted as $p_j^a$ (Eq. 1), which is the margin value ($[ -1,1 ]$) between its probabilities to be visited during weekday ($w_d$) and weekend ($w_e$).

$$\begin{aligned} p_j^a=\frac{W_j^d}{N_j}-\frac{W_j^e}{N_j} \end{aligned}$$

(1)

Here, $W_j^d$ and $W_j^e$ denote the number of visits at $p_j$ during $w_d$ and $w_e$. Also $N_j$ is its total number of visits. If $p_j^a$ is greater than zero, it will exhibit an alignment toward $w_d$ and if it is less than zero, it’ll show that $p_j$ is visited more during $w_e$. Otherwise (if $p_j^a=0$), $p_j$ will be neutral (not temporally aligned)

Definition 2

(User Act). Given a set of users $\mathbb {U}=\{u_1, u_2,\dots ,u_n\}$, we define that each $u_i$ ($\forall u_i \in \mathbb {U}$) has a User Act denoted as $u_i^a$ (Eq. 2) which is the margin value ([-1,+1]) between probabilities of her $w_d$ and $w_e$ visits.

$$\begin{aligned} u_i^a=Avg_i^d-Avg_i^e \end{aligned}$$

(2)

$Avg_i^d$ and $Avg_i^e$ are probabilities for $u_i$ to visit locations during $w_d$ and $w_e$ respectively. If $u_i^a$ is greater than 0, it will reflect $u_i$’s temporal preference toward $w_d$ and if it is less than 0, it’ll indicate that she is more interested in $w_e$.

2.1 Observations

We setup two observations to perceive that certain POIs and users can be oriented toward $w_d$ or $w_e$. We use threshold T to reflect the extent of alignment. As, people visit $w_e$ oriented places during casual Friday (e.g. they go to bar on Friday night and perform sport activities on Friday afternoon), we include Friday as weekend. Hence, $w_d$ has one day more than $w_e$, and T is $\frac{1}{7} \approx 15\,\%$ which is consistent with uniform distribution of locations for each day in a week.

1. Absolute POI Act Observation: This observation demonstrates that many POIs are significantly used either during $w_d$ or $w_e$. On the other hand, we aim to study to what extent each POI is oriented toward either $w_d$ or $w_e$. Hence, for each $p_j$, visited by a set of users $U_j$, we compute $p_j^{a*}$ (Eq. 3) as an absolute rate of temporal $w_d$/$w_e$ deviation. In this inspection, we choose those locations from both datasets (Sect. 5.1) that are visited by at least 5 users.

$$\begin{aligned} p_j^{a*} = \frac{\sum _{u_i \in U_j}|p_{i,j}^d-p_{i,j}^e|}{|U_j|} \end{aligned}$$

(3)

$p_{i,j}^d$ and $p_{i,j}^e$ are the probabilities of each $u_i \in U_j$ to visit $p_j$ during $w_d$ and $w_e$ (Eq. 4):

$$\begin{aligned} p_{i,j}^d=\frac{W_{i,j}^d}{W_{i,j}}, p_{i,j}^e=\frac{W_{i,j}^e}{W_{i,j}} \end{aligned}$$

(4)

Here $W_{i,j}$ is the total number of times that each $u_i \in U_j$ has visited $p_j$. Also, $W_{i,j}^d$ and $W_{i,j}^e$ record the visits performed exclusively during $w_d$ and $w_e$.

Fig. 1 a and b depict the probabilities regarding POIs’ weekly deviations based on different ranges (e.g. 0.3–0.4). As highlighted in dark orange, more than 70 % of the POIs in both datasets have an average absolute orientation greater than T. This means that majority of locations in both datasets are predominantly used either during the weekend or weekday.

Fig. 1.

Observation on Absolute POI Act

2. Absolute User Act Observation: Similarly, for each user $u_i$ with $L_i$ as the check-in log, we compute $u_i^{a*}$ (Eq. 5) as her average rate of absolute temporal $w_d$/$w_e$ deviation. We select users who has visited at least 8 POIs ($\{\forall u_i \in \mathbb {U} | \left| L_i \right| >8\}$). Figure 2 a and b illustrate relevant probabilistic bins which reflects to what extent each user is temporally oriented (disregarding the alignment toward $w_d$ or $w_e$). $\left| p_{i,j}^a\right|$ is $p_j$’s absolute POI act limited to $u_i$’s visits.

$$\begin{aligned} u_i^{a*} = \frac{\sum _{p_j \in L_i}|p_{i,j}^a|}{|L_i|} \end{aligned}$$

(5)

If $u_i^{a*}$ is less than T(15 %), we can ensure that $u_i$ is not oriented toward $w_d$ or $w_e$. However, as highlighted in dark orange (Fig. 2), 57.3 % and 61.6 % of users in Foursquare and Brightkite have an absolute temporal deviation more than the T. Also more than 10 % of users are highly aligned toward either weekday or weekend ($u_i^{a*}>45\,\%$).

Based on the observations conducted in LBSN, we can now conclude that weekly temporal influences exist for both users and POIs.

Fig. 2.

Observation on Absolute User Act

3 Recommendation

In this section, we firstly provide an efficient approach to compute user acts and secondly we describe our recommendation framework.

3.1 User Act Efficient Model

Primary user act (Definition 2, Eq. 2) treats all POIs the same, while they differ based on POI acts and visiting influence. Therefore, we propose a more effective model to compute the user act. We first need to obtain user’s visiting orientation toward $w_d$ or $w_e$. Therefore, we compute the POI act for every location visited by $u_i$ ($p_j \in L_i$). We use Eq. 6 to find positive or negative impacts.

$$\begin{aligned} \hat{p}_{i,j}^d=(p_{i,j}^d - \lambda ) , \hat{p}_{i,j}^e=(p_{i,j}^e - \lambda ) \end{aligned}$$

(6)

Where $\lambda \in (0,1)$ serves as a separator of $w_d$/$w_e$ margins. If we assume $\lambda =0.5$, $p_{i,j}^d= 0.75$ and $p_{i,j}^e=0.25$, then $\hat{p}_{i,j}^d=0.75-0.5=0.25$, which indicates that $p_j$ has a positive impact on user $i's$ weekday act. We argue that the POI with higher probability to be visited by a user (visiting influence) should play a more significant role in computation of her user act. [25] comprises three influential modules of Collaboration, Friendship and Vicinity which we use to compute visiting influence for each location ($p_j$). Our modifications on baseline are described in Sect. 4. To capture visiting influence, we remove each $p_j$ from $L_i$, we can subsequently obtain $c^*_{i,j}$ which represents the probability of $u_i$ to visit $p_j$ considering all three modules. We then normalize (i.e. between (0,1]) the results using Eq. 7:

$$\begin{aligned} \hat{c}^*_{i,j}=\frac{c^*_{i,j}-Min_{ci}}{Max_{ci}-Min_{ci}}, \end{aligned}$$

(7)

where $Max_{ci}=arg_{max} ({C^*_{i,k}}), Min_{ci}=arg_{min} ({C^*_{i,k}}), \forall p_k \in L_i$. To get the final weekday orientation probability for each $p_j \in L_i$ we use Eq. 8:

$$\begin{aligned} Pr_{i,j}^d=\hat{c}^*_{i,j} * \hat{p}_{i,j}^d=\frac{c^*_{i,j}-Min_{ci}}{Max_{ci}-Min_{ci}} * (p_{i,j}^d - \lambda ) \end{aligned}$$

(8)

The higher $\hat{c}^*_{i,j}$ is, the more likely this location will be visited by $u_i$ and will be more influential on $u_i$’s act. Similarly, the weekend orientation probability ($Pr_{i,j}^e$) can be computed as follows:

$$\begin{aligned} Pr_{i,j}^e=\hat{c}^*_{i,j} * \hat{p}_{i,j}^e=\frac{c^*_{i,j}-Min_{ci}}{Max_{ci}-Min_{ci}} * (p_{i,j}^e - \lambda ) \end{aligned}$$

(9)

Finally, the user act orientation is obtained through Eq. 10:

$$\begin{aligned} \hat{u_i^a}=\left| \tilde{Avg}_i^d-\tilde{Avg}_i^e \right| \end{aligned}$$

(10)

While $\tilde{Avg}_i^d$ (Eq. 11) and $\tilde{Avg}_i^e$ (12) are respective $w_d$/$w_e$ average ratios.

$$\begin{aligned} \tilde{Avg}_i^d=\frac{\varSigma _{p_j\in L_i}Pr_{i,j}^d}{|L_i|} \end{aligned}$$

(11)

$$\begin{aligned} \tilde{Avg}_i^e=\frac{\varSigma _{p_j\in L_i}Pr_{i,j}^e}{|L_i|} \end{aligned}$$

(12)

The value regarding $\tilde{Avg}_i^d$-$\tilde{Avg}_i^e$ shows the direction. If it is greater than zero, it will indicate that user is aligned toward $w_d$ and if it is less than zero, it will show $w_e$ orientation.

3.2 Framework

In this section, we propose the framework which suggests a ranked list of candidate POIs for each user disregarding the extent of her temporal orientation.

Fig. 3.

Continuous stream of users is discretized by first computing relevant user acts and then utilizing of threshold T.

As Fig. 3 depicts, we can imagine the input of a recommender system as a continuous stream of users in course of time. Utilizing check-in history, the system should suggest top @Num appealing locations for each user. A basic POI recommender system doesn’t differentiate $w_d/w_e$ temporal preferences, however we use threshold T to discretise input users based on their effective user acts (Sect. 3.1). If they pass the threshold, temporal method will be employed otherwise they will be treated as non-temporal users. For example, $u_m$ and $u_v$ are oriented to do the check-ins during $w_d$. However unlike $u_m$, $u_v$ doesn’t surpass T and is not adequately oriented toward $w_d$ so the framework doesn’t apply the temporal method for her. While the user act reflects how a user performs the check-ins in weekly cycles, POI act is used in recommendation process to suggest right POIs to the right users through utilizing of such temporal preferences.

$$\begin{aligned} f(L_i)= {\left\{ \begin{array}{ll} M_{avg}(\rho ,\delta )&{} \text {if } \hat{u_i^a}\ge T\\ usg_w &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(13)

As formulated in Eq. 13, the system receives $u_i$’s check-in log ($L_i$). If the user act computed based on $L_i$ exceeds threshold T, the system will utilize temporal influence. Otherwise the user will be recommended by $usg_w$ [25] which also integrates further modifications (Sect. 4). In temporal case, $\rho$ is the initial list of recommending POIs computed by USG and $\delta$ resembles the POI act for each item in primary recommendation list. $\rho$ and $\delta$ are the input of $M_{avg}$ function which performs recommendation as described in Sect. 3.3.

3.3 Temporal Act Based Recommendation

If the efficient user act is greater than threshold ($\hat{u_i^a} \ge T$), we need to follow temporal recommendation approach ($M_{avg}$). The method has two inputs. $\rho$ which is the primary decently sorted recommendation list and $\delta$ which includes the acts for each of POIs in $\rho$. We first retrieve Top K*@Num items from $\rho$ while @Num is the number of final list (denoted as R). R is formed by three subsets of Weekday aligned($R^d$), Weekend oriented($R^e$) and Neutral ($R^n$) where $R=\{R^d,R^e,R^n\}$ and $|R|=@Num$. The final proportion for each category will follow relevant ratios from proper POIs which are computed based on efficient user act (Eq. 14).

$$\begin{aligned} M_{avg}(\rho ,\delta )= {\left\{ \begin{array}{ll} \left| R^d\right| =(\tilde{Avg}_i^d+\lambda -\frac{\xi }{2})* @Num &{} \text {if } p_y^a>\theta \\ \left| R^e\right| =(\tilde{Avg}_i^e+\lambda -\frac{\xi }{2})* @Num &{} \text {if } p_y^a<\theta \\ \left| R^n\right| =\xi * @Num &{} Otherwise \end{array}\right. } \end{aligned}$$

(14)

Here, $(\tilde{Avg}_i^d+\lambda -\frac{\xi }{2})$ and $(\tilde{Avg}_i^e+\lambda -\frac{\xi }{2})$ are respective $w_d$ and $w_e$ proportions from final recommendation list. Also $\theta$ is the threshold for detection of $w_d$/$w_e$ oriented POIs. For example if $\theta =0$, the weekday portion from the final list will comprise the POIs whose acts are greater than 0 ($\forall p_y^a \in \delta |p_y^a>0$) and for weekend ratio the POI acts should be less than 0 ($\forall p_y^a \in \delta |p_y^a<0$). In fact, Neutral POIs are not likely to have high scores in $w_d$/$w_e$ lists. However, we still need to propose them when they gain high probabilities. Therefore we reserve a minor portion ($\xi$) for POIs which are not temporally aligned.

4 Utilizing Primary Influences

In this section, we provide our empirical details on two primary modules in POI recommendation which are Geographical Influence and User based Collaborative Filtering. For social influence we adapt the method used in [25].

4.1 Geographical Influence

Geographical Influence (GI) [25, 26, 28] declares that individuals visit locations which are close to those they have visited previously. Considered as another important module in location recommendation, we provide an empirical review about it. We observe two cases: (i) Non-temporal: We compute geographical distance between each POI pair in one’s check-in history. (ii) Temporal: We also perform another test on consecutive check-ins within a time period. This period denotes an average distance between two subsequent POIs that a user may travel in less than a day ($T_g$ = 12 h). In order to invalidate the noise, we apply the speed condition ($\varDelta _d /\varDelta _t<\gamma$) in which $\varDelta _d$ is the distance between two adjacent POIs and $\varDelta _t$ is the time spent presumably to travel between them.

Fig. 4.

Geographical influence observation: probabilities of the distance ranges

As illustrated in Fig. 4a, majority of distances between POI pairs are less than 100 km. Also, about 25 % are less than 10 kms. Notice that the scale is modified after 1000 kms and the spike shows the sum. In temporal aspect (Fig. 4b), the highest probability for distance between two daily consecutive POIs is less than 100 kms. The similar figures are seen on Foursquare. In both observations, the probability of the distance between a POI pair, follows power law distribution (polynomial: $y=ax^m$ while x is the distance between the POI pair, y is its probability and both a and m are optimizing parameters). However, the number of consecutive POI pairs limited to threshold $T_g$ is merely 2.5 % of all POI pairs. This makes the cost function minimization faster while the distance probabilities will be close after applying the feature scales. Hence, we train single feature hypothesis based on the temporal set. The polynomial equation can be converted to the Linear Regression. We also employed Normal Equation (NE) instead of the Gradient Descent (GD) for minimization. NE obtains optimized parameters in one round unlike GD which applies various learning rates with multiple iterations. Indeed, NE performed well as there is only one feature in regression (distance between POI pair) and the size of the matrix was small. Here, the probability for $u_i$ (with $L_i$ as check-in log) to visit location $l_j$ is the multiplication of the distance probabilities between $l_j$ and each location $l_y \in L_i$. However, multiplying numerous decimal points will pass the minimum value and the result will be zero for many $l_j$s. Therefore, we suggest a log based Eq. 15 where a and m are optimized values and d implies the distance function between a pair.

$$\begin{aligned} log(Pr[l_j|L_i])=\sum _{l_y \in L_i} a \times d(l_y,l_j)^m. \end{aligned}$$

(15)

4.2 User-Based Collaborative Filtering

In a binary logic (like [25, 26]), while L and U are respective set of locations and users, if user $u_i \in U$ has already visited $l_j \in L$, then $c_{i,j}$ will be 1 otherwise 0. Moreover, cosine similarity weight (Eq. 16) between $u_i \in U$ and $u_k \in U$ ($w^+_{i,k}$) is computed based on the number of shared POIs among ($L_i \cap L_k$). Here, $L_i \subset L$ and $L_k \subset L$ are corresponding check-in histories belonged to $u_i$ and $u_k$.

$$ \begin{aligned} \begin{array} {lcl} w^+_{i,k} = \frac{\sum _{l_j \in L_i \cap L_k} c_{i,j}c_{k,j}}{\sqrt{\sum _{l_j \in L_i}c^2_{i,j}}\sqrt{\sum _{l_j \in L_k}c^2_{k,j}}} \, \, \, \, \, \, \, \& \, \, \, \, \, \, \, c^+_{i,j} = \frac{\sum _{\{\forall u_{k}|w_{i,k}>0\}} w_{i,k}c_{k,j}}{\sum _{\{\forall u_{k}|w_{i,k}>0\}} w_{i,k}} \end{array} \end{aligned}$$

(16)

In order to recommend a set of locations to $u_i$, we merely select items from users who share one or more POI(s) with $u_i$. In fact, if $L_i \cap L_k= 0$ and $l_j \in L_k$ then the check-in probability for $u_i$ to visit $l_j$ (Eq. 16, $c^+_{i,j}$) will be zero unless $l_j$ is already visited by another user $u_m$ while $L_i \cap L_m \ne 0$. Such empirical point will reduce the number of iterations during recommendation process. This is done through excluding those who does not share any location with current user. We were inspired by this experimental point to argue that influential effect of $l_j \in L_i$ on $u_i$’s temporal preference increases by the number of visits on $l_j$ performed by any $u_m \in U$ while $L_i \cap L_m \ne 0$.

5 Experimental Evaluation

In this section we plot and implement multiple experiments to compare our proposed method with a few alternative approaches (Sect. 5.3). Our main goal is to ensure how the concept of User/POI act can improve baseline methods which merely rely on User/POI correlations and neglect possible user and POI specific temporal influences. Nevertheless, we need to take a point into consideration that effectiveness of POI recommendation systems on LBSN datasets are always affected by low density of User-POI matrices. Hence, rather than measuring the differences using absolute values, we count on relative excellence in comparison.

Table 2. Statistics of the datasets

5.1 Dataset

In this paper, experiments are conducted on two large-scale real [3] LBSN datasets. Both (Foursquare¹ and Brightkite²) are publicly available. Relevant statistics are shown in Table 2. Furthermore, Fig. 5 depicts POI distribution of both datasets on the map. The Brightkite dataset is more extensive, however it is extremely sparse (Density: $2.7 \times 10^{-5}$) and more than 50 % of the dataset is formed by check-in history of cold start users. Similarly in Foursquare, only 8 % of user pairs share more than 5 POIs.

Fig. 5.

Check-in distribution

5.2 Evaluation Metrics

Considering top N (e.g. 5, 10 and 20) results returned by a POI recommendation system, there are two methods to evaluate its effectiveness. The first approach is survey based which employs the normalized Discounted Cumulative Gain (nDCG) [16]. The other method (used in this paper) utilizes F1-score ratios. In this method, we firstly exclude x % (default 30 %) of POIs from check-in history of any user. We then train recommendation model using rest of the POIs. Finally, we examine how many of excluded POIs are recovered using returned list of recommendation. As denoted in Eq. 17, Precision@N is the ratio of total Number of recovered POIs ($R_p$) to the number of recommended POIs (N). However, Recall@N would be the ratio of total Number of recovered POIs ($R_p$) to the number of initially excluded POIs ($E_p$). Indeed, Precision, Recall and F1-score metrics are computed for each test user (20 % of all dataset users) and final metrics are computed based on the total average. $F1-score@N$ will be the final performance metric.

$$\begin{aligned} \begin{array} {lcl} Precision@N=\frac{R_p}{N}, Recall@N=\frac{R_p}{E_p}, F1-score@N= \frac{2\times Precision@N \times Recall@N}{Precision@N + Recall@N}. \end{array} \end{aligned}$$

(17)

5.3 Recommendation Methods

Recommendation methods used in experiments are as follows:

• User-based CF (UBCF): The primary User-based collaborative filtering.

• User-based CF Temporal (UBCFT): Another version of our model which treats all the POIs the same in computation of the user act. Referring to Eq. 13, probabilities of $\rho$ for input of $M_{avg}$ function is calculated using Eq. 16.

• USG: Denoted by USG, this method takes advantage of three modules of User-based CF, Social Influence and Geographical Influence where $0<\alpha < 1$ and $0<\beta < 1$ [25]. We will adapt User-Time-POI model (Baseline: [26]) in future work as we limited sparsity to User-POI matrix.

• Temporal U+S+G (USGT): Model proposed in this paper (Sects. 2 and 3).

5.4 Impact of Parameters

With regard to Eq. 6, we assume $\lambda =0.5.$ to treat $w_d$ and $w_e$ the same. Moreover, in order to decide on the value of $\xi$ in Eq. 14, we chose a random set of 20 % from users in both datasets and measured the rate of neutral POIs ($\{\forall p_y \in \rho | p_y^a=0\}$) in top K*@Num items from recommendation list. As the rate was less than 10 % in both datasets, we set the value for $\xi$ to 0.1 (e.g. 2 if @Num=20). Moreover, we set K to 10. Finally, in order to reproduce the tri-module baseline (USG:[25]), despite other automatic models in rank learning (e.g. SVM pairwise and EM), we employed tuning (Table 3). We changed the values for $\alpha$ and $\beta$ between 0 and 1 to get the best performance @5. The optimized parameters of $\alpha$ and $\beta$ are selected based on the best values of F1-score@5.

Table 3. USG optimised values

Referring to Eq. 18, $S_{i,j}$ denotes the final prediction probability for $u_i$ to perform a check-in at location $l_j$. $S^u_{i,j}$ denotes user based CF probability, $S^s_{i,j}$ [25] and $S^g_{i,j}$ (Sect. 4.1) provide the values for social and geographical influence respectively. we employ feature scaling [20] to make statistical values consistent.

$$\begin{aligned} S_{i,j}=(1-\alpha -\beta )S^u_{i,j}+\alpha S^s_{i,j}+\beta S^g_{i,j}. \end{aligned}$$

(18)

5.5 Performance Comparison

Next, we discuss the results to summarize our findings. Figures 6 and 7 illustrate output of experiments for foursquare and brightkite datasets. In these figures, our proposed method (USGT) clearly outperforms other models. UBCFT exhibits a minor improvement compared to UBCF. This shows that User/POI acts must be computed based on the visiting influence as implemented in USGT.

Fig. 6.

Comparing the methods - Foursquare dataset

Fig. 7.

Comparing the methods - Brightkite dataset

Also, notice that in LBSN sparse condition when the density of User-POI matrix is extremely low, the effectiveness of the location recommenders is not inflated. For example, precision in [26] and recall in [13] are less than 4 % and for [5] both metrics are less than 3.5 %. Hence, performance evaluations are relative based on algorithms. Moreover, recall can be low even for active users. The reason is concealed in evaluation metrics. For instance in case of recommending @5, when all top 5 recommended POIs are recovered from initially excluded items, precision will be 100 %. However the recall value will be dependent on the number of excluded POIs. Considering a 30 % excluded from 150 POIs in a user’s history, the recall will then be only 5/50 = 10 %. Hence, if majority of active users in a dataset include numerous visited POIs in their check-in history, recall ratio for active users will still be little.

6 Related Work

As the survey [1] reports, with regard to expeditious extension of LBSN platforms (e.g. Foursquare, Gowalla and so on), POI recommendation to individuals via such mediums have become pervasive. Three modules of Collaborative Filtering (CF), Social Influence (Friendship in networks) and Geographical Influence are essential in such recommenders. However, integration of the time factor in any one of these modules is also considered as another multi-aspect influential parameter. This is despite the fact that some primary methods like HIT-based [31] and Random Walk&Restart [21, 24] have already been used for location recommendation.

are of two types of memory and model based. Memory based approach is divided into two categories of item and user based. In user based approach the weight of similarity between certain users will be computed by employing a measurement function such as Cosine or Pearson. Subsequently, the probability for a user to visit a POI will be calculated using the rating of the similar users on the same POI [25]. We also utilize user based collaborative filtering in POI recommendation. However, in item-based approach, the co-visited POIs will be found first and then a weighted mixture of user ratings upon similar POIs will be computed [4]. CF methods in recommendation have employed various types of data such as text (e.g. [8]), GPS trajectories [9, 10, 30] and check-in logs [1]. Nonetheless, they have failed to gain adequate performance metrics. Therefore other components (e.g. Social and Geographical influence) have been appended to improve recommendation results.

Social links may also influence users in visiting new POIs [2, 6, 7, 25]. However, this parameter can’t be effective independently in certain conditions like cold start scenarios when the users miss adequate check-in history or friends on the network. Ye et al. [25] employs Jaccard coefficient to model similarity of two users based on shared locations and friends. They accord higher importance to the shared locations than friends which implies that the number of shared locations surpass social links. While considering the time factor [7] studies how the user can actively influence the friends or be affected by them. They also model influence propagation through social links.

Geographical Influence (GI) has been observed in several previous works [14, 22, 25, 26, 28] and states that spatial proximity between POIs matters in recommendation. On the other hand, users tend to visit the POIs which are close in distance to their previously visited locations. This has already been denoted for the POIs of the users using Power law distribution and Gaussian model. Considering the pre-assumption, GI can only be considered as an extension to the CF module as if it fails to suggest remote POIs for users even if the prediction probability might be a tiny value. We have also witnessed the GI observation (including the temporal aspect of subsequent timely ordered POIs) in our datasets. Moreover, we have employed Normal Equation to minimize the error function and exploit optimized parameters of the distribution function.

Temporal influence has also been studied from various aspects recently. Yuan et al. [26] confirm that some locations are visited in particular day/night times (e.g. library during the day or bars during the night). They prove that such day time similarity can improve location recommendation. From another perspective, [17, 29] take periodicity into consideration, which is based on the intuition that some locations are visited on daily, weekly or annual intervals. [18, 24] also categorize the check-ins into long-term and short-term visits. Long term determines the steady patterns witnessed all along the check-in history, while short term states otherwise. However, their approach is not applicable when the users do not visit the venues continuously. Like motif in graphs, [15, 29] aim to discover repeated temporal patterns. Li et al. [11] propose a rating scheme that grants higher scores to the newly visited locations. This is based on the fact that human beings can’t remember everything from long time ago.

A user’s interest can be relevant to proposed POI’s specifications. While we study associated temporal patterns between users and POIs, [12] takes the textual context into consideration. They use Latent dirichlet allocation (LDA) to learn a user’s topics of interest and choose the POIs based on their associated topics. Current temporal models in POI recommendation including Matrix Factorization [5], Collaborative Filtering [26], Graph-based [27] and Density estimation [28] perform recommendation using user, time and POI correlations. However, we include periodic (e.g. weekly) temporal preferences of Users and Locations to improve effectiveness.

7 Conclusions

In this paper, a temporal POI recommendation system has been proposed for Location-based social networks. Relying on primary insights, we observe that certain locations are visited more during weekends while some others are aligned toward weekdays. The similar orientation is witnessed in check-in behaviour of LBSN users. Thus, an intelligent POI recommender should logically take such user/POI preferences (act) into consideration. While previous models are defined based on the correlation among users and POIs, we extend recommendation systems in a probabilistic approach to include user and POI specific temporal influences. Our framework recommends relevant POIs to users based on their weekday/weekend alignments. Furthermore, we have taken subsequent POI pairs visited by the same user into consideration and provided an optimized version of geographical influence. Proposed model in this paper outperforms current state-of-the-art recommendation techniques. Considering the importance of this temporal aspect, we plan to integrate it into model based methods in future.