{'fraction_non_alphanumeric': 0.031161836368299563, 'fraction_numerical': 0.009553731726083611, 'mean_word_length': 4.55250978996084, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Investigation on Social Network Recommender Systems and Collaborative Filtering Techniques

Nowadays, with the remarkable expansion of the information through the internet, users prefer to receive the exact information that they need through some suggestions from their friends or profiles to save their time and money. Recommend systems based on different algorithms as one of the basic ways to reach this goal through the internet have been proposed but each of them has their own advantages and disadvantages. In this study, we have selected and implemented two approaches which are Collaborative Filtering (CF) and Social Network Recommendations System (SNRS). Based on some limitations to finding a dataset which covers friendship, rating and item categories we generated it for 10 categories, 10 items, and 100 users and compared two approaches. We used Mean Absolute Error (MAE) and accuracy to compare the result of two mentioned approaches and found that the SNRS method as it is claimed to be improved version of CF works more efficiency.


I. INTRODUCTION
Finding relevant information has been a challenge for a long time. Based on this requirement, recommendation systems are becoming one of the most popular technique to encounter with this problem. Almost, all recommendation system try to make predictions about the preference of each user based on the preferences of a set of similar users through content-based filtering, collaborative filtering or combination of both. Collaborative filtering is the prevalent recommendation system which has been used to identify users that can be characterized as a similar according to the logged history of prior behaviors. Generally, a collaborative filtering algorithm use a collection of user profiles to identify interesting information, items, products, services or etc. for these users. A particular user achieves a recommendation based on the user profiles of other similar users. User profiles are made by asking users to rate items, items, products, services or etc. There are several applications for collaborative filtering in different domains such as trust and security [10,19,23,31], web services recommender systems [14,32], and context-aware recommenders [13,20]. In this paper, we have compared a traditional collaborative filtering with the improved version of probabilistic approach (which is known as Social Network-based Recommender System).
II. RELATED WORK Nowadays, recommender systems are becoming one of the approaches that help users to make decision in regards of what products to buy, which news to read and what movie to watch. These systems try to maintain the loyalty of users and increase sale from producer's point of view and on the other side save user's time and money through proposing the most matched recommendations to users. Generally, three categories for recommender systems can be enumerated which are collaborative filtering, content-based filtering and the hybrid version which is the combination of two mentioned categories. Social recommender systems which are known as improved version of collaborative filtering are based on social networks. Social networks are made of a finite group of users and their relationships (figure1) that they establish among them through the social links so one key insight is that social-based recommender systems should account for a number of dimensions within a user's social network, including social relationship strength, expertise, and user similarity. There are several techniques to extracting information from social graph network such as information retrieval [9] and knowledge extraction [4] that can be applicable in collaborative filtering. Additionally, combining summarization techniques [17] and data mining approaches [15] with collaborative filtering model is getting more attention these days to receive a better accuracy. Analyzing the data generated by users within social networks has several practical applications that can be used to develop recommendation systems [2].

III. COLLABORATIVE FILTERING
Collaborative Filtering is a technique used by many recommendation systems. We can define Collaborative filtering as a method of making automatic predictions (filtering) about the interests of a user by collecting preferences or taste information from many users (collaborating) [4]. Collaborative Filtering can be of three types 1) Memory Based Filtering: In this approach we use ratings of the users, directly to the rating of the active user (user for we are predicting the rating to recommend). In most of the cases we do not use all the users in prediction. Instead of that we use a set of nearest neighbors and that's why this algorithm is known as "User-Based Nearest Neighbor Algorithm".
2) Model Based Filtering: Here system does not use the user ratings directly. Instead of that they form a model using those rating values and use that to predict the rating for the active user. This model can be formed using Bayesian Networks, Clustering, Association Rule Mining or Latent Semantic. All of them try to get a model that reduces the data to compute for each recommendation. 3) Hybrid Filtering: Some applications use the previous two models together. This approach helps to overcome the short comings of both the algorithms. It improves the prediction performance. Importantly, it overcomes the CF problems such as sparsity and loss of information. However, they have increased complexity and are expensive to implement [5].

