{'fraction_non_alphanumeric': 0.04341100261046118, 'fraction_numerical': 0.010151793483515421, 'mean_word_length': 4.162715248315448, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
B-Rank: A top N Recommendation Algorithm

In this paper B-Rank, an efficient ranking algorithm for recommender systems, is proposed. B-Rank is based on a random walk model on hypergraphs. Depending on the setup, B-Rank outperforms other state of the art algorithms in terms of precision, recall (19% - 50%), and inter list diversity (20% - 60%). B-Rank captures well the difference between popular and niche objects. The proposed algorithm produces very promising results for sparse and dense voting matrices. Furthermore, a recommendation list update algorithm is introduced,to cope with new votes. This technique significantly reduces computational complexity. The implementation of the algorithm is simple, since B-Rank needs no parameter tuning.


I. INTRODUCTION
One of the most amazing trends of today's globalized economy is peer production [1]. An unprecedented mass of unpaid workers is contributing to the growth of the World Wide Web: some build entire pages, some only drop casual comments, having no other reward than reputation [2]. Many successful web sites (e.g. Blogger and MySpace) are just platforms holding user-generated content. The information thus conveyed is particularly valuable because it contains personal opinions, with no specific corporate interest. It is, at the same time, very hard to go through it and judge its degree of reliability. If you want to use it, you need to filter this information, select what is relevant and aggregate it; you need to reduce the information overload [3].
As a matter of fact, opinion filtering has become rather common on the web. There exist search engines (e.g. Google news) that are able to extract news from journals, web sites (e.g. Digg) that harvest them from blogs, platforms (e.g. Epinions) that collect and aggregate votes on products. The basic version of these systems ranks the objects once for all, assuming they have an intrinsic value, independent of the personal taste of the demander [4]. They lack personalization [5], which constitutes the new frontier of online services.
Users need only browse the web in order to leave recorded traces, the eventual comments they drop add on to it. The more information you release, the better the service you receive. Personal information can, in fact, be exploited by recommender systems. The deal becomes, at the same time, beneficial to the community, as every piece of information can potentially improve the filtering procedures. Amazon.com, for instance, uses one's purchase history to provide individual suggestions. If you have bought a physics book, Amazon recommends you other physics books: this is called item-based or contentbased recommendation [6], [7]. Many different techniques have been developed in the past, including collaborative filtering methods [6], [8]- [10], content-based techniques [11]- [14], spectral based methods [15]- [17] and network based algorithms [18]- [20].
The evaluation of recommender systems is difficult [21]. There are several reasons for this: a) an algorithm may perform well on a particular data set but fails on others, b) in the past, evaluations focused on predictive accuracy of withheld ratings. Novelty and diversity were mostly ignored. These two factors play a pivotal role from a user point of view [22]. c) there is still no common framework in the community, defining a set of evaluation metrics. Such a framework would be particular useful, when comparing different techniques based on different data sets.
In this paper I propose B-Rank, a novel top N recommendation algorithm. B-Rank is based on a markov chain model [23] on hypergraphs [24]. The algorithm produces high precision and recall performance, maintaining high diversity between different recommendation lists at the same time. B-Rank is parameter free, which is very attractive from an implementation point of view. The performance is measured on two complementary data sets -movielens and jester. I compare B-Rank to ZLZ-II [20], [25], which is known to be superior to ordinary collaborative filtering methods in the investigated setup. GRank [20], a global ranking method, serves as a base benchmark.
II. METHODS User ratings are stored in a matrix V (O×U ). O denotes the number of objects and U is the number of users. v αi ∈ V corresponds to user i's rating to object α. Throughout this paper objects are labeled by Greek letters, whereas people are identified by Latin letters.

