Location Recommendation for Location-based

Social Networks

Mao Ye Peifeng Yin Wang-Chien Lee

Department of Computer Science and Engineering
The Pennsylvania State University
University Park, PA 16802, USA
{mxy177,pzy102,wlee}@[Link]

ABSTRACT networking services allow users to connect with friends, ex-

In this paper, we study the research issues in realizing loca- plore places (e.g., restaurants, stores, cinema theaters, etc),
tion recommendation services for large-scale location-based share their locations, and upload photos, video, and blogs.
social networks, by exploiting the social and geographical As city and neighborhood exploration is one of the main
characteristics of users and locations/places. Through our themes in many location-based social networking services, it
analysis on a dataset collected from Foursquare, a popu- is highly desirable for such services to provide location recom-
lar location-based social networking system, we observe that mendations to their users. Moreover, as the users and loca-
there exists strong social and geospatial ties among users tions in location-based social networking services are rapidly
and their favorite locations/places in the system. Accord- growing, it is essential to adopt efficient techniques for real-
ingly, we develop a friend-based collaborative filtering (FCF) izing location recommendation.
approach for location recommendation based on collabora- Fueled by a broad application base in on-line shopping,
tive ratings of places made by social friends. Moreover, we recommendation systems have received a lot of attention
propose a variant of FCF technique, namely Geo-Measured from both the industry and academia. Recently, a number of
FCF (GM-FCF), based on heuristics derived from observed studies have explored the use of social relationship amongst
geospatial characteristics in the Foursquare dataset. Finally, users in recommendation systems to enhance the effective-
the evaluation results show that the proposed family of FCF ness of recommendation techniques [1, 3, 4]. The main ideas
techniques holds comparable recommendation effectiveness behind these studies are to employ the trust and interest sim-
against the state-of-the-art recommendation algorithms, while ilarity carried along in social relationships amongst friends
incurring significantly lower computational overhead. Mean- to enhance personalized search and recommendations. How-
while, the GM-FCF provides additional flexibility in tradeoff ever, these prior works mainly focus on conventional rec-
between recommendation effectiveness and computational ommendations in social networks. In this paper, we study
overhead. the research issues in realizing location recommendation for
large-scale location-based social networks. Particularly, we
Categories and Subject Descriptors aim at exploiting both social and geographical characteris-
H.4 [Information Systems Applications]: Recommen- tics of relationships amongst users and places to support the
dation system location recommendation services.
While existing recommendation techniques for conventional
General Terms social networking systems may be applicable to the location
Application recommendations, these techniques [2, 3] usually incur very
high computational overhead. Owing to the rapidly growing
Keywords number of users and locations in location-based social net-
Location recommendation, social networks, location-based working services, these existing techniques are not efficient
systems for on-line recommendation services. By exploring the strong
social tie between friends, in this paper, we propose the
1. INTRODUCTION friend-based collaborative filtering (FCF) approach for loca-
With the rapid development of mobile devices, wireless tion recommendation based on collaborative ratings of com-
networks and Web 2.0 technology, a number of location- monly visited places made by social friends. Additionally, we
based social networking services, e.g., Loopt1 and Foursquare2 , propose a variant of FCF technique, namely Geo-Measured
have emerged in recent years. These location-based social FCF (GM-FCF) based on heuristics derived from observed
geospatial characteristics in the Foursquare dataset. We
1
[Link] conduct a comprehensive performance evaluation to validate
2
[Link] our proposal and make comparison with the state-of-the-art
recommendation algorithms, including the conventional col-
laborative filtering (CF), social collaborative filtering (SCF)
and random walk and restart (RWR). The evaluation re-
Permission to make digital or hard copies of all or part of this work for sults show that the family of FCF techniques holds com-
personal or classroom use is granted without fee provided that copies are parable recommendation effectiveness against the compared
not made or distributed for profit or commercial advantage, and that copies algorithms, while incurring significantly lower computational
bear this notice and the full citation on the first page. To copy otherwise, to overhead. Meanwhile, the GM-FCF provides additional flex-
republish, to post on servers or to redistribute to lists, requires prior specific ibility in tradeoff between recommendation effectiveness and
permission and/or a fee. ACM GIS ’10 , November 2-5, 2010. San Jose, computational overhead.
CA, USA. (c) 2010 ACM ISBN 978-1-4503-0428-3/10/11...$10.00.
.

458
 Mean Common location ratio (%)