IV. PROBABILISTIC APPROACH
Probabilistic Approach is a relatively new technique. As described in the paper, to predict that a user will like/dislike a given item, there are 3 factors to be considered.
1) User Preference, which is the probability of the current user to give a given rating to any similar item as of target item.
2) Item Acceptance, which the probability of the current item to get a given rating by all the users under consideration.
3) Friend Inference, which is the probability of the friends of current user to give a given rating to any similar item as of target item.

V. REQUIREMENTS OF DATASET
Dataset needed for testing both of this algorithms needs lots more information than just social network and individual reviews. We tried many datasets namely yelp.com, facbook, movielens etc. But those datasets were not rich enough to test this algorithm. In the paper also they have made their own dataset with the help of information from yelp.com. The main requirements for the dataset were: a. It must show social relationship bonds between different individuals. b. It must show individual ratings given by individuals to different items. c. It must show the categories to which the different items belong to. In other words, it must show the different attributes each of the different item have. Since we cannot find a dataset good enough for this algorithm, we generated our own dataset.

VI. DATASET AND IT'S GENERATION
To generate the dataset, we used Microsoft Excel. The basic heuristic that we used is that a user will give more or less similar rating to a given item as his/her friends gave to that same item. We needed 3 tables/sheets to store the needed data.

1) Relationship Table
In this, we stored the relationship bonds between different individuals of a social network. We took 100 users, so this table has 100 x 100 entries. Lets assume R(x,y) represents the bond between 2 users x & y, then R(x,y) = {0,1,2,3,4,5} x,y ϵ Users R(x,y) = R(y,x) ,x≠y, x,y ϵ Users R(x,y) = undefined , x=y, x,y ϵ Users The value of R(x,y) lies between 0 to 5, where 0 indicates extreme dislike and 5 extreme indicates best friends x & y. We assigned random ratings from 0 to 5 to random pairs of friends in this sheet. Some pairs were not. rated at all, since it is not necessary that every individual knows every other individual in a social network.

2) Rating Table
In this, we stored the rating given by different individuals to different items. Part of this table was used as training dataset along with two of other tables and part of this table was used as testing dataset. In this we took 100 users & 10 items, so this table has 100 x 10 entries. Lets assume K(x,y) represents the rating given by user x to item y, then K(x,y) = {0,1,2,3,4,5} K(x,y) ≠ K(y,x) x ϵ Users, y ϵ Items The value of K(x,y) lies between 0 to 5, where 0 indicates extreme dislike and 5 extreme extreme likeness of a user x for a given item y. We generates this table manually by first taking some random individuals and putting random ratings for them against random items. Lets assume we put a random rating R from a user U to an item I. Now for all other users apart from this random ones, we calculates their ratings as average of what his/her friends gave to that item.
For example, User U2 has not been assigned any rating for given item I5, so we will find all friends of U2, who have given ratings to I5. Lets assume there are 3 friends of U2 namely U9, U17, U31 who have given rating R9, R17, R31 to item I5. So to calculate the rating that U2 will give to I5, we take the weighted average of the relationship between U2 & his friends & the ratings they gave to I5.

3) Attribute/Category Table
In this, we stored the attributes each item has. In other words, we stored the categories to which an item belongs to. Also an item can have more than 1 attributes or it can belong to more than 1 categories. Lets assume B(x,y) represents whether an item x belongs to category y or not, then B(x,y) ≠ B(y,x) x ϵ Items, y ϵ Categories B(x,y) = {0,1} The value of B(x,y) can be 0 or 1, where 0 indicates that item x doesn't belong to category y and 1 indicates that item x belongs to category y. In this we took 10 items and 10 categories, so this table has 10 x 10 entries. This entries were randomly generates.