A. B-Rank
B-Rank is based on a random walk model with given initial conditions χ (i) , taking place on a hypergraph G 1 . A transition matrix P is associated with the hypergraph G. P αβ ∈ P denotes the transition probability from object α to object β. χ (i) is a normalized column vector, representing user i's preference, i.e the collection of already voted objects: χ (i)β = 1/ α sign(v αi ), where sign(x) = 1 if x > 0, and 0 otherwise. 1 A hypergraph G(V, E) is a finite set V of vertices together with a finite multiset E of hyperedges, which are arbitrary subsets of V . The incidence matrix H of a hypergraph G(V, E) with E = {e 1 , e 2 , · · · , em} and V = {v 1 , v 2 , · · · , vm} is the m × m matrix with h ij = 1 if v j ∈ e i and 0 otherwise.
In the hypergraph framework, each user i is modeled as a hyperedge and each object α is a hypergraph vertex. I define the transition matrix P of G like: Where k α = β =α i w i h αi h iβ , δ αβ is the Kronecker Delta and w i is the associated weight to hyperedge i.
In matrix formulation P reads as P = D −1 A with the symmetric adjacency matrix A = HW H T − T . D is a diagonal matrix containing the row sums of A, H is the incidence matrix and H T its transposed. W is the diagonal hyperedge weight matrix and T is the diagonal vertex degree matrix with T α = δ αβ i w i h iα h iβ . P is a row stochastic matrix with zero diagonal by construction.
B-Rank calculates user i's recommendation list f (i) as follows: In this paper I focus on the unweighted version of B-Rank. Namely, I set w i = 1 ∀i. This is done, to have straight forward comparisons to similar algorithms. The more complex case w i = 1∀i will be discussed in a follow up paper. Different aspects of the algorithm, computational issues and ranking stability questions are outlined in Sect.VI-A and Sect.VI-B respectively.

B. ZLZ-II
ZLZ-II [20], [25], is based on a lazy random walk process, taking place on a bipartite user-object graph. ZLZ-II uses a coarse grained version of the original voting matrix. a αi = 1 if v αi > v tr , and 0 else. v αi is the original vote and a αi is the transformed vote used in ZLZ-II. v tr is a threshold, to be selected. In general only "positive" votes are kept and the rest is discarded. Objects are assigned with a initial "resource" f . The given resources f are re-distributed according the linear transformation:f i = W f (i) . The resultingf i is user i's recommendation list. Like in B-Rank, this vector is sorted in descending order and the top N objects are presented as recommendations. W is a column stochastic matrix: k β is the number of votes given to object β and k j is the number of objects voted by user j. Note, that W 's diagonal is non-zero (lazy random walk). 2 #denotes the element-wise multiplication of two vectors.

C. Collaborative Filtering
Collaborative Filtering (CollabF) is perhaps the most popular recommendation method [26]. It is based on useruser linear correlations as a similarity measure.
where v jβ is the predicted vote, v i the average vote expressed by user i and S is the similarity matrix. In this paper I use a common correlation measure (pearson correlation [27]), to calculate S.
with S ij = 0 if users i and j haven't judged more than one item in common. User j's recommendation list is generated by stacking v jβ in a vector, sorting the elements in descending order and following the procedure described in Sect.II-A.

D. GRank
GRank is a global ranking scheme. Objects are ranked according their popularity (number of votes): k α . Unlike B-Rank, CollabF and ZLZ-II, GRank takes not into account users personality, since it generates the same recommendation list for every user participating in the system. The ranking list is given by sorting the objects according their popularity in descending order.

E. Data set
I used two data sets to test B-Rank. MovieLens (movielens.umn.edu), a web service from GroupLens (grouplens.org). Ratings are recorded on a five stars scale. The data set contains 1682 movies × 943 users. Only 6, 5% of possible votes are expressed. Jester (shadow.ieor.Berkeley.edu/humor), an online joke recommender system. The data set contains 73421 users × 100 jokes. In contrast to MovieLens, the data set from jester is dense: 75% of all votes are expressed. The rating scale are real numbers between −10 and 10.
Apart from the sparsity and the dimensional ratio (number of object vs. number of users), the most fundamental difference is the amount of a priori information accessible to users. People choose movies they want to see on the basis of many different information sources. They know actors, they read reviews, they ask friends for feedback etc. When users buy their tickets, they already did a preselection. On the other hand no pre-selection is possible with online jokes.
In this sense, the two data sets are complementary. Tests on diverse data sets are more meaningful in general [21]. For a discussion on different performance aspects, see [17].

