With the increase of time-stamped data, the task of recommender systems becomes not only to fulfill users interests but also to model the dynamic behavior of their tastes. This paper proposes a novel architecture, called Dynamic Community-based Collaborative filtering (D2CF), that combines both recommendation and dynamic community detection techniques in order to exploit the temporal aspect of the community structure in real-world networks and to enhance the existing communitybased recommendation. The eciency of the proposed D2CF is dealt with a comparative study with a recommendation system based on static community detection and item-based collaborative filtering. Experimental results show a considerable improvement of D2CF recommendation accuracy, whilst it addresses both of scalability and sparsity problems.
Several types of recommenders have been proposed and can be categorized into
three major categories [
In this work, we focus on collaborative filtering which predicts users interests/preferences from those of remaining users sharing similar tastes. Collaborative filtering is considered as one of the most used techniques due to its eciency and its high accuracy . Typically, the recommendation process for this technique starts when users express their preferences by rating items. The system analyzes these ratings to determine the exact preferences of the user, then, matches the active user’s preferences and the preferences collection to discover the category of users having similar taste with the active user. Finally, the system recommends a set of items for the active user according to the preferences of their similar users.
From another side, the community detection presents a growing interest for
many researchers, especially in web applications. A panoply of community
detection algorithms exist in literature and most of them focus on static community
detection, but recently the dynamic aspect of networks has sparked a new line of
research. Static community detection algorithms have been explored in
collaborative filtering, based on the idea that community structure will enhance the
performance of recommendations [
The purpose of this paper is to model the dynamic behavior of users in recommender systems. We assume that users behaviors are learned from users’ ratings data and more specifically by looking firstly at the items which have been rated by each user and then finding how to link items to each other over time in order to build the dynamic network of items. Our major contribution consists in presenting a novel approach named Dynamic Community-based Collaborative Filtering (denoted D2CF for short) capturing dynamic communities of items which present the evolution of users interests and preferences over time to over recommendations more suitable for real-world networks.
This paper is organized as follows: Section 2 presents the basic concepts of recommendation and community detection. Related work is provided in Section 3. Our proposed architecture D2CF is presented in Section 4. Section 5 is dedicated to the experimental study. 2
Basic concepts for recommendation and community detection This section gives a brief overview on both recommendation systems and community detection. 2.1
Recommender systems have been proposed to address the information overload problem by filtering the relevant data and suggesting items of potential interest to users. Formally, in a typical recommendation system, there is a set of users U and a set of items I. The task of recommender system is to predict user’s preferences P for each item in I. The output is a list L containing items with the highest preference values. Content-based filtering, collaborative filtering and hybrid approaches are three major categories of recommendation methods: – Content-based approach selects items based on their content along user’s profile. Its principle is to recommend items similar to the ones that the user has preferred in the past. – Collaborative filtering approach infers user’s preferences from remaining users having similar tastes. Methods pertaining to this approach can be divided into user-based and item-based methods. – Hybrid approach combines content-based and collaborative filtering methods, in other words it takes into account both the users and the items properties.
In this work, we will focus on the most widely used recommendation method,
namely Item-based Collaborative Filtering [
Pu,j =
Pj2 S s(i, j) ru,j
Pj2 S |s(i, j)|
(1)
The similarity value can be calculated in many ways. Common methods are
Cosine similarity and Pearson Correlation [
Due to the nature of the data used in collaborative filtering, this approach
su↵ers, as the case of all methods, from one or more weaknesses such as the
cold start problem when a new user starts with an empty profile, the sparsity
problem occurring when available data are insucient for identifying similar
users, and the scalability problem when there is an excessive information of users
and items. To overcome these problems, several recommendation methods have
been implemented using di↵erent techniques. We cite in particular, clustering
techniques [
Community detection techniques aim to find subgroups where the amount of interactions inside the group is more than the interaction outside it, and this can help to understand the collective behavior of users.
The communities identification process depends on the nature of networks,
either static or dynamic. Static networks are basically constructed by
aggregating all observed interactions over a period of time and representing it as a single
graph. Dynamic networks, also called time varying graphs can be either a set of
independent snapshots taken at di↵erent time steps [
Dynamic community detection: Several researchers explored the dynamic
aspect of networks to identify communities structure and their development
over time. Hopcroft et al. [
To overcome this problem, new studies have exploited another representation
of data that takes into account all temporal changes of the network in the same
graph. We cite, in particular, the intrinsic Longitudinal Community Detection
(iLCD) algorithm proposed by Cazabet et al. [
There has recently been much research on merging community detection and recommender systems in order to provide more personalized recommendations related to users belonging to the same community. In fact, community-based recommendation is a two-step approach. The first step consists in identifying groups in which users should share similar properties and the second step uses the community into which the target user pertains to recommend new items.
Using static community detection algorithms, Kamahara et al. [
Qiang et al. [
These methods only deal with static networks, derived from aggregating data
over all time, or taken at a particular time. The accumulation of an important
mass of data in the same time and in the same graph can lead to illegible graphs,
not able to deal with the dynamic aspect of real-world networks. To take into
account the evolution of users behaviors over time using a kind of community-based
dynamic recommendation, a first attempt was established by Lin et al. [
Aiming to benefit from the whole advantages of the dynamic community detection process as part of recommender systems, we propose a global architecture allowing to ensure this combination as detailed below. 4
The proposed architecture, called Dynamic Community-based Collaborative Filtering, denoted by D2CF, is based on three main steps as shown in Figure 1. !"#$% &'(#)$* +('( 3456,(7,+'(22 2)(7 !"#$%&' #()*+,./
0+%%1#&)&(2 945!"#$%&' '+%%1#&)" :()(')&+# 2)(7
;4/('+%%(#:$)&+#52)(7
This step consists in building a dynamic network in which the evolution of the
users’ interests (i.e. the set of items be looked at or ranked) over time is
represented. We assume that if a user does not rate a given item then this latter is not
yet watched by him. It is important to note that, in this work, the nodes are the
items and not the users and hence the communities are groups of items. The
interactions between nodes are modeled using the co-ratings relationship. Indeed,
two nodes interact with each other if at least one user gives the same rating
to both of them in the same time. With the aim to prepare the list of network
changes over time, we have adapted the method of temporal network building
[
Once the dynamic network (temporal network or a sequence of snapshots) is
constructed in the pre-processing step, we are now able to use it as input to
dynamic community detection method. Based on the network interactions, a
community can be defined as a set of items that are extremely related to each
other physically (strongly connected) and semantically (a learning pattern of
items that tends to have the same interests of several users over a period of
time). The advantage here is that a community is not restricted to item-related
topics but it contains various topics (e.g. Horror, Comedy, Romance, ect.). The
novelty in this work is to apply a dynamic community detection algorithm that
takes into account the evolution of the network behavior in order to obtain a
more appropriate community structure. To ensure this step, we choose to use
the iLCD algorithm [
– A community dies when there is no disposal nodes in its structure. 4.3
In this step, the learned patterns (communities) will be exploited to help the recommender system to predict the users’ future interests based on certain categories given by these communities. Firstly, a target item should be identified for each user. The target item in this case is the item in which the active user is more interested (The item with the highest rating value). The items that belong to the communities of target item and that are not rated by the active user are selected as candidate items. The list of top k recommended items for the active user contains the k candidate items that have the highest predicted preferences. Our objective is to compute the preference of the user u on the candidate item i based on the items that belong to the communities of i. By doing this the recommendation is restricted on the communities to which the candidate item pertains. To this end, we propose an adaptation of the traditional item-based Collaborative filtering method (See Equation (1)). In fact, instead of computing user’s preferences taking into consideration all items present on the whole network to discover the most similar items to the candidate item, we only rely on the items that pertain to candidate item’s communities extracted from the dynamic network as shown in Figure 2.
Target item Item-based CF
D2CF approach
Thus, we can formally define the preference prediction as follows: Pu,i =
Pj2 C s(i, j) ru,j
Pj2 C |s(i, j)| (2) where C is the set of items pertaining to the community of i, ru,j is the rating given by the active user u to the item j and s(i, j) is the similarity degree between items i and j.
We propose to compute the similarity s(i, j) using the Pearson correlation
similarity measure [
Finally, the recommendation list contains the candidate items i having the highest preference values Pu,i.
In the case where the user is new (no ratings history), the target item of this user is learned by browsing item in the recommender system. We select then the candidate items that belong to the communities of the target item. The recommendation list contains the candidate items which are ranked according to their similarities relative to target item. 5
To evaluate the e↵ectiveness of D2CF, we propose to use the movieLens dataset available through the movieLens website (http://movieLens.umn.edu). This dataset contains in total 100.000 ratings collected by 943 users on 1682 movies, from 1909-1997 to 22-04-1998. The score of rating is ranged from 1 to 5. Each user has rated at least 20 movies. The ratings information are timestamped. We suppose that each movie is represented by a node and a community is defined as a set of nodes. If a user rates a movie, this means that he is interested in watching it. MoviLens data are represented as a sequence of temporal events in the following way: – user U1 rates movie I1 with 5 at T1, – user U2 rates movie I1 with 3 at T1,
To experimentally determine the impact of the training size on the quality of the recommended movies, we propose to test three scenarios: – Set 1 : For each user, we randomly select 90% of his ratings as instances in the training set and the remaining ones will be used in the testing set. – Set 2 : For each user, we randomly select 40% of his ratings as instances in the training set and 10% will be used in the testing set. – Set 3 : For each user, we randomly select 20% of his ratings as instances in the training set and 10% will be used in the testing set.
The data selection should take into account the evolution over time, so that, instances of the testing set should be chosen after those of the training set. We run 10-fold cross-validation on data. The precision is defined to evaluate the validity of a given recommendation list and it is formulated to detect the average of the true recommendations relative to the total number of the proposed recommendations. While the recall metric is defined as the ratio of the number of recommended objects collected by users appearing in the test set to the total number of the objects actually collected by these users.
The implementation of the whole system needs several parameters. Our choices regarding the three steps of D2CF can be summarized as follows: 1. Pre-processing step: Our idea is to extract movies interactions in such a way that we know what a movie has been assessed with another one with the same score by the same producer in the same time. In fact, if an interaction between two movies occurred more than N times over a period of P days, an edge is established between them. We define the values of P and N such a way that we conserve more links between nodes. After performing several tests on the movieLens data, we set P and N respectively to 200 and 30 for Set 1, 200 and 20 for Set 2 and 200 and 5 for Set 3. This means that, in Set 1, an edge is established between two nodes, if these ones have interacted at least 30 times over a period of 200 days and this edge is removed if less than 30 interactions have occurred between them over a period of 200 days after the edge creation date. The movies that are not very visible in the users’ ratings behaviors are considered as outliers. The outliers are the nodes that are disconnected of the core of the network due to their low interactions with other movies (i.e. there are less than N users who give the same rating for both of movies). 2. Dynamic community detection step: In this stage, we are able to apply any state of art dynamic community detection algorithm. In this experiment we choose to use iLCD algorithm to extract communities from the temporal network built above. Since the quality of resulting communities depends on the threshold (i.e. is a parameter using as input in the community detection step to determine the belonging or not of new added nodes in a community), we choose the value 0.5 to obtain by the end of the process, overlapping, small and dense communities. 3. Recommendation step: Using detected communities, we are now able to generate the top k recommendation list of movies to the active user. This step requires both the user’s ID to look for his target item and the community structure as input parameters to select the candidate items that may interest the active user. Then, the predicted preference of each candidate item is computed using Pearson correlation-based similarity measure. The items which have the top k preference predictions are recommended to the active user.
In order to evaluate both of the e↵ectiveness and eciency of our proposed D2CF approach we compare the performance of this one with the following methods: – The Static Community-based Collaborative Filtering (denoted S2CF for short), which is a static version of our proposed architecture. We keep the same parameters used for the dynamic network without taking into account the temporal dimension. This is possible since, as mentioned before, the iLCD algorithm allows both static and dynamic community detection. – The traditional item-based Collaborative Filtering with Pearson correlationbased similarity measure available from Apache mahout library in Java. The obtained results are summarized in Table 1. We can notice that our D2CF method outperforms traditional recommendation methods: item-based collaborative filtering and Collaborative filtering based on static community detection. In fact in Set 3, our approach is able even with small set of users’ data to provide users with a wealthy and varied recommendation list based on the communities of users’ interests. The recall and precision values for both item-based and static community-based collaborative filtering decrease as we increase the training set size but our approach combining recommendation and dynamic community detection still provide better recommendation quality as shown in Figure 5. In fact, D2CF gives its best results (i.e. D2CF proposes for one user an average of 6 good items out of every 10 recommended items while S2CD o↵ers an average of two good items out of every 10 recommended items and finally item-based collaborative filtering gives an average of 0,15 good items per user). These results show that our approach is the best in the case of scalable data, which is explained by the fact that the dynamic network learned by more users’ data better performs the prediction of users’ preferences for unseen items.
D2CF approach presents a significantly improvement on recommendation on both small and large sets. We can say that this approach addresses both /%(! ) . & ','! % " -&! ) +#$"%! , +*())$! ")#! ( ' & "%"! #$ "! ! scalability and sparse problems and it is able to handle the real-world networks by providing a dynamic recommendation based on dynamic communities. 6
In this paper, we propose a Dynamic Community-based Collaborative Filtering approach that combines recommendation and dynamic community detection. This approach is able to deal with real-world networks as it takes into account the evolutionary aspect of the users’ interests over time. The experimental results show that our proposed D2CF outperforms both of item-based collaborative filtering and collaborative filtering based on static communities. As a future work, we will explore the similarity computation process of users pertaining to the same community in the recommendation context.