VII. IMPLEMENTATION OF COLLABORATIVE FILTERING APPROACH
We have used the Memory based approach to implement our Model. This is the basic formula for the Memory based model. 'u' is the active user, 'I' is the item for which we are predicting the rating. 'userSim' is the function of calculating the similarity between two users(neighbors), r ni is the raring of user 'n' for item 'i'. Here 'n' is a neighbor of the active user.
This formula has many problems like: • The prediction will be miss-scaled, if the similarities of the neighbors do not sum up to one. To calculate a weighted average of ratings, the sum of the coefficients that multiply the ratings should be 1. Otherwise: o If the sum of the similarities of the neighbours is higher than one, the predicted value will be higher than the real weighted average.
o If the sum of the similarities of the neighbours is lower than one, the predicted value will be lower than the real weighted average.
• Different users use different rating scales in their minds. Is necessary to normalize the different scales [6].
Now we have come up to the formula: To resolve the problem of the wrong scale due to the sum of the userSim coefficients, the result is divided by the sum of all coefficients to normalize the scale. Finally, to get the correct estimation the average value of the ratings of the user is added, because it was subtracted during the calculation.
Cr u,n denotes the set of co-rated items between Active user u and his/her neighbors n. This is the Pearson Correlation and it has been used to measure the correlation between the ratings of the Active user and its neighbor.

VIII. DISADVANTAGES OF COLLABORATIVE APPROACH
The basic challenge in collaborative filtering is named Cold-Start which in new items, products, services or etc. that have not been yet rated by the users. In this scenario many people have to rate the items, products, services or etc. before the system will be effective. Data sparsity is the another problem which can occur when there are many items, products, services or etc. to rate and user normally only rates a few items, products, services or etc. which it leads to impede finding users similar to the target one.

IX. IMPLEMENTATION OF PROBABILISTIC APPROACH / SOCIAL NETWORK-BASED RECOMMENDER SYSTEM
The improved version of collaborative filtering tries to propose a model that takes user preference, item acceptance and friend inference into consideration (figure 1). We briefly explain each criterion and how they can be involved in final decision. 1) User preference: user preference probability which is based on naïve Bayes assumption will be achieved through equation (1) where Pr(A'1, A'2, ..., A'n) and Pr(RU = k) are normalization constant and the prior probability that U gives a ranking k. User Preference is actually the probability that a user U will give a rating K to any item I provided that item has attributes A.
2) Item acceptance: this probability which is similar to estimation in user preference, captures the general acceptance of item I from point of view users like user U. Item acceptance is the probability that a given item I will get rating K from users, provided that item has attributes A.
where Pr(RI = k) is the prior probability that the target item I receives a rating value k, and Pr(Aj | RI = k) is the conditional probability that user attribute Aj of a reviewer has a value of aj given item I receives a rating k from this reviewer [1]. These two probabilities can be learned by counting the review ratings on the target item I in a manner similar to what we did in learning user preferences [1].
3) Friend inference: in this step, SNRS learns how the particular user U and each his/her friend V are related based on the items they have both rated previously. This probability is achieved through estimating user similarities or coefficients, either based on user profiles or user rating. Friend Inference for a user U for an Item I, is the probability that friends of that user will give a rating K to that item I.

4)
To get the final probability, that a user U will give rating K to a given item I, provided that the item has attributes A, we multiply all three of them and divide by a normalizing factor. Z can be calculated from training dataset. P f = (P u x P i x P fi ) / Z 5) To calculate the predicted rating Kf, that a user U will give to an item I, provided that item I has attributes A, is given by taking the weighted mean of all rating from 1 to 5 with their corresponding probabilities. K f = ∑ P fi *k i / ∑ P fi i = 1,2,3,4,5.

X. COMPARISON
We have used two measures to compare both approaches.

1) MAE (Mean Absolute Error)
Mean absolute is the mean of absolute error of the number of observations. In this project we compared 50

) Accuracy
Accuracy is the percentage of total number of observations in which the recommended made was exactly the same as the actual value. Accuracy = (C / N) x 100 % Where C is total number of observations in which the recommended made was exactly the same as the actual value.
N is total number of observations. XII. CONCLUSION In this paper we have implemented two algorithms which are collaborative filtering and improved version of probability approach. As it was expected, the improved version which is known as Social Network Recommender System has better efficiency in comparison with traditional collaborative filtering because in this approach user's own preference, item's general acceptance and influences from friends have been taken into consideration. The main issue about the results is that the difference between two results are not that much noticeable which is somehow related to the limitations about finding actual data set based on two algorithms input requirements.