F. Accuracy evaluation
To test the algorithms I divided the data in two disjoint sets, a training set S tr and a test set S ts . The training set is used to predict missing votes contained sin the test set.
I implemented four different evaluation metrics: recall, precision, F1 and diversity. The last is adopted from [20]. Recall for user i is defined as the number of recovered items d i in the top N places of the recommendation list, divided by the number of items D i in the test set for that user, thus P R i = d i (N )/D i . Averaging over all users gives the final score for recall P R. Precision measures the number of recovered items in the top N places divided by the length of the recommendation list N . For user i we have P P i = d i (N )/N . The overall precision P P is obtained by averaging over all P P i .
Increasing N (length of the recommendation list) usually increases recall and decreases precision at the same time. To balance out these effects, it is common to use the F1 metric, the geometrical mean of recall and precision: F 1 = (2 * P R * P P )/(P R + P P ).
To test the diversity between different recommendation lists I use h(N ), a metric proposed in [20]. Each experiment was done on 20 different instances -i.e. different splittings for training and test set with a fixed ratio (number of votes in the test set vs. number of votes in the training set). Final scores for all metrics were obtained by averaging over all instance results. All methods (B-Rank, ZLZ-II, GRank) were tested with the same instances, to make a fair comparison.

III. RESULTS
The main results are collected in Tables I-VIII. Bold figures indicate best result for a given evaluation metric. The length of the recommendation list N was set to N = 20 and N = 10 for all experiments. The performance improvement is measured relative to the ZLZII algorithm. There is a tendency toward higher improvements for shorter recommendation lists (N = 10). Best improvements are achieved for diversity between different recommendation lists. The best improvement, compared to ZLZ II, is achieved for inter list diversity. This result highlights the fact, that B-Rank can cope with users personality. From real world experiments we know, that higher diversity is positive correlated to user satisfaction in general [22]. However, user satisfaction is hard to measure in off-line experiments and user feedback is needed to draw robust conclusions.
An extension to the ZLZ II algorithm was proposed by [28], where the authors reached a comparable performance for diversity like B-Rank in the movielens dataset. Their method includes a tuning parameter λ. B-Rank in contrast is parameter free and therefore easier to implement and maintain.
Extensions to B-Rank may increase improvements again. One extension to the presented basic B-Rank algorithm is a non constant weight matrix W . This will be discussed in a follow up paper. Another extension is to take into account n-step propagation (indirect connections between two objects α and β). Tests for different n > 1 significantly dropped recall, precision and inter list diversity performance as well. One explanation for this behavior is a propagation reinforcement of popular items.
The basic version of B-Rank can be extended by introducing a user dependent parameter η(i), controlling the contribution of backward and forward propagation: . Such a parameter is a fine tuning of user i's preferences for popular and niche objects. Also a user independent, global η is possible. All these extensions increase computational compexity, since the system have to learn the 'correct' parameters.
Extensions and non trivial weight matrices W will be investigated and presented in a follow up paper.
V. SUMMARY In this paper I proposed B-Rank, a new top N recommendation algorithm. The algorithm is based on a random walk model on hypergraphs. B-Rank is easy to implement and needs no parameter tuning. The algorithm outperforms other state-of-the-art methods like ZLZII [25] and Collaborative Filtering in terms of accuracy and inter list diversity.
B-Rank is able to find interesting 'blockbusters' and niche objects as well. The algorithm is very promising for different applications, since it produces good results for sparse and dense voting matrices as well. Furthermore, I introduced a simple recommendation list update algorithm, which reduces computational complexity dramatically, Sect.VI-B.

