Personalized recommendation based on overlapping communities using time-weighted association rules
Haoyuan Feng1, Jin Tian1, Harry Jiannan Wang2, Minqiang Li1, Fuzan Chen1, Nan Feng1
1

2

Tianjin University, Tianjin, 300072, P.R. China
University of Delaware, Newark, DE, 19716, USA jtian@tju.edu.cn Abstract
Modeling users’ ever-changing interests has been a critical topic in recommender system research. In this paper, we propose a new personalized recommendation framework by leveraging and enhancing overlapping community concepts from complex network analysis literature and developing a time-weighted association rule mining method. Experiment results show that our proposed approach outperforms several existing methods in recommendation precision and diversity.
Keywords: personalized recommendation; overlapping community; time-weighted association rules; user interests
1. Introduction
Recommender systems have been implemented by many commercial websites, such as Amazon and eBay, to help users discover products of their interests. High-quality recommender algorithms and strategies can greatly increase profits and improve user loyalty. One of the most important aspects in personalized recommendation is the user interest modeling. Most of the conventional user interest models are static models, such as the user-based collaborative filter model, assuming that the users’ interests do not change over time. However, users’ interests are rather dynamic, e.g., users may prefer different styles of clothes at different ages. Users’ interests for products like music and movie are even easier to change. Therefore, it is critical to capture user interest change over time in order for the recommender system to predict users’ preferences more accurately.
In this paper, we propose a novel recommendation model based on overlapping communities using time-weighted association rules (OCTW). Temporal factors of user interests are fully considered when generating both the overlapping communities and the association rules. The overlapping community method is adopted to generate the users’ interest relationship network based on their ratings. The association rules, which have good scalability, are generated to represent user interests. Then for each community, the proposed model operates the time decay function on association rules, which satisfy the downward closure property. Experimental results show that the proposed model can predict the user interests change better and achieve a higher recommendation accuracy compared with some traditional methods.
The key contribution of this paper is two-fold: (1) presenting a temporal overlapping community method to generate the dynamic user-user interest relationship network over time and to depict the users’ multi-interest characteristics, and (2) proposing a new time-weighted association rule algorithm to model user interests change over time. The rest of the paper is organized as follows: the details of the proposed OCTW model are elaborated in Section 2. Section
3 presents the experimental studies for verifying the proposed model. Finally, Section 4 summarizes the key points of the paper and concludes with remarks for the future research.
2. Brief Literature Review

19

When observed data is generated from a distribution that changes over time it is known as concept drift (Sahoo and Singh 2012b). Interest drift can be considered as the special term of concept drift in recommendation. Research on user interest drift can be mainly divided into two groups. The first group is to build user models on a limited number of subsets of the original dataset and then ensemble the recommendation results. Elwell proposes an ensemble of classifiers-based approach for incremental learning of concept drift by training one new classifier for each data batch (Elwell
2011b). Masud et al. classify users into several different subsets according to their interests and establish the interest models separately in different subsets’ feature space (Masud et al. 2011a).
Research in the second group tends to reduce the weights of outdated data for recommendations.
Rafeh and Bahrehmand develop a time-adaptive collaborative filtering model to identify the user interest change by introducing a time-decay function (Rafeh and Bahrehmand 2012a). Huang et al. propose a two-stage recommender system based on time series to capture the main interests of users in supermarket purchase (Huang and Huang 2009a). Koren use the user ratings to represent user’s changeable interest in a potential matrix factorization model (Koren 2010b).
People may have multiple interests at the same time period resulting in the diversity of the user interest. There has been some recent work on modeling users’ multiple interests. Cantador and Castells describe a proposal to automatically extracting multilayered communities of interest from semantic user profiles and applied it to group modeling and hybrid recommendations
(Cantador and Castells 2011b). Chen et al. proposed a generalized cross domain collaborative filtering framework to make recommendations from multiple domains (Chen et al. 2013). The overlapping community methods provide an alternative to represent the variability and diversity of the user interests. The users in the overlapping part belong to more than one community and thus have multiple interests. Research has shown that local fitness maximisation (LFM) algorithm, i.e., a local optimized overlapping-community algorithm, is better than the traditional global optimized ones (Lancichinetti et al. 2009a).
Association rules (AR) have been successfully used to represent user interests in some static recommendation model (Wang and Shao 2004b). Generally, user interests can be provided by AR in the rule form ‘A B’(A and B are the implicit/explicit user interest or items), which means that the users that have the interest ‘A’ are likely interested in ‘B’. Each rule represents a specific association with a certain interest. As for dynamic interest models, some researches have adopted the calendar-based temporal association rules to show the date effect on the user interest (Li et al.
2003a), while others have conducted the time-interval rules to describe the purchase cycle (Joong and Nam 2012a). Time association rules with time-varying minimum support are also proposed, which changes the downward closure property (Cagliero 2013a).
The proposed model aims to capture the user’s multiple interest in a temporal context with a modified LFM-based overlapping community method. And a time-weighted AR method is further precisely designed to predict the user interest that is changeable over time in each community.
3. OCTW Configuration
3.1 Framework of OCTW
The framework of proposed model has three parts in Figure 1. The first part is to generate the overlapping communities, which contains three steps: user-user network setting, overlapping community detection and community combination. The second part of the proposed model is to mine the association rules in those overlapping communities separately, which includes frequent itemset mining and time-weighted rules’ generation. It’s the core part of proposed model by fully considering the time effect and increasing the ability to follow user interest change. The third part is the personalized recommend part which filters association rules for users. As one person may