100 3 sistent with our life experience, i.e., friends share much more
Cumulative Percentage (%)

2.5
common interests than two arbitrary people do. Because the
95 basic idea behind some recommendation techniques such as
2
collaborative filtering is to make use of common interests
90 1.5 between similar users to predict missing ratings, we believe
1
friends in location-based social networks may play a positive
85 role in collaborative recommendation.
Friends 0.5 Besides the difference in common location ratios between
Non−friends
80 0 friends and non-friends, nevertheless, Figure 1(a) also shows
0 0.2 0.4 0.6 0.8 1 0 200 400 600 800 1000
Common location ratio Distance between friends (km) that about 96% of friends share less than 10% commonly vis-
(a) Friends vs. Non-friends (b) Local vs. Distant friends ited locations and about 87.7% of friends share nothing in
common. This reveals some important information — since
Figure 1: Spatio-Social analysis there is a great number of friends sharing nothing in com-
2. SPATIO-SOCIAL ANALYSIS mon, not all social friends will contribute to location recom-
Location-based social networking systems are different from mendation. Thus, we next investigate what kind of friends
conventional social networking systems in its geospatial em- may share more commonly visited locations than others. To
phasis. To identify unique social and spatial characteristics find the correlation between common location ratio and dis-
in such systems, we perform a spatio-social analysis upon tance of friend pairs, we group friends based on their dis-
the collected Foursquare data. tance in steps of 10 km, i.e., friends located in 0 ∼ 10 km
form group 1, those located in 10 ∼ 20 km form group 2, and
2.1 Data Collection so on. Figure 1(b) shows the mean common location ratio
Due to the lack of publicly available location-based so- corresponding to these groups. As shown, the mean com-
cial networking data for analysis and experimentation, we mon location ratio follows a decreasing trend as the distance
crawl live data from Foursquare, one of the most popular between friends increases. This verifies our expectation that
location-based social networking services. We aim the data nearby friends have a much higher probability to share com-
crawling task at collecting user and location data. We se- mon locations since it is easier for them to participate in
lect a well-connected user (who has hundreds of friends) as a activities at the same locations.
seed to start the crawling. When a user is visited, we exam- In summary, based on the above observations, a natural
ine his/her profiles to extract i) the address information; ii) hypothesis is that social activity (visiting locations) of a user
the list of friends; and iii) the locations where he/she is the in location-based social network is largely affected by geo-
mayor.3 Through a breath-fist traversal of the social net- graphical proximity.
work, we obtain the user dataset. Afterwards, by crawling
the locations collected in the user data collection process, 3. COLLABORATIVE LOCATION RECOM-
we extracts the location addresses and the list of visitors.
After aggregating the user and location data, we obtain a MENDATION
dataset of 58,659 users and 96,219 locations. Note that each In location-based social networks, users update their vis-
user and location in the dataset is associated with an address ited locations anytime and anywhere. To achieve highly ac-
which is converted into geographical point (i.e., latitude and curate location recommendation, it’s essential to realize the
longitude) via Google map service. service efficiently. As discussed earlier, through large-scale
matrix multiplications, many existing collaborative filtering
2.2 Data Analysis techniques require a full scan of all users and locations in the
Upon the collected data, we perform an analysis to better process of location recommendation for a given user. Hence,
understand how the users and locations in location-based scalability is a critical issue since large-scale matrix multi-
social networks are associated with each other. plication incurs tremendous computational overhead for col-
First, we would like to see whether socially connected users laborative recommendation [5, 6, 7].
(i.e., friends) on location-based social networks are different
from an arbitrary pair of users in terms of commonly visited 3.1 Friend-based Collaborative Filtering (FCF)
locations. To proceed with this analysis, we first define the According to our data analysis, we observe that social
common location ratio between a given pair of users ui and friends share more common locations than non-friends. Thus,
uj and denote it as α(ui , uj ). Let Li and Lj denote the sets an idea is to consider only friends when processing collab-
of locations visited by ui and uj , respectively. Then, the orative filtering for a targeted user, since non-friend users
common location ratio α(ui , uj ), measuring the degree of do not have much value for reference in recommendation.
|L ∩L | As such, we only need to compute the similarity weight be-
overlap in visited locations, is defined as α(ui , uj ) = |Lii ∪Ljj |
tween friends, instead of all users, and the given user. We
We use common location ratio to examine two different expect great savings in matrix computation because the ma-
sets of user pairs — one consists of friends and the other trix size is significantly reduced. There is a tradeoff in re-
non-friends. Figure 1(a) plots the cumulative percentage of lying only on friends in collaborative recommendation. On
these two types of user pairs corresponding to common loca- the one hand, since non-friends are not considered, much
tion ratios. As shown in the figure, the common location ra- noise is reduced and thus good for precision. On the other
tios between user pairs is generally very small. Nevertheless, hand, there are indeed some cases where non-friends share
friends obviously have a higher chance to share commonly common locations. Those persons also contribute to recom-
visited locations than non-friends. For example, as indicated mendation, especially when there are few similar users to the
in Figure 1(a), about 4% of friends have a common location targeted person. Eliminating these non-friends may hurt re-
ratio greater than 10%. We consider visited locations as call as a result, i.e., some potentially preferred locations are
an indicator for user interests. Thus, the common location not recommended due to the lack of non-friends with similar
ratio may represent the common location interests between location interests. We will study the impact on precision and
two users. Indeed, the finding shown in Figure 1(a) is con- recall later in the performance evaluation.
In FCF, only friends are used as references in collaborative
3
Foursquare does not show visited locations in user profiles. filtering. In other words, we only need to calculate the simi-

