Most modern recommendation systems use the approach of collaborative ltering : users that are believed to behave alike are used to produce recommendations. In this work we describe an application (Liquid FM) taking a completely di erent approach. Liquid FM is a music recommendation system that makes the user responsible for the recommended items. Suggestions are the result of a voting scheme, employing the idea of viscous democracy [3]. Liquid FM can also be thought of as the rst testbed for this voting system. In this paper we outline the design and architecture of the application, both from the theoretical and from the implementation viewpoints.
Most modern recommendation systems use the approach of collaborative
ltering [
Viscous democracy is a kind of liquid democracy [
In this sense, liquid voting systems try to take the best from both worlds. Every
member's opinion, in a direct democracy, is directly relevant to a nal decision,
but the vote of each one can be (knowingly!) uninformed; instead, in a classical
representative system, elected representatives are encouraged to be informed on
the speci c decision they are making, but on the other hand many people feel that
their opinion on that matter is basically irrelevant. This phenomenon is called
political ine cacy by social scientists|see for example [
Viscous democracy was proposed by Boldi et al. in [
This framework can be used in a variety of settings. In our application, we show how it can be easily adapted to music recommendation. For a certain music genre, we ask users to express a short list of their favorite songs, or to delegate one of their Facebook friends they consider to be an expert on that genre. This builds a graph of delegations for each music genre. We wish to employ this data to create recommendations for each user.
In Section 2, we will give a panoramic overview of recommender systems, and of liquid democracy. Then, in Section 3 we will detail how we extract information from the delegation graph. In Section 4, we will describe how we have developed the system: how its algorithms were implemented, the architecture of its components, and the external resources we used; nally, in Section 5 we will sum up our work and present possible directions for future research. 2
Information overload, experienced everyday by internet users, has caused a growing research interest in recommendation systems|i.e., systems able to pro-actively suggest items of interest, in order to save users' time.
Recommender systems (RS) have been done in the past mainly with one of two
di erent approaches, known as content-based ltering (CBF) and collaborative
ltering (CF). Content-based ltering [
Collaborative ltering [
CF does not need any speci c knowledge about items: while CBF requires a
phase of feature representation that can be costly for some domains, CF does
not and can be applied without much e ort to movies, news stories, websites,
et cetera [
A well-known problem of CF is cold start [
We propose an application sharing traits with CF|we take a bipartite graph
of user ratings of items as input, and employ user ratings to produce
recommendations; however, we take in suggestions about the importance of trust in
recommendations and from the study of liquid and viscous democracy. In fact, [
The idea of propagating trust to predict ratings has been previosly analyzed
theoretically, with the help of simulations made on real data. In [
From now on, we will denote with dG(x; y) the distance from node x to node y in the graph G, and with oG(x) the outdegree of node x in G; we may omit reference to G if it is obvious from the context.
Let us de ne U as the set of users and S as the set of items|they will be songs in our application1. D = (U; AD), with AD U U , is the directed graph of delegations; an arc from user u to u0 means the former delegates the latter as an expert on the topic. V = (U; S; AV ), with AV U S, is the bipartite graph of votes, where an arc from u 2 U to s 2 S means that the user u recommends item s.
We are going to put some restrictions on these graphs: rst of all, we are going
to assume that there is an underlying, undirected friendship graph F = (U; EF ),
with EF U U , where an edge (u; u0) 2 EF expresses a personal acquaintance
of u and u0. We impose that AD EF : this permits us to ensure that the trust
expressed through a delegation is a result of personal knowledge, as suggested
in [
Further, we are going to impose that 8u 2 U , we have 0 oD(u) 1, meaning that a user can delegate only one person, and 0 oV (u) 3, meaning that every user can vote up to 3 items2. We are going to consider only nodes u 2 U having oD(u) > 0 _ oV (u) > 0. An example of such a setting is pictured in Figure 1. 1 As we will explain in Section 4, we are going to consider di erent sets of songs and votes, one for each music genre treated. For the rest of this section, we are going to consider the music genre as xed. 2 We will explain this assumption in Section 3.2.
Francis
David John Zorn, "Batman"
Miles Davis, "Pharaoh's Dance"
Hugo A voting system is a function vD : U ! R assigning a score to each user, depending on the delegation graph. Such a function will be the basic building block of our recommendations.
Usually, in liquid vote this function is just the size of the tree with root in u 2 U : lD(u) =
fu0 2 U jdD(u0; u) < 1g
This function is used, e.g., by the well-known LiquidFeedback3 platform. Nonetheless, it assumes that \trust" transferred from a to b is the same whether a delegated b directly, or whether they are connected by a long chain of delegations| and they may not even know each other.
Let us assume that we wish, instead, that the amount of trust passed on from a to b is greater if (a; b) 2 AD, and lesser if there are many steps connecting them. To do so, we introduce a damping factor 2 (0; 1], de ning how much of the voting power of a is transferred to b when a delegates b. Therefore, the scoring function characterizing viscous democracy will be: vD(u) = X
d(u0;u) u02U
Authors [
With approaching 0, instead, the voting power becomes nontransferable: all users become equal, regardless of the delegations they received; in other words,
(1) Lou Gustav Klaudia
Joe
Isaac
David the model becomes a direct democracy, without any proxy vote. These di erences are presented graphically in Figure 2, making use of the item-scoring function we will show in the next section. Having a score for each user, we can easily score each item s 2 S. Indeed, we can de ne a function r : S ! R as r(s) =
X u2Uj(u;s)2AV vD(u) (2)
This function will get us a score for an item proportional to the importance of who voted it, according to vD. The score is completely de ned by the graphs V and D. We can then proceed to rank each item with r, and present them to the users accordingly. As in many standard information retrieval tasks, a user looking for results (about a certain music genre, as we will explain in Section 4) will be presented with all possible items|all items in S|ranked from higher to lower r. Users of our application will be therefore more likely to listen to songs ranked higher in this list.
Let us call the in uence of u 2 U the di erence the votes of user u make in the nal rankings|that is, Ps2S r(s) rV nfug(s). Please note that, since we have not normalized r, users giving more votes have a larger in uence in the nal rankings, serving the purpose of encouraging them to give more recommendations. However, it also explains why we had to put a limit on oV (u): if we had not, a single user u could have an arbitrary in uence on the score r, resulting in the possibility of spam. To drop this constraint on oV , we could require a costly e ort from users to sustain a large number of votes|for example, a user could vote a song only if they have fully listened to it.
In the end, the in uence of a user on item scores is determined by the number of recommendations they give|limited, but under their control|and by the delegations they received|unlimited, but not under their direct control.
As mentioned before, an example of how r behaves is pictured in Figure 2. 3.3
The item-scoring function we presented gives the same ranks to whoever is their observer. This behavior is unusual in recommender systems, where the goal is to give the right recommendation to the right person. In our case, a user may be more interested in listening to what their delegate suggested, rather than other| possibly more popular|items. Looking at our example in Figure 2, Francis may be more interested in listening to \Pharoah's Dance", even if it is not globally highly-ranked, because it is the recommendation of his delegate David. Similarly, Hugo may be interested in it, because he has, in turn, delegated Francis.
This goal can be easily expressed as a personalized item-scoring function. Let us de ne a function p : S; U ! R as p(s; u) =
X u02Uj(u0;s)2AV d(u;u0) (3) (4)
Such a function permits the user u to get a positive score only for the items recommended by users belonging to the chain of delegations starting in u. For the purpose of maintaining this intention, but at the same time avoiding to completely discard all the items highly ranked by the original r, we can de ne a linear combination of the two functions, normalized to 1: c(s; u) =
p(s; u) max p(s0; u) s02S + (1 )
r(s) max r(s0) s02S where 2 [0; 1] regulates the amount of personalization of c.
An example is pictured in Figure 3. 3.4
In addition to the presented ways to compute recommendations, the setting here described also permits to compute other information that may be of interest to the users. Particularly, it allows them to know how authoritative (i.e., trustable) their taste is in a particular music genre. The function vD, in fact, can be normalized into a percentile-based scoring, obtaining an easy-to-read assessment in the form \u is better than vD(u) people out of 100" (for a speci c genre), with vD(u) = c c 100 jfu02UjvD(u0)<vD(u)gj . It can then be used to provide useful information from jUj two di erent perspectives: 1. Showing to the user a fair evaluation about which music genres they are believed to be more expert about. 2. Presenting to a user interested in learning more about a speci c genre which of their friends is considered an expert|making use of the direct knowledge graph de ned on page 3. Gustav Klaudia
Joe
Isaac
David We will now discuss how the presented techniques have been implemented in practice. The nal result is Liquid FM: a Facebook application that enable its users to vote one of their friends as an expert on a music genre, and (by means of the described formulas) recommends them some piece of music to listen to, by identifying the best experts.
Firstly, we will present a general overview of the architecture of Liquid FM, explaining the role of its main components; then, we will give a more detailed look at the implementations of the formulas presented in Section 3; nally, we will discuss the external components we employed.
Categories As anticipated in the previous section, we applied our scoring algorithms to 9 music genres, called categories from now on, and their set will be denoted as C. In this way, we will have di erent votes and di erent recommendations for each category. Such a behavior is closer to reality: an expert in HipHop is not assumed to be quali ed to give, say, classical music suggestions. However, it also permits to have di erent graphs for the same users|an interesting fact for future analysis.
The selected categories were Classical, Electronic, Folk, HipHop, Indie, Jazz, Metal, Pop, Rock. They were chosen by inspecting LastFM top 20 tags4 and discarding those not expressing a musical genre (such as \seen live") and sub-genres (having included Indie and Rock, we discarded \Indie Rock"). We decided to add Classical (only ranked 36th on Last Fm), since it is a di erent and interesting community, under-represented in services such as the one we referred to. 4.1
As pictured in Figure 4, Liquid FM features two main components:
Construction of web pages: voting forms, user feedback, and on-the-fly personalized recommendations User votes
Song ranks and scores
Computing global rankings
{ a Java part, with the role of analyzing the whole graphs and computing global scores through vD and r (equations 1 and 2): it is meant to be fast, and executed periodically; { a Python part, with the role of glueing the di erent parts together and providing all the other functions: from the construction of web pages to the implementation of personal scores (functions p and c, equations 3 and 4).
These two parts interact with each other through a shared database, that persistently stores every information. We chose MongoDB, an open-source documentoriented NoSQL database, for e ciency, scalability, and exibility. Furthermore, we do not often need complex operations, involving more than one collection, and we would like to control what is happening at application-level.
On this database, we have two main collections gathering user-submitted data: one for D and one for V . These collections are both represented in Figure 4 as \User votes". A document in the collection for D looks like this:
f c a t e g o r y : c , from : u , t o : u0 g While a document in the collection for V has this structure:
f c a t e g o r y : c , u s e r : u , a d v i c e : s g
The advice s is a dictionary containing author and title of the song, as well as a YouTube video id. In fact, we associate with each song selected by a user a YouTube video, in order to be able to play it as a recommendation. YouTube is in fact one of the largest and most used music streaming platforms, and it can be included in third-party services (with small limitations). A screenshot of the voting phase in displayed in Figure 5.
Please note that the structure of an advice, as well as the category c, is
wellincapsulated: therefore, the schemas of these collections can be easily extended in
the future in order to support di erent (i.e., not music-related) scopes.
f
f
g
The division of global and personalized recommendations into two separate
components originates from e ciency reasons. Having to compute and store all the
personalized scores for each user would be impracticable, as they would be jCj jSj jU j
scores. Therefore, they are computed with a lazy approach: when a user u asks
for her personal recommendations, we compute all of them on-the- y and cache
them. Global recommendations, instead, are the main result of the system, and
every user depends on them|even to see the personalized scores, since we use the
function c (equation 4). For this reason, we compute them periodically with a fast
Java component, and save them to a dedicated MongoDB collection.
Global recommendations in Java The global recommendation component was
carried out in Java, since for this task it is faster than Python and since e cient
open-source libraries to deal with graphs are available; in particular, we employed
extensively the WebGraph framework [
This component is run periodically. It takes as input the graphs D and V , memorized in their MongoDB collections, and it results in a new collection for each category, composed of documents of this form:
a d v i c e : s , rank : r(s) g and in another collection ranking users, where each document has this form: i d : u , category1 : f s c o r e : vD(u) , p e r c : vD(u) g , : : : c
We can schematize the process, for each category c, in these steps: Personalized on-the- y recommendations As discussed above, personalized recommendations are computed on-the- y by a Python component. Python was in fact chosen as the main language of the application, due to its versatility and its fast production times; also, we decided to use Flask5, an open-source web development micro-framework particularly suited for our task.
Personalized recommendations are computed only when users ask for them, since they require to see only a very small part of the graphs, and because storing all of them would be unfeasible. The score we will use to rank personalized recommendations is the function c(s; u) (eq. 4); in order to compute it we must, in the rst place, compute p (eq. 3).
To compute p(s; u) for all songs s 2 S and a xed user u we walk through the chain of delegations on graph D, starting from u. Since 8u oD(u) 1, this path on D is unique (although it may end in a cycle). Therefore, we simply proceed as follows (for a suitable stopping threshold ): 1. Let p be a map with 0 as default value for missing keys. 2. while t > and 9u0 s.t. (u; u0) 2 AD (a) u u0 s.t. (u; u0) 2 AD (b) For each s s.t. (u; s) 2 AV :
p[s] p[s] + t (c) t
t
Now we have all the ingredients for function c, and we can proceed to compute the ranking order according to it.
First of all, consider that the ranking order induced by c(s) is equivalent to c(s) = k p(s; u) + r(s) where k = (1 max r(s0) s02S ) max p(s0; u) s02S
Therefore, for each element s of the map p, we multiply its value by k and add the value of r(s). Then, we retrieve all the other items s s.t. r(s) min p[s0], and s0 insert them in the map p. Finally, we can build the iterator of personal recommendations by chaining two iterators: 1. the iterator of all elements in p, sorted by their values;
2. the iterator of all other elements s 2 S having r(s) < min p[s0], sorted by their s0 values; remember that they are already indexed in this order in the database.
The nal iterator can be implemented in a lazy fashion, allowing us to retrieve the elements of the second iterator only when necessary. The rst iterator, instead, will be computed eagerly upon its request, and then cached. To cache these (and other) values, we employed redis6, an open-source in-memory key-value cache. To conclude this section, we would like to brie y describe the main external software components we used in developing Liquid FM.
Facebook As mentioned earlier, Liquid FM is a Facebook application. The reason
for it is that we used the Facebook friendship graph as the graph F de ned on
page 3. In fact, Facebook is at the moment the largest existing social network (with
1.4 billion users), and it has been previously used as a good approximation of an
acquaintance graph [
In this work, we presented a Facebook application aimed at putting the viscous
democracy framework [
The discussed application is currently active on http://bit.ly/liquidfm, and we have so far collected some small datasets; currently, the delegation graphs consist of few tens of delegations, so it is impossible to draw any conclusion from
them. In order to be able to collect larger amount of information it is crucial that we nd a way to make the application viral : this is a matter of social engineering that needs to be taken into careful consideration.