Recommender systems have changed the way people nd products, points of interest, services or even new friends. The technology behind recommender systems has evolved to provide user preferences and social in uences. In this paper, we present a rst approach to develop a recommendation engine based on social metrics applied to graphs that represent object's characteristics, user pro les and in uences obtained from social connections. It exploits graph centrality measures to elaborate personalized recommendations from the semantic knowledge represented in the graph. The graph model and selected graph algorithms for calculating graph centralities that are the core of the recommender system are presented. Semantic concepts such as semantic predominance and similarity measures are adapted to the graph model. Implementation challenges faced to solve performance issues are also discussed.
The widespread availability of products and services through web-based and mobile applications makes it di cult for end users to select the right item, according to their preferences. A recommender system must make use of di erent sources of information for providing users with suggestions of items that better correspond to their expectations. Those sources can include user preferences, item descriptions or social information.
Several approaches have been proposed to tackle the problem of selecting automatically the list of items that really contributes to satisfy the needs of end users. Approaches based on demographics or modeling user pro les are oriented to exploit user features and preferences for ltering available choices. The main challenge of this approach is to create the user pro le from scratch. Some systems invite users to select their preferences from a prede ned list of categories or allow the system to extract their pro les from other applications. Other systems register every user action to dynamically build models based upon the user's behavior. Some research works focus on collecting ratings made by users that have evaluated the product or service providing a rst-hand perception of the quality of the evaluated item. Other approaches have focused on describing the main features of every item and trying to match them with user requirements.
Modeling social networks using graphs has opened opportunities for exploring
new alternatives for implementing recommender systems. Social metrics, such as
ow centralities calculated on graph-based models provide interesting measures
to represent the semantic predominance of concepts featuring users' preferences
as well as item characteristics. A rst proof of concept was accomplished and
reported in [
The remainder of the paper is structured as follows: Section 2 presents related work. Then, Section 3 introduces the proposed graph-based recommendation model. Section 4 discusses selected graph algorithms used to calculate social metrics, particularly ow centralities. Next, Section 5 describes the framework developed in the prototype and the performance challenges we had to overcome. Finally, in Section 6 we report the results we have obtained thus far and discuss future work. 2
Traditionally, recommender systems are classi ed into the following categories:
demographic, content-based, collaborative ltering, social-based, context-aware
and hybrid approaches. However, the ever increasing amount of information
available in social media enables the development of knowledge-based
recommender systems [
In order to personalize recommendations, it is necessary to know information
about each user. User models are representations of users' needs, goals,
preferences, interests, and behaviors along with users' demographic characteristics [
Our work tries to balance between simple [
There is a wide range of recommendation algorithms and techniques. They vary
according to data availability, recommender ltering type as well as user and
object representation. Several methods have demonstrated to have an acceptable
performance such as: association rule learning [
In this work, we use graph metrics commonly used in social network
analysis [
Recommender systems are creating unique opportunities to assist people to nd
relevant information when browsing the web, and making meaningful choices
with the success of emerging Web 2.0, and various social network Websites. In
[
Wang et al. [
Ye et al. [
Similar to our work, Savage [
We can state that novel approaches rely mainly on the fusion of information inferred from a user's social network pro le and other data sources (e.g. mobile phone's sensors). In this sense, it is necessary to develop new strategies that produce recommendations from rich but still incomplete information. 3
Our recommendation engine is based on a graph representation of users and objects of interest linked through concepts (denoted as terms). Figure 1 shows the graph model where every node falls in one of three categories: User, Term or Object of Interest, and every edge represents the semantic relation between nodes: Predominance, Similarity or Friendship. Every Term node of the graph in Figure 1 acts as a semantic descriptor of both: Users and Objects of Interest. In other words, every user and every object are correspondingly described by the terms linked to them. In general, users are described by their tastes, preferences, and interest (user model) whereas objects are described by tags and keywords (object model). In this manner, when a term is shared between a user and an object, it shows the possibility that the user could be interested in that particular object, even though the object had never been seen or rated by user.
A graph-based representation allows us to apply graph algorithms (e.g. social metrics) to discover topological features, key relationships, and important (prestigious) nodes. Then, with these features we can make relevant recommendations to users, such as suggesting friends or places. Therefore, the foundation of our recommender system relies on a knowledge base constructed from both: a user model (see section 3.3) and an object model (see section 3.4).
In order to construct the user and object models, we applied a linguistic analysis over user and object text descriptions. Basically, we conducted preprocessing (removal of stopwords and selection of most descriptive words) and statistical linguistic analysis (using weighting schemes: tf-idf and okapi BM25) to de ne a bond between text descriptions and semantic relations represented in the graph (see section 3.2). It is possible to obtain user and object descriptions from social networks (Facebook, Foursquare, Twitter), web pages (Wikipedia, web search results, etc.), human experts contributions or other textual resources. 3.1
Formally, we de ne a weighted graph G = (V; E; fE ) where V = fv1; : : : ; vng is a set of vertices vertex (nodes), E = fe1; : : : ; eng ffx; yg j x; y 2 V g is a set of edges, and fE : E ! R the function on weights for every edge. In our recommender system V = U [ T [ O where U is the set of users, T is the set of terms, and O is the set of objects of interest. E = P [ S [ F where P is the set of predominance edges, S the set of similarity edges, and F is the set of friendship edges. Function fE is adapted according to each type of edge. For instance, we can obtain the sub-graph of users as GU = (U; F; fF ) (see User layer in Figure 1), the sub-graph of objects as GO = (O; S; fS ) (see Objects of Interest layer in Figure 1), and the sub-graph of user and object pro les as GU[T [O = (U [ T [ O; P; fP ). 3.2
In order to build the semantic relations of the graph, it is necessary to obtain text descriptions of users and objects. As a result, we have two collections: the users text collection (UTC) and the objects text collection (OTC), where each text description is considered a document D in a vector space model.
We de ne three types of semantic relations (edges of the graph): predominance, similarity, and friendship. Each semantic relation links di erent types of nodes and has a di erent weighting function. Predominance is the edge between a user or an object and a term, similarity is the edge between two objects and friendship is the edge between two users.
Predominance is the semantic relation between a term and a user or an object.
A term acts as a descriptor of users and objects. We de ne a weighting function
over the edge of predominance based on linguistic analysis. We apply Okapi
BM25 ranking function [
In Equation 1, pred is the predominance of the term T in document D, Idoc is the number of indexed documents (size of collection), Tdoc is the number of documents containing term T , T F is the term frequency relative to document D, DL is the document length, avgDL is the average document length among the entire collection, K and B are free parameters (usually K = 1:2 and B = 0:75).
Idoc + 0:5 Idoc + 0:5
T F + K
T F ((1 (K + 1) B) + B avDgDLL ) ! (1) (2) (3)
Similarity is the semantic relation between two objects. This measure indicates the degree of a nity between objects. We apply the cosine similarity measure (Equation 2) to obtain this value. The Similarity is calculated after the predominance, since it relies on shared terms. Then, every object is a vector of predominances as shown below Equation 2.
Similarity(A;B) = cos =
A B kAk kBk ObjectA = pred(A;T1); pred(A;T2); ObjectB = pred(B;T1); pred(B;T2) ; pred(A;Tn) ; pred(B;Tn)
In Equation 2, the similarity between object A and object B is determined by the weights of the terms they have in common. In this manner, a high similarity value indicates a higher semantic correspondence between objects.
Friendship is the semantic relation between two users. This measure indicates the degree of a nity between two users. Our current model does not distinguish between close friends, friends or acquaintances. Therefore, the users' sub-graph is only a friend-of-a-friend (FOAF) node-link type. 3.3
As part of the graph-based representation, users are de ned as sub-graphs. A user model is composed of two sub-graphs: user pro le Gu = (u; P; fP ) and user FOAF network GU = (U; F; fF ). Figure 2A shows the user pro le network and 2B the user FOAF network. In the user pro le sub-graph, each user is linked to a set of terms that indicate tastes, preferences and interests. Tastes are general inclinations of user towards some entities and they are generally expressed with actions such as likes (e.g. Foursquare, check-ins and Facebook likes football, beer, steak, co ee, etc ). Preferences are user inclinations towards taste features. Preferences are more ne grained than tastes and are usually expressed in users' reviews and ratings (e.g. starred reviews: I like the double espresso, I don't like diet soda). Interests are de ned as contextual user inclinations or intentions (e.g. I want to try Chinese food, I'm going to watch minions movie ). fP = 8 pred(U;T ) < 1 : #stars
Case A Case B
Case C 2 13
Our scheme to weight edges within a user pro le is indicated in Equation 3. Case A occurs when only text descriptions are used; this means that terms are weighted according to the Okapi measure (pred, as shown in Equation 1). Case B occurs when explicit likes are found in Foursquare or Facebook. Case C occurs when terms extracted from starred reviews are used to describe a user. In addition to Equation 3, we use a threshold value to limit the number of terms connected with a given user. In fact, we use the rst quartile as threshold value. An example of user pro le is shown in Figure 2A, where, it is possible to notice that a user likes football, rock and co ee, and is likely to be student. In user friendship networks, as mentioned earlier, there are no di erences among friendship types. Then, in FOAF network all weights are equal to 1 (fF = 1). A user FOAF network is shown in Figure 2B. 3.4
Objects of interest are sets of items that can be of potential interest to a user. Depending upon the application, objects of interest can be of di erent grain size. For instance, they can be coarse-grained as a point of interest (POI) or ne-grained as items inside places. An object is described by the category to which it belongs (e.g. dog is an animal). Also, it is described by tags designed by users or keywords found in object's description. The object model is consists of two sub-graphs: object pro le Go = (o; P; fP ) and object similarity sub-graph GO = (O; S; fS ). Object pro le was built with data gathered from Foursquare, Wikipedia and results from web searches. The weights of edges that link objects and terms were calculated using the predominance formula shown in Equation 1. This means that the weight function on edges is fP = pred(O;T ). 3.5
In order to apply social metrics (centrality measures) and relate them to pertinent recommendations, we de ned two networks from user perspective: a user global network (U GNu) and a user local network (U LNu). User global network is the whole graph (all nodes: users U , terms T and objects O and all edges: similarities S, predominances P and friendships F ) centered in current user. Therefore, U GNu = (U [ T [ O; S [ P [ F ) (see Figure 1). Whereas user local network is the sub-graph de ned by current user node u, term nodes adjacent to user Tu and object nodes adjacent to terms node OT linked trough predominance edges from user Pu and from objects PO. Hence, U LNu = (u [ Tu [ OT ; Pu [ PO) (see Figure 3). It is important to highlight the di erence between user global and local networks, since it will lead to di erent semantics interpretations when calculating centrality measures over them. 4
Centrality Measures and Recommender Engine Centrality measures have been used extensively in the past to exploit networks and discover the most relevant nodes in a graph. In social network analysis (SNA) graph centralities are used to identify the most relevant persons, communities and even detect strange behaviors in the network. However, given the takeo of social networks, people have increased their interaction not only to meet people and friends but to search about things they like, give their impressions, and reach points of interest and objects of interest. These spatio-temporal interactions can also be represented in a graph, thus, an accurate user pro ling representation can give us a great deal of insight about the user behavior. Because of these approaches in exploiting graph measures we have explored the use of centralities to exploit the topological structure of our user global network and ow centrality to get the most of our weighted global and local networks in terms of a recommender engine. 4.1
Centrality in graphs is widely used to measure the importance of a node in a
graph, especially in SNA [
Fig. 3. User Local Network
ities to measure the relevance of people in the social network. Some centrality
measures like closeness and betweenness are based on the calculation of the
shortest distance to reach all other nodes in the graph. Our algorithms to
calculate centralities are applied to the network of persons so we can infer the most
popular nodes (degree), the capacity of a node to reach any other in the network
(closeness), and to identify the leaders interconnected within a neighborhood
in the graph (betweenness) [
We are using ow centralities [
Flow Betweenness In SNA betweenness is one of the most common referenced
centralities. Flow betweenness (see Equation4) is de ned in [
Fb(i) =
Pn j<k mjk(xi) Pn j<k mjk Flow Closeness Closeness is just a measure of distance and is de ned as the inverse of the average distance to other vertices. A node with high ow closeness centrality has a fast communication within all the nodes in the graph. In equation 5, ow closeness is de ned as the inverse sum of the max ow to every other resource. In our recommender model, elements with high ow closeness should be recommended to the user as things that could be interesting, because those weighted elements are close to the user pro le (see Figure 5). (4) Eccentricity On the other hand, eccentricity is the maximum distance taking in consideration the weighted paths of the network. Eccentricity lets us nd the nodes that are far away from the most central node in the network. In equation 6 eccentricity is de ned as the maximum distance between pairs of nodes given their maximum ow in the network. In our recommender model, an item with As we have shown, our recommender model relies on the continuous computation of predominance and similarity between items in the graph. As the graph evolves from user interactions between the user and objects of interest, the recommendations get more accurate over time. However, in order to give recommendations, computation of centralities is required. As shown in Table 1, we can recommend similar items if the user is asking \What else?", then we can show him similar items to the recommended item. Flow betweenness is used to recommend things the user \can't miss" because of their relevance in the network. Flow closeness is used to recommend central items that could be things that the user \would like to discover", and eccentricity is used to show items to the user that are far away from the more central nodes in the network and could cause a \being di erent" impression.
We decided to implement the discussed model and graph measures in a weighted graph. We explored di erent graph databases and graph processing frameworks, to select the tools to build a graph processing framework that could give us the exibility to calculate those metrics with ease. We de ned an architecture (see Figure 7) based on the graph model discussed before. We named our graph processing framework \Census" which is built with Play framework1 and is intended to have multiple instances of Signal/Collect while processing our graph in Google Compute Engine2. Census uses Neo4j3 Graph database to store the graph, Neo4j give us the exibility to do queries over the computed network through custom plugins that serve queries through a REST API. Census process requests from Census Control which uses an orchestrator to administrate compute requests and instances of Census in the graph. With Census we explored a rst approach to implement the presented recommender model. The graph database was populated with nodes of persons and 1https://www.playframework.com/ 2https://cloud.google.com/compute/ 3http://neo4j.com/ Centro Expositor Africam Museo Revolucion Convento Sta. Monica Museo Amparo Museo Regional Puebla Fuerte Loreto Casa Alfen~ique Catedral Puebla Exconvento Calpan Convento San Gabriel Capilla Rosario Fuerte Guadalupe Plazuela Sapos Barrio Analco Paseo San Francisco Barrio Artista Estadio Cuauhtemoc Predominance 0.39 0.47 1.22 0.67 0.65 0.66 0.78 0.40 0.64 0.40 0.84 0.40 0.23 0.64 0.41 0.25 0.21 1.38 points of interest from the city of Puebla, Mexico, then we selected documents from the Web to create a pro le of the points of interest using our semantic approach described before. We created di erent users with their respective pro les setting them with random characteristics as weights in the relationships of the graph. We calculated similarities between those points of interest and the terms describing them. The result was a big graph database with approximately 3,000 nodes and 10,000 weighted relationships. Over the global network we calculated the graph measures to discover the relevant nodes in the graph. 5.3
After computing all the algorithms, we focused our attention on the local network of a user in particular. Results of centrality computation are presented in Table 2. We can notice that higher centrality measure values allow us to suggest the most relevant points of interest for this user. For example we can see that \Catedral Puebla" is an element with high betweenness which means that it is a relevant place in the city and that element should be recommended as \You can't miss". Another relevant element is the \Museo Revolucion" because it shows the highest ow closeness. In the case of ow eccentricity, we can see the elements that are far away from user preferences giving the opportunity to explore new things and be di erent.
We have presented a rst approach to a graph-based recommendation model that takes advantage of social metrics and recommends points of interest to citizens and/or visitors in a smart city. The proposed model expresses the semantics of relationships that exist between users and points of interest through terms that de ne a pro le for the items. This new approach, using particularly ow centralities, considers semantic predominance of terms for de ning and exploiting the relationships among user pro le preferences as well as the descriptive characteristics of points of interest. Recommendations can then be extracted based on the knowledge represented in the graph.
In order to validate the recommendation model, the recommendation engine was implemented and has shown that interesting recommendations could be suggested to users, considering not only their preferences, but also taking into account suggestions coming out from preferences of other members of the social network related to them by the friendship relationship. The graph-based recommendation model also proposes to explore points of interest that are very di erent to user preferences, inviting him to explore new points of interest in the city.
The implementation of the recommendation engine is a challenging task because of the data volume and the complexity of required calculations to evaluate ow centralities and semantic predominance. This challenge not only raised new questions but also opened interesting opportunities for dealing with performance issues. Preliminary results were presented, showing that the use of social metrics in any real recommendation system must include a specialized components for solving distributed and concurrent processing tasks. Even though nowadays there are advanced and e cient solutions for managing big data, adequate use of graph-based solutions for modeling social networks still remains as the core problem of a recommendation engine.
The framework presented in this paper was tested through a prototype that demonstrated the validity of our proposal. The recommendation engine is available through a REST APIs. These web services can be easily integrated into web or mobile apps. Application domains include intelligent tourism, (as in those described in this paper), as well as other areas of interest for citizens, such as administrative services in a Smart City. 7
The prototype will be extended and adapted to include speci c information on
the cities of Puebla in Mexico and Shanghai in China. Also, di erent aspects
could still be improved in the recommendation engine to contribute to enrich
the user experience in a smart city:
{ Incorporation of new semantic lters to propose lists of objects of interest;
proposing for instance only the points of interest in the proximity of the user's
location and considering the time when the user queries the recommendation
system.
{ In absence of explicit evaluation of user preferences, we will explore the
integration of the Sentiment Analysis component developed by our group [
Acknowledgments Special thanks to our colleagues C. Thovex, F. Aramburo, E. Castillo and D. Baez-Lopez for their signi cant contributions in this work. This project was partially supported by CONACYT-PROINNOVA No.198881, CONACYT-OSEO No.192321, and China's Foreign Experts Recruitment Program.