459
larity weight between friends, instead of every pair of users. Foursquare dataset and obtain α = 0.0414 and β = −0.508,
Notice that we do not need to introduce social friendship which will be used in experiments. Then, by utilizing y =
explicitly to adjust similarity weight as in SCF. Since only αxβ , we have the similarity weight between two friends ui
friends are included to calculate the similarity weight wi,k , and uk
the social friendship has already been taken into consider- y(x = d(ui , uk ), α, β)
ation implicitly. For simplicity, we adopt cosine similarity wi,k = ∑ (6)
uk ∈Ui y(x = d(ui , uk ), α, β)
measurement here. In the following, we redefine the rate
predication function to consider only friends. Let U and L where Ui is the friend set of ui .
denote the user set and the location set in a location-based In GM-FCF, instead of scanning all locations to calculate
social networking system. Besides, let Ui denote the friend the similarity weight between friends, we only access the lat-
set for a given user ui . We assume that the system keeps itude and longitude (a 2-dimension geo-point) for similarity
track of the rating a user ui ∈ U put on a visited location weight estimation. Thus, the computation cost for similarity
lj ∈ L and denote it as ri,j . These recorded user ratings weight calculation is estimated as 2 × |Ui |. The total com-
on locations are thus used to predict possible ratings of the putation cost is C(GM − F CF ) = 2 × |Ui | + m × |L|, where
user on unvisited locations. We denote this predication as m × |L| accounts for the cost of missing rating predication.
rbi,j and obtain this predicted rating of ui on lj as follows.
∑
uk ∈U ′ rk,j wi,k 4. EXPERIMENTS
rbi,j = ∑ i (1) In this section we evaluate performance of the proposed
uk ∈U ′ wi,k
i
FCF techniques and compare them against social collabo-
where Ui′ (⊆ Ui ) is the set of friends with top-m similarity rative filtering (SCF) and random walk with restart (RWR),
weight. Notice that the number of friends (|Ui |) is usually two state-of-the-art collaborative recommendation techniques.
much smaller than |U |, i.e.|Ui | ≪ |U |. We crawled the Foursquare website, one of the most repre-
In FCF, for a given user, only his friends are involved in sentative location-based social networks, for a month to col-
the computation of similarity weight and contribute to the lect a data set consisting of 58,659 users and 96,219 locations
missing rating prediction. Thus, we estimate the computa- in total. Due to the lack of location ratings in Foursquare,
tion cost for collaborative filtering as C(F CF ) = |Ui | × |L| + we use for each user/location pair a binary rating, where ”1”
m × |L| < C(CF ) because of |Ui | ≪ |U |. Furthermore, we means the user visited the location and ”0” otherwise. Also,
conclude that C(F CF ) < C(SCF ). to avoid sparsity problems, we only include users who have
visited more than 2 locations in our experimental dataset,
3.2 Geo-measured friend-based collaborative similar as in [3]. After preprocessing, we have a User-User
filtering (GM-FCF) (UU) matrix with density of 5.9 × 10−3 and a User-Location
According to the spatio-social analysis of Foursquare data, (UL) matrix with density of 2.2 × 10−3 . For each individual
we observe that nearby friends tend to share more commonly user in the dataset, we randomly remove 20% of all loca-
visited locations (see Figure 1(b)). Thus, instead of scanning tions that he/she has visited, and use location recommenda-
friends’ visited locations to calculate their similarity weights, tion algorithms to recover the missing user-location pairs we
an idea is to model the similarity weight between friends by remove.
their distance. Accordingly, we propose geo-measured friend-
based collaborative filtering (GM-FCF) which uses linear re- 4.1 Metrics
gression method upon power-law distribution of distances In location-based social networking systems where users
between friends to learn a friend similarity model. The are able to instantly share their visited locations, the perfor-
power-law distribution is formulated as y = αxβ , where x mance of provided recommendation services are required to
denotes the variable of distance between friends and y here be highly effective and efficient.
denotes the variable of common location ratio. Both y and
x are often transformed into “log-log” scale, where a linear 4.1.1 Effectiveness
model can fit as below. A location recommendation algorithm computes a ranking
score for each candidate location (i.e., one user has not vis-
log10 y = w0 + w1 log10 x (2)
ited) and returns the top-N highest ranked locations as rec-
The original power-law distribution can be recovered via ommendation to a targeted user. To evaluate the prediction
the following equation. accuracy, we are interested in how many locations previously
α = 10w0 β = w1 (3) removed in the preprocessing step re-appear in the recom-
Hence, we can simply apply a linear curve fitting method mended results. More specifically, we examine (1) the ratio
to realize regression as follows. More specifically, let y ′ = of recovered locations to the N recommended locations, and
log10 y and x′ = log10 x. We shall fit data as follows (2) the ratio of recovered locations to the set of locations
deleted in preprocessing. The former is called precision@N
y ′ (x′ , W ) = w0 + w1 · x′ (4) (P (N )) while the latter is called recall@N (R(N )), collec-
where w0 and w1 are the linear coefficients, collectively de- tively denoted as P @N (where P represents ”Performance”).
noted by W . In order to avoid over-fitting when we approach Moreover, we take another further step to consider the pre-
the weight coefficients by least square error method, we add cision and recall relative to random recommendations [8].
a penalty term (i.e., regularization term) to discourage the More specifically, the relative precision and recall are defined
coefficients from reaching large values as below. as follows.
1 ∑ ′ ′
N
λ P (N ) |L||U |
E(W ) = {y (xn , W ) − tn }2 + ||W ||2 (5) Pr (N ) = = P (N ) × (7)
2 n=1 2 Prand (N ) |D|
where N presents the cardinality of input dataset, tn is the
R(N ) |L|
ground truth corresponding to x′n , and λ is the regularization Rr (N ) = = R(N ) × (8)
term. Rrand (N ) N
As to be discussed further later in performance evaluation, where |D| is the total number of deleted locations among all
we experimentally apply the above linear regression upon the users.