20

belong to a few communities, the recommendation list could contain recommendations from different interest groups. So the third part combines the recommended items by membership to communities and gets Top-N items from list for each person. These make the model personalized.

Figure 1. Framework of OCTW

3.2 Overlapping community generation
Split the training data into a pre-designed period of time (six months in this paper) as the timestamp of data. User purchase/rating history can be transformed into the user-item matrix
M = [mij ]nu ni by a forgetting-curve-liked function as follows
- (TL- periodij )

mij = e
0

if period > 0

(1)

if period = 0

where TL is the duration of training data, periodij is the serial number of month when the user i bought/rated the item j, is the cycle of user interests change in a certain domain. nu is the number of the user and ni is the number of item. Thus user-user network is generated based on the matrix, by adding edges between users who “like” the same items. The weight of edge is decided by both the number of same items the two correlated users have bought/rated and the difference between the two users’ buying/rating time. So one same item contributes a weight ranged from 0 to 1.
Then a modified LFM algorithm is adopted to detect the overlapping communities in user-user network. We use both the identical main process and the same fitness function of the original LFM method (Lancichinetti et al. 2009a). But the choosing principle of the start node in our modified LFM method is based on the degree ranking. An additional community combination process is executed after the communities could not expand and a hybrid community combination strategy is adopted in the proposed recommendation model.
For one thing, if the original communities obtained by LFM method have high combined degree (CD), it means there are too many points in the overlapping domain of two communities.
Accordingly, we combine these communities if the combined degree is higher than a pre-designed threshold. The combined degree is calculated as follows (Wang 2011a):
C p Cq
N (C p ) N (Cq )
(2)
CD pq = ×
+ (1- )
C p Cq
N (C p ) N (Cq )

where C p , Cq are the overlapping communities. N (C p ) is the neighbor set of C p . Thus CD pq is decided by both inside nodes and outside neighbors.
[0,1] is a pre-designed parameter.
On the other side, if one of the two communities is much smaller than the other, that is, the proportion of the two communities is smaller than a pre-designed value, the CD is calculated as:
C p Cq
(3)
CD pq = min(C p , Cq )

21

This kind of CD definition aims to obtain CD values based on the proportion of the overlapping part to the smaller community.
3.3 Association rule mining
The frequent itemset mining is a time-consuming process with scanning the dataset many times.
FP growth algorithm can speed up the process in parallel processing without the generation of the candidate itemsets. Based on FP model, we proposed a novel time-weighted rule mining method.
First, split the training set into TL periods, calculate the weight in each time period using expression (1), and normalize the weights. Weight s denotes the normalized weights and
Weights

0,1 , s=1,…, TL. Then calculate the support of rules in different durations and get time

conferences Timeconf :
Timeconf ( A

B) =

1 support ( A)

TL

TL

Weights ( A) s=1 Weightt ( B) supportst ( A B )

(4)

t=1

where supportst ( A B ) is the support of rule ‘A B’ beginning from time period s to time period t.
3.4 Personalized recommendation
The proposed model needs to combine the recommendations from different communities by considering the target user’s degree of membership in every community. The degree of membership is calculated by the percentage of the user node’s edges in a certain community to all edges of this node in all communities. Recomij is the global recommendation value of item i to