A. General remarks on B-Rank
To highlight various aspects of B-Rank, I introduce a toy network Fig.(1). For simplicity all links between objects and users are equally weighted w i = 1 ∀i. First, I discuss some general aspects, second I show how all aspects are well captured by the B-Rank algorithm.
Case A: huge audience in common: Intuitively, two objects α and β are similar to each other, when they share many users -i.e. they have many hyperedges in common. Let's assume object α and object β share many users and user i voted for α but didn't vote for β yet. Then it's reasonable to recommend β to user i. Such a recommendation strategy clearly favors "blockbusters", objects rated by almost every user in the community (e.g objects 1 and 3 in the toy network Fig.(1).
Case B: exclusive audience: Look at object 5 in the toy network: this object is exclusively rated by user 4. Moreover, object 4 and object 5 share only user 4 and object 4 was not rated by many other users. In this sense, object 4 and 5 have an exclusive audience in common. It is reasonable to mark these objects as very similar and to recommend one of them to users who have not rated both.
Do the random walk: I define a path (α → β) as an ordered triple {α, i, β} with α = β (i.e object, user, object). The transition probability P αβ in Eq.(1) counts the number of paths (triples) starting at α and ending at β, divided by the number of all paths starting at α. Examples: for P 12 we count 6 paths starting at object 1. Two of them ending at object 2, thus P 12 = 1/3. For P 13 we count again 6 paths starting at 1, and three paths ending at object 3, thus P 13 = 1/2. Note, that P αβ = P βα in general, and P αα = 0 ∀α.
Put everything together: To demonstrate the effect of forward and backward propagation in B-Rank we use a basic preference vector χ = [0, 0, 0, 1, 0] T and the topology of the toy net in Fig.(1). For the forward propagation f F = P T χ we get: The obtained figures for objects α = 4 indicate the probability for a random walker starting at object 4 and landing at α = 4. Note, the scores are the same for objects 1, 3, 5. Object 2 obtains no score, because there is no simple path from object 4 to object 2. Object 4 obtains no score since the path {4, i, 4} is not a valid path per definition. For the backward propagation f B = P χ we get: The backward propagation vector contains the probabilities for a random walker starting at objects α = 4 and landing at object 4. We observe the same score for object 1 and object 3, but a much higher score for object 5, since the probability for a random walker starting at object 5 and ending at object 4 is much higher, then the probability reaching object 4 from another node.
The final score f is given by the element wise multiplication of f F #f B . Thus f = [1/18, 0, 1/18, 0, 1/3] T The final score for each object α = 4 has a simple interpretation: it is the probability for a random walker starting at object 4, visiting object α and come back to object 4.
The higher score of object 5 makes sense in the given setup, because objects 4 and 5 share an exclusive audience, furthermore object 4 is only 'loosely' connected to all other objects.
B-Rank captures well the possible configurations described in case A and B. If an object α has many links and shares most of them with another object β, then β is reached with higher probability then other objects, less connected (number of paths) to α. On the other hand, if an object α has many connections, but shares exclusively some hyperedges (users) with an object β, then f F may give low resource to β, but f B will give a high score to the same object β. In summary: B-Rank takes into account propagation of popular and niche objects as well.
Introducing hyperedge weights, described in Sec.(II-A), is a generalization of the procedure described in this appendix. It is not clear, what weight function is an appropriate choice. This issue will be investigated in an follow up paper.

B. Computational issues
I focus on two different computational aspects: 1) I show, how to make an efficient 'real-time' recommendation without performing the matrix-vector multiplication needed by B-Rank and 2) I give an update algorithm for the transition matrix P → P new , avoiding matrix-matrix multiplication to calculate P new . Note: the matrix-matrix multiplication is needed to calculate the adjacency matrix A for the hypergraph.
1) Offline-Online tasks in B-Rank: To calculate user i's recommendation list f (i) , one has to perform two matrix-vector multiplications -steps 1 and 2 described in Sec.(II-A) -and an element-wise multiplication of two vectors. We can reduce the effort to compute the matrixvector multiplications. The idea is simple: calculate object specific basis representations b F and b B for the forward and backward propagation vectors, independent of all users. The recommendation task (online) for a user i is then reduced to calculate a linear combination of the basis forward and backward propagation vectors. b F α = P T e α , b B α = P e α . e α ∈ R O is a natural basis vector, where the dimension O is given by the number of objects.
b) Online: The forward and backward propagation vectors for user i are then given by: With c α = χ (i)α . The final calculation of user i's ranking list f (i) is given by step 3, described in Sec.(II-A). Note: using this shortcut produces different figures in the recommendation lists, compared to the ones, generated by the procedure in Sec. (II-A). However, the ranking (ordered list) will be the same. The online part is easily done, since the calculation essentially reduces to calculate a linear combination of rows and columns from the transition matrix P .
2) Update algorithm: The main effort to calculate the transition matrix P consists of a matrix-matrix multiplication to compute the adjacency matrix A of the hypergraph. A naive way to maintain the system would be a recalculation of P → P new , every time a user rated an object. I give a simple update algorithm for P → P new . I write the transition matrix P like: a) Single vote manipulation: I further investigate the update algorithm in case of one additional vote in the incidence matrix H. To model a one vote change in H, I define the single-entry matrix J ij ∈ R n×m , which is zero everywhere except in the (i, j)th entry, which is 1. Assume a matrix A(n × m) and a matrix J ij (m × p), then AJ ij = [0 0 · · · A i · · · 0 0] is a n × p matrix with the i.th column of A in place of the j.th column. Conversely, assume A(n×m) and J ij (p×n). Then, J ij A is a p×m matrix, with the j.th row of A in the b) Many vote manipulation: The generalization of single vote manipulations is straightforward, since a many vote update is represented by a combination of single vote updates.