460
4.1.2 Efficiency 250
1E+12
Collaborative filtering consists of two major parts, simi- 200
larity calculation and rating predication, both of which es-

Computation Cost
P@5 Test
sentially incur matrix multiplication. More specifically, the 150 1E+8

cosine similarity between users can be projected as multipli-

→
− 100 CF
cation of a |L|-dimension vector Vi , whose values are either SCF 1E+4
RWR
0 or 1, indicating whether ui visited the location, and a 50
−
→ FCF
location-user matrix M|L|×|U | . The result is a vector Vi′ of 0
GM−FCF
1E+0
length |U | which includes all similarity between any user uk Precision Recall CF SCF RWR FCF GM−FCF

and the given targeted user ui . For rating predication, com- (a) Effectiveness (b) Efficiency - log scale
−→
putation is a multiplication between Vi′ and a user-location Figure 2: Performance comparison among CF, SCF,
matrix M|U |×|L| , and the result is a vector of predicated rat- RWR, FCF and GM-FCF
ings for the targeted user ui to all locations in L. As for
RWR, the main computation is about the “random walk”, Also in Figure 2, we evaluate the performance of GM-FCF.
which can be treated as rating predication [2, 3]. Each itera- As shown, the effectiveness of GM-FCF is competitive to
tion of random walk is a rating predication based on current FCF, while shows great advantages in efficiency. To sum up,
status vector and the transitive matrix. Different from col- the GM-FCF location recommendation techniques provide
laborative filtering, there are multiple iterations (I) for RWR flexible tradeoff between recommendation effectiveness and
till the result converges. Let Ci (·) denote the computation computational overhead.
cost incurred for user u∑i , then we have the average compu- 5. CONCLUSIONS
u ∈U Ci (·)
i A
tation cost as C(·) = |UA |
where UA denotes the In this paper, we study the research issues in location rec-
set of targeted users. We compare the efficiency by their ommendation services for location-based social networking
computation costs summarized below. systems. Through the spatio-social analysis of Foursquare
dataset, we observe that there exist strong social and geospa-
C(CF ) = |U | × |L| + m × |L| tial ties among users and their visited locations in the sys-
∑|UA | tem. In light of friends displaying similar behavior, we de-
i=1 |Ui |
C(F CF ) = × |L| + m × |L| velop friend-based collaborative filtering (FCF) approach for
|UA | location recommendations based on collaborative filtering
C(GM-FCF ) = 2 × |L| + ∑m × |L| of locations among social friends. Moreover, we propose a
|UA |
i=1 Ui variant of the FCF technique, namely, GM-FCF, based on
C(SCF ) = |U | × |L| + + m × |L|
|UA | heuristics derived from observed geospatial characteristics
in the Foursquare dataset. Finally, we validate the proposed
C(RWR) = |I| × (|U | + |L|)2
ideas and evaluate the FCF family of techniques via compre-
where Ui denotes ui ’s friend set. hensive experimentation. The evaluation results show that
the family of FCF techniques holds comparable recommen-
4.2 Experiments and Results dation effectiveness against the state-of-the-art recommen-
Here we compare the overall performance of CF, SCF, dation algorithms, while incurring significantly lower com-
FCF, GM-FCF and RWR4 . Figure 2(a) plots both relative putational overhead.
precision and recall for P@5. As shown, social friendship is
beneficial for location recommendation in social networks, 6. REFERENCES
since all algorithms that take social relation into account [1] J. Golbeck. Tutorial on using social trust for
outperform CF in terms of precision. However, in contrast recommender systems. In RecSys, pages 425–426, 2009.
to the significant improvement reported in [3], the social fac- [2] M. Jamali and M. Ester. TrustWalker: a random walk
tor only brings minor improvement over the CF algorithm. model for combining trust-based and item-based
As for the recall, SCF and RWR outperforms CF. FCF con- recommendation. In KDD, pages 397–406, 2009.
siders only friends in its recommendation, suffering missing
[3] I. Konstas, V. Stathopoulos, and J. M. Jose. On social
knowledge of non-friend users and thus hurting its recall a
networks and collaborative recommendation. In SIGIR,
little bit. However, the differences in recall amongst all com-
pages 195–202, 2009.
pared algorithms are insignificant. The experimental result
shows that the proposed FCF technique is very competi- [4] H. Ma, H. Yang, M. R. Lyu, and I. King. Sorec: social
tive in comparison with other collaborative recommendation recommendation using probabilistic matrix
techniques. factorization. In CIKM, pages 931–940, 2008.
On the other hand, the strength of FCF lies in its com- [5] G. Takács, I. Pilászy, B. Németh, and D. Tikk. Scalable
putational efficiency which is a mandate for on-line location collaborative filtering approaches for large recommender
recommendation. Figure 2(b) shows the computational cost systems. Journal of Machine Learning Research,
(in log scale) among the compared techniques. As shown, 10:623–656, 2009.
FCF significantly outperforms all other techniques in sev- [6] H. Tong, C. Faloutsos, and J.-Y. Pan. Fast random
eral order of magnitude. In summary, FCF prevails because walk with restart and its applications. In ICDM, pages
it only considers friends (a small number compared with the 613–622, 2006.
whole user set) when processing location recommendation [7] K. Yu, S. Zhu, J. D. Lafferty, and Y. Gong. Fast
for a given user, leading to a much lower computation over- nonparametric matrix factorization for large-scale
head. On the other hand, the effectiveness of FCF remains collaborative filtering. In SIGIR, pages 211–218, 2009.
competitive because nearby friends provide a high-quality [8] T. Zhou, Z. Kuscsik, J.-G. Liu, M. Medo, J. R.
pool of references for location recommendations. Wakeling, and Y.-C. Zhang. Solving the apparent
4 diversity-accuracy dilemma of recommender systems.
With extra experiments not shown due to space constraint, PNAS, 2010.
the probability of ”restart” for RWR is set to 0.9 for RWR
to achieve optimal performance.

461