user j and defined as:
Recomij = max Degree(C p ,i ) max{Timeconf C p ( x

j )}

where Degree(C p ,i ) is the membership degree of user i in community C p , p 1, 2, is not in C p , Degree(C p ,i ) = 0 . x

(5)
. If user i

j denotes any rule which have item j as the later part in

community C p . Thus the global recommendation value of item j, Recomij is the maximum in the product values of the maximum of Timeconf ( x

j ) in each community C p and the

corresponding degree of membership in C p . After ranking the recommendation values, a Top-N recommendation strategy is used to generate the recommendation list for the target user.

4. Experiments
Experiments were conducted to testify the recommendation performance of the proposed model in predicting the user multiple and variable interest. The MovieLens dataset was adopted which has 943 users and 1682 movies in 7 months. The user rating data in the first six month were used for training and the remaining data in the seventh month for testing. Four evaluation indices, precision, recall, F1 and diversity, were used. We calculate the average values of precision, recall, F1 of all active users who like at least one item in testing month. Diversity is denoted as the number of the unique recommendations (Adomavicius and Kwon 2012a). Since the data is sparse, there are many items, which are not scored by users. These items couldn’t be judged whether people like them in the testing month. We ignore these items in the experiments.
Firstly, we assessed the proposed model with different community combination methods.
Figure 2 shows the recommendation performance of different algorithms with Top-10 recommendation. The hybrid community combination method (shown as method iv in Figure 2) was compared with the models (i) with no community combination at all and (ii) only used the

22

combination strategy mentioned in expression (2) or (iii) only used the combination strategy mentioned in expression (3). The recommendation model that used the hybrid combination strategy performed best on both precision and recall among the compared four models. The F1 score obtained by this model was also higher than that of the other three models. It means that communities with high CDs need to be combined to improve the result, and the proposed hybrid method really takes advantage of the two single strategies and keeps balance of them. Thus in the next experiments, the proposed algorithms OCTW adopted the hybrid combination strategy.
Secondly, we compared the proposed algorithm OCTW with some conventional methods, such as the traditional AR method, the user-based collaborative filtering method (UBCF), the item-based collaborative filtering method (ITCF), the time-weighted association rules model
(TWAR), the association model with overlapping communities (OCAR), and one recent research, the two-stage recommender system (TSTS) (Huang and Huang 2009a). All the algorithms adopted Top-10 recommendations strategy. The average precision, the average recall, the average F1 score and the diversity are listed in Table 1.
Table 1 Performance comparison of the seven algorithms (Top-10)

Algorithm
OCTW
OCAR
TWAR
AR
TSTS
UBCF
ITCF

Figure 2. Recommendation performance with different community combination strategies

precision
0.4809
0.4221
0.3169
0.2747
0.4673
0.2490
0.1721

recall
0.1285
0.0752
0.0371
0.0335
0.0995
0.0256
0.0143

F1
0.2027
0.1276
0.0664
0.0597
0.1641
0.0465
0.0264

diversity
139
173
65
65
59
239
338

Shown as Table 1, the proposed model performed best among the seven algorithms. Both the F1 score and the diversity obtained by OCTW are more than three times to that of AR. The
OCTW increases the F1 scores 200.5% and 58.86% compared with TWAR and OCAR respectively. Moreover, OCTW achieves the highest diversity value among the first five algorithms except OCAR, which illuminates that the overlapping community method plays an important role in depicting a certain user’s various interests so as to obtain diverse recommendations. Although the CF-based algorithms, UBCF and ITCF perform higher in diversity, they perform poorly in both precision and recall, as well as F1 score. TSTS performs similar to OCTW in precision, but much worse than OCTW in both F1 score and diversity.
Finally, we conducted experiment to testify the performance of the algorithms with different
N values in Top-N recommendation strategy. Figure 3 depicted the performance curves of the algorithms with different Ns. Except UBCF, the OCTW’s F1 is always higher than other models.
And OCTW is also higher than UBCF when N is smaller than 50, which indicates OCTW can achieve higher recommendation accuracies when the required recommendation number is limited.
For example, the screen could not show too many recommendations in a mobile recommendation context. Note that those algorithms that adopt association relationship can achieve high-quality rules as well as good recommendations when N is small. However, when N increases, there are not enough rules to extract for such big number of items with a fixed minimum support. Therefore, the performance curves of such algorithms are nearly flat as the value of N increases.
5. Conclusions and Future works
This paper proposes a dynamic model OCTW to predict user multiple and changeable interests. A modified overlapping community method is employed to describe users’ relationships based on their buying/rating actions, in fully consideration of the time weights of the relationship edges. A novel time-weighted association rule method is then designed to capture the frequent itemsets.

