Context-Aware Friend Recommendation for Location-Based Social Networks
Context-Aware Friend Recommendation
for Location Based Social Networks using
Random Walk
Hakan BAGCI and Pinar KARAGOZ
Department of Computer Engineering
METU, Ankara, Turkey
1
11 April, 2016
Outline
•
Introduction
•
LBSNs and Recommendation
•
LBSN Model
•
Problem Definition
•
Proposed Work
•
RWCFR
•
Evaluation
•
Methodology
•
RWCFR Experiments
•
Conclusion
2
Location Based Social Networks
•
A Location-Based Social
Network (LBSN) enables
users to add their
location information to
the social network,
hence they can share
location-embedded
information with other
users.
3
4
Recommendation Systems
5
LBSN Model
•
Problem Definition
•
Let graph
G
be an instance of the LBSN model.
•
Given
G
and user’s current location, for each user
u
in
U
, we aim to
predict the potential friends of the users.
•
Potential friends list is an ordered list of elements from
U
with size
N
,
which is the desired number of recommendations.
•
The goal is to generate potential friend list with highest accuracy, in
other words, with minimal errors relative to user's future friends.
6
7
Proposed Work
•
We propose a random walk based context-aware
friend recommendation algorithm for LBSNs.
•
RWCFR
provides friend recommendations to users
based on LBSN check-in data.
•
The data is modeled using an undirected unweighted
graph.
•
Random walk
is operated on this graph to estimate
the possibility of users to be friends.
•
RWCFR is a
context-aware
algorithm and considers
personal
,
spatial
and
social
context of users.
8
Recommendation Algorithm Phases
Random Walk
•
In order to make friend recommendations to users, we employ a
random walk with restart on the underlying graph of the LBSN.
•
The random walk is not performed on the entire graph representing
the whole LBSN.
•
A subgraph is extracted from the entire graph for each user according
to current context (e.g. Current location ) of the user.
•
After the subgraph is constructed, the random walk starts from the
current user’s node and continues until reaching a steady-state.
9
Random Walk
•
There is a constant random probability of jumping back to starting
node in every transition. Therefore, the random walk does not move
out of the context of the current user.
•
After the random walk converges to a steady-state, the steady-state
probabilities of user nodes are ranked.
•
The top-N friend recommendations are returned to the user.
10
RWCFR – Subgraph Construction
•
Friends of friends (social context)
•
Users that visited locations that the current user previously visited
(social spatial context)
•
Previously visited locations of user in vicinity (personal spatial context)
•
Friends and their previously visited locations in vicinity (social spatial
context)
•
Experts and their previously visited popular locations in vicinity (social
spatial context)
11
RWCFR - Expert Identification
•
In order to obtain local experts and popular locations, we employ a HITS-
based algorithm in which locations are authority and users are hub nodes.
•
Each user’s hub score denotes the location knowledge of that user in
recommendation area.
•
Similarly, authority score of a location represents the popularity of that
location in this area.
•
According to HITS, people who visit many high quality locations in a region
have rich knowledge about the region. Similarly, if a location is visited by
many experts, it is more likely to be a quality location.
12
RWCFR in Action
Location_2
Location_1
Expert_2
Expert_1
Friend_5
User_1
Location_3
Location_4
Location_5
PopularLoc_1
PopularLoc_2
Friend_1
Friend_2
Friend_7
Friend_3
Friend_4
Friend_6
13
Evaluation - Datasets
14
Evaluation Methodology
•
We know the current location of the user in real life.
•
However, in order to employ these datasets in our experiments, we
need to determine the recommendation points for each user.
•
In order to obtain these points, we employ clustering.
•
We cluster each user's check-in data, and resultant clusters' centers
are employed as current locations of the users in corresponding runs
of the algorithm.
15
Evaluation Methodology
•
RWCFR tries to predict the potential friends of the users.
•
Therefore, we need to partition each user's check-in history and
friendship data into two, training and test datasets.
•
RWCFR algorithm operates on training datasets and produces the friend
recommendation results for each user.
•
These results are validated using the corresponding test datasets of the
users.
•
This validation is performed using two well-known metrics,
precision
and
recall
.
•
We also employ
f-measure
to evaluate precision and recall together.
16
Evaluation Metrics
17
RWCFR – Algorithms to Compare
•
Popularity-Based Friend Recommendation (PBFR)
:
•
Recommends the users that have check-ins in recommendation region and
have the highest number of friends
•
Friend-Based Friend Recommendation (FBFR):
•
Recommends the second degree friends (i.e. friends of friends) sorted by the
number of friends
•
Expert-Based Friend Recommendation (EBFR):
•
Recommends the friends of local experts that have the highest number of
friends
18
Brightkite Results
19
Brightkite Results
20
Brightkite Results
21
Gowalla Results
22
Gowalla Results
23
Gowalla Results
24
Foursquare Results
25
Foursquare Results
26
Foursquare Results
27
RWCFR - Evaluation
•
The results clearly indicate that RWCFR outperforms FBFR, EBFR and
PBFR considering precision, recall and f-measure metrics.
•
RWCFR is a multi-criteria algorithm and it considers popularity,
friendships and local experts together.
•
Our LBSN model fuses these data seamlessly.
•
Moreover, RWCFR employs user’s location history.
•
On the other hand, other algorithms consider friendships, expert
users and popularity disjointly and do not provide a data fusion
framework.
28
Conclusion
•
We propose a friend recommendation algorithm
•
RWCFR – Friend Recommendation
•
We compare the accuracy of RWCFR with popularity-based, friend-
based, and expert-based baselines.
•
Our proposed friend recommendation algorithm outperforms all the
baselines.
29
30
This study presents a context-aware friend recommendation algorithm using random walk in Location-Based Social Networks (LBSNs). The proposed algorithm considers personal, spatial, and social context to provide accurate friend recommendations based on LBSN check-in data.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Context-Aware Friend Recommendation for Location Based Social Networks using Random Walk Hakan BAGCI and Pinar KARAGOZ Department of Computer Engineering METU, Ankara, Turkey 11 April, 2016 1
Outline Introduction LBSNs and Recommendation LBSN Model Problem Definition Proposed Work RWCFR Evaluation Methodology RWCFR Experiments Conclusion 2
Location Based Social Networks A Location-Based Social Network (LBSN) enables users to add their location information to the social network, hence they can share location-embedded information with other users. 3
Problem Definition Let graph G be an instance of the LBSN model. Given Gand user s current location, for each user u in U, we aim to predict the potential friends of the users. Potential friends list is an ordered list of elements from U with size N, which is the desired number of recommendations. The goal is to generate potential friend list with highest accuracy, in other words, with minimal errors relative to user's future friends. 6
Proposed Work We propose a random walk based context-aware friend recommendation algorithm for LBSNs. RWCFR provides friend recommendations to users based on LBSN check-in data. The data is modeled using an undirected unweighted graph. Random walk is operated on this graph to estimate the possibility of users to be friends. RWCFR is a context-aware algorithm and considers personal, spatial and social context of users. 7
Random Walk In order to make friend recommendations to users, we employ a random walk with restart on the underlying graph of the LBSN. The random walk is not performed on the entire graph representing the whole LBSN. A subgraph is extracted from the entire graph for each user according to current context (e.g. Current location ) of the user. After the subgraph is constructed, the random walk starts from the current user s node and continues until reaching a steady-state. 9
Random Walk There is a constant random probability of jumping back to starting node in every transition. Therefore, the random walk does not move out of the context of the current user. After the random walk converges to a steady-state, the steady-state probabilities of user nodes are ranked. The top-N friend recommendations are returned to the user. 10
RWCFR Subgraph Construction Friends of friends (social context) Users that visited locations that the current user previously visited (social spatial context) Previously visited locations of user in vicinity (personal spatial context) Friends and their previously visited locations in vicinity (social spatial context) Experts and their previously visited popular locations in vicinity (social spatial context) 11
RWCFR - Expert Identification In order to obtain local experts and popular locations, we employ a HITS- based algorithm in which locations are authority and users are hub nodes. Each user s hub score denotes the location knowledge of that user in recommendation area. Similarly, authority score of a location represents the popularity of that location in this area. According to HITS, people who visit many high quality locations in a region have rich knowledge about the region. Similarly, if a location is visited by many experts, it is more likely to be a quality location. 12
RWCFR in Action Location_2 Location_1 PopularLoc_1 Friend Visit Count Friend_6 Expert_2 Friend_5 65 Expert_1 PopularLoc_2 Friend_7 51 Friend_1 Location_5 Friend_4 47 User_1 Friend_6 45 Friend_5 Friend_7 Location_3 Friend_2 Location_4 Friend_3 Friend_4 13
Evaluation - Datasets Brighkite Gowalla Foursquare Users 6013 9768 4906 Locations 42494 55181 28095 Activities - - 331 Friendships 27330 44300 26522 Total Check-ins 252200 262004 451263 Check-ins per User 41.94 26.82 91.98 Friends per User 4.55 4.54 5.4 14
Evaluation Methodology We know the current location of the user in real life. However, in order to employ these datasets in our experiments, we need to determine the recommendation points for each user. In order to obtain these points, we employ clustering. We cluster each user's check-in data, and resultant clusters' centers are employed as current locations of the users in corresponding runs of the algorithm. 15
Evaluation Methodology RWCFR tries to predict the potential friends of the users. Therefore, we need to partition each user's check-in history and friendship data into two, training and test datasets. RWCFR algorithm operates on training datasets and produces the friend recommendation results for each user. These results are validated using the corresponding test datasets of the users. This validation is performed using two well-known metrics, precision and recall. We also employ f-measure to evaluate precision and recall together. 16
RWCFR Algorithms to Compare Popularity-Based Friend Recommendation (PBFR): Recommends the users that have check-ins in recommendation region and have the highest number of friends Friend-Based Friend Recommendation (FBFR): Recommends the second degree friends (i.e. friends of friends) sorted by the number of friends Expert-Based Friend Recommendation (EBFR): Recommends the friends of local experts that have the highest number of friends 18
Brightkite Results PBFR FBFR EBFR RWCFR 0.5 0.375 Precision 0.25 0.125 0. 1 2 3 4 5 Number of Recommendations 19
Brightkite Results PBFR FBFR EBFR RWCFR 0.25 0.2 0.15 Recall 0.1 0.05 0. 1 2 3 4 5 Number of Recommendations 20
Brightkite Results PBFR FBFR EBFR RWCFR 0.26 0.195 F-Measure 0.13 0.065 0. 1 2 3 4 5 Number of Recommendations 21
Gowalla Results PBFR FBFR EBFR RWCFR 0.5 0.4 0.3 Precision 0.2 0.1 0. 1 2 3 4 5 Number of Recommendations 22
Gowalla Results PBFR FBFR EBFR RWCFR 0.275 0.22 0.165 Recall 0.11 0.055 0. 1 2 3 4 5 Number of Recommendations 23
Gowalla Results PBFR FBFR EBFR RWCFR 0.325 0.26 F-Measure 0.195 0.13 0.065 0. 1 2 3 4 5 Number of Recommendations 24
Foursquare Results PBFR FBFR EBFR RWCFR 0.16 0.12 Precision 0.08 0.04 0. 1 2 3 4 5 Number of Recommendations 25
Foursquare Results PBFR FBFR EBFR RWCFR 0.1 0.075 Recall 0.05 0.025 0. 1 2 3 4 5 Number of Recommendations 26
Foursquare Results PBFR FBFR EBFR RWCFR 0.11 0.0825 F-Measure 0.055 0.0275 0. 1 2 3 4 5 Number of Recommendations 27
RWCFR - Evaluation The results clearly indicate that RWCFR outperforms FBFR, EBFR and PBFR considering precision, recall and f-measure metrics. RWCFR is a multi-criteria algorithm and it considers popularity, friendships and local experts together. Our LBSN model fuses these data seamlessly. Moreover, RWCFR employs user s location history. On the other hand, other algorithms consider friendships, expert users and popularity disjointly and do not provide a data fusion framework. 28
Conclusion We propose a friend recommendation algorithm RWCFR Friend Recommendation We compare the accuracy of RWCFR with popularity-based, friend- based, and expert-based baselines. Our proposed friend recommendation algorithm outperforms all the baselines. 29