23

Finally the recommendation result is generated with top-N recommendation strategy.
Experimental results show that the OCTW is able to achieve a high recommendation accuracy and diversity than other conventional algorithms. We are planning to extend our research in a number of directions, such as adopting a self-tuned minimum support in the model and enhancing the model in an incremental learning frame to deal with new sequential data.

Figure 3. F1 scores of seven models with different Top-Ns

Acknowledgements
The work was supported by the National Science Fund for Distinguished Young Scholars of
China (Grant No. 70925005) and the General Program of the National Science Foundation of
China (Grant Nos. 71001076, 71101103, and 71271149).
References
1. Adomavicius, G., Kwon, Y. O. “Improving Aggregate Recommendation Diversity Using Ranking-Based
Techniques,” IEEE Transactions on Knowledge and Data Engineering (24:5), 2012a, pp. 896-911.
2. Cagliero, L. “Discovering Temporal Change Patterns in the Presence of Taxonomies,” IEEE Transactions on
Knowledge and Data Engineering (25:3), 2013a, pp. 541-555.
3. Cantador, I., Castells, P. “Extracting Multilayered Communities of Interest from Semantic User Profiles:
Application to Group Modeling and Hybrid Recommendations,” Computers in Human Behavior (27:4), 2011b, pp. 1321-1336.
4. Chen W., Hsu W., Lee M. L. “Making Recommendations from Multiple Domains,” ACM Proc KDD, 2013, pp.
892-900.
5. Elwell, R., and Polikar, R. “Incremental Learning of Concept Drift in Nonstationary Environments,” IEEE
Transactions on Neural Network (22:10), 2011b, pp. 1517-1531.
6. Huang, C. L., and Huang, W. L. “Handling Sequential Pattern Decay: Developing a Two-Stage Collaborative
Recommender System,” Electronic Commerce Research and Applications (8:3), 2009a, pp. 117-129.
7. Joong, H. C., Nam, H. P. “Comparative analysis of sequence weighting approaches for mining time-interval weighted sequential patterns,” Expert Systems with Applications (39:3), 2012a, pp. 863-873.
8. Koren, Y. “Collaborative Filtering with Temporal Dynamics,” Communications of the ACM (53:4), 2010b, pp.
89-97.
9. Lancichinetti, A., Fortunato, S., Kertesz, J. “Detecting the Overlapping and Hierarchical Community Structure in
Complex Networks,” New Journal of Physics (11:3), 2009a, pp. 033015.
10. Li, Y. J., Ning, P., Wang, X. S., Jajodia, S. “Discovering Calendar-Based Temporal Association Rules,” Data and Knowledge Engineering (44:2), 2003a, pp. 193-218.
11. Masud, M. M., Gao, J., Khan, L., Han, J. W. “Classification and Novel Class Detection in Concept-Drifting Data
Streams under Time Constraints,” IEEE Transactions on Knowledge and Data Engineering (23:6), 2011a, pp.
859-874.
12. Rafeh, R., and Bahrehmand, A. “An Adaptive Approach to Dealing with Unstable Behaviour of Users in
Collaborative Filtering Systems,” Journal of Information Science (38:3), 2012a, pp. 205-221.
13. Sahoo, N., Singh, P. V., Mukhopadhyay, T. “A Hidden Markov Model for Collaborative Filtering,” MIS
Quarterly (36:4), 2012b, pp. 1329-1356.
14. Wang, F. H., and Shao, H. M. “Effective Personalized Recommendation Based on Time-Framed Navigation
Clustering and Association Mining,” Expert Systems with Applications (27:3), 2004b, pp. 365-377.
15. Wang, Y. P. (eds.). Research on Overlapping Community Detection in Complex Networks, Taiyuan University of
Technology, Taiyuan, 2011a.

24