نوع مقاله : مقاله پژوهشی

نویسندگان

• فاطمه رضایی مهر ¹
• چیترا دادخواه ²

¹ دانشکده مهندسی کامپیوتر، دانشگاه صنعتی خواجه نصیرالدین طوسی

² استادیار دانشگاه صنعتی خواجه نصیرالدین طوسی

چکیده

امروزه اینترنت نقش بااهمیتی در زندگی انسان‌ها دارد و محتوای وب باید متناسب با نیازهای کاربران باشد تا اطلاعات به‌روز و مناسب با سلیقه کاربر را فراهم نماید. در این راستا، سیستم‌های توصیه‌گر به کاربران کمک کرده و اقلامی که به سیلقه کاربران نزدیک‌تر است، را به آن‌ها در کم‌ترین زمان ممکن توصیه می‌کند . امروزه، با افزایش داده، استفاده از سیستم‌های توصیه‌گر رو به افزایش است. از طرفی دیگر این سیستم‌ها با چالش‌هایی از جمله تغییر سلیقه کاربران در طی زمان، شروع سرد، خلوت بودن ماتریس کاربر-قلم، حملات افراد جعلی در سیستم و تاثیر منفی آن‌ها در لیست توصیه سیستم روبرو هستند. هدف این مقاله ارائه یک سیستم ‌‌توصیه‌گر زمان و اعتماد مبنا جهت بهبود کارایی و افزایش دقت توصیه‌های سیستم است. سیستم پیشنهادی در ابتدا با افزودن برخی امتیاز‌های ضمنی قابل اعتماد به ماتریس امتیاز‌دهی کاربر- قلم، مشکل پراکندگی داده را حل نموده و سپس یک شبکه وزن‌دار کاربر-کاربر براساس زمان ارائه نظر کاربر نسبت به قلم و روابط اعتماد میان کاربران تولید می‌نماید که بدین ترتیب مشکل شروع سرد و تغییر سلیقه کاربر در طی زمان را رفع می‌کند. سیستم توصیه‌گر پیشنهادی بر اساس الگوریتم تشخیص جامعه جدیدی که در این مقاله ارائه شده است، نزدیک‌ترین کاربران همسایه و هم‌سلیقه با کاربر فعال را پیدا نموده و بر اساس روش پالایش همکارانه، کا-بالاترین قلم را به کاربر پیشنهاد می‌دهد. نتایج ارزیابی سیستم پیشنهادی برای سیستم توصیه‌گر مبتنی بر فیلم بر روی مجموعه‌داده Epinions نشان می‌دهد سیستم پیشنهادی نسبت به سیستم‌های پایه از کارایی بالاتری برخوردار است.

کلیدواژه‌ها

• سیستم‌های توصیه‌گر
• زمان
• اعتماد
• تشخیص جوامع
• پالایش همکارانه

موضوعات

• مدیریت داده، اطلاعات و دانش در حوزه کسب‌وکار هوشمند

عنوان مقاله [English]

Recommender Systems Based On Time and Trust Using Graph Based Community Detection

نویسندگان [English]

• Fatemeh Rezaimehr ¹
• Chitra Dadkhah ²

¹ Computer Engineering Faculty, K. N. Toosi University of Technology

² -

چکیده [English]

Abstract
Recently, the Internet has played a significant and substantial role in people's lives. However, the content available in the global web environment should align with users' daily needs, providing them with useful and up-to-date information tailored to their tastes. In this context, recommender systems assist users by suggesting items that closely match their preferences in less time. Today, with the exponential growth of data, the utilization of recommender systems has surged. Conversely, these systems encounter challenges such as evolving user preferences over time, cold start problem, sparsity within the user-item matrix, the infiltration of fake users in the systems, and their adverse impact on the recommendation lists. The objective of this paper is to propose a recommender system grounded in time and trust factors to enhance the efficiency and precision of system recommendations. Initially, the proposed system addresses the data sparsity dilemma by incorporating reliable implicit ratings into the user-item matrix. Subsequently, it constructs a weighted user-user network based on user rating timestamps and trust relationships among users, thereby mitigating the cold start problem and accounting for changing user preferences over time. The proposed recommender system employs a novel community detection algorithm introduced in this paper to identify the nearest neighbors of active users and recommends the top @k items based on the collaborative filtering approach. Evaluation results of the proposed system, tested on a film recommender system using the Epinions dataset, demonstrate its superior efficiency compared to basic systems.

Introduction

Today, with the increasing tendency of users to use websites for obtaining information, online shopping, and using social networks for expressing personal opinions, the ways of obtaining information and establishing connections among users have undergone significant changes. Consequently, users are confronted with the big of data. Managing this data and selecting the appropriate options from this vast collection and presenting it to users is one of the main reasons for the development of information retrieval systems and search engines. In this regard, Recommendation Systems (RSs) help users choose the best options and recommend items that are closer to their preferences in the shortest possible time. Different models of RS such as collaborative filtering, content-based, knowledge-based, and newly developed context-aware RS, have been presented by researchers (Casillo et al., 2022). Each has its own advantages and disadvantages, which can be combined to create a hybrid RS. It should be noted that RS face challenges, including changes in user preferences over time, cold start for new users or items, sparsity of the user-item matrix, attack by fake users, and their negative impact on the recommendation list. In this paper, a time- and trust-based recommendation system is presented to enhance the performance and accuracy of recommendations. Our proposed system initially solves the data sparsity problem by adding reliable implicit ratings to the user-item rating matrix. It then generates a weighted user-user network based on the time of user feedback on items and trust relationships among users. This approach addresses the cold start problem and the change in user preferences over time. Our system is based on a novel community detection algorithm presented in this article, which identifies the nearest neighboring users with similar tastes to the active user and recommends the top-k items using the collaborative filtering method. The evaluation of the proposed system is performed on an Epinions dataset for a movie recommendation system. The evaluation uses metrics such as accuracy, recall, F1 score, mean absolute error, and root mean square error. The experimental results indicate the superior performance of the proposed system compared to similar systems.

Literature Review

In the recent years, the researchers attempt to improve the accuracy of their recommendation for retaining the users and increasing the profit. Some of the papers has worked on optimizing the performance of their proposed RS using evolutionary algorithms (Tohidi & Dadkhah, 2020) and the others used the additional information such as time, location, etc. Trust-based RSs have been recently introduced to the community of computer science. Recent studies have shown that incorporating social factors or trust statements in RSs leads to the improvement of recommendation quality (P. Moradi & Ahmadian, 2015; S. Ahmadian, M. Meghdadi, & Afsharchi, 2018b). So far, several trust-based CF approaches have been proposed to overcome data sparsity and cold-start problems as well as to increase recommendable items (Ghavipour & Meybodi, 2016; Moradi, Ahmadian, & Akhlaghian, 2015; P. Massa & Avesani, 2007; Ranjbar Kermany & Alizadeh, 2017). Trust statements can be explicitly collected from users or can be implicitly inferred from users behaviors (S. Ahmadian, M. Meghdadi, & Afsharchi, 2018a; S. Ahmadian, P. Moradi, & Akhlaghian, 2014). Liu and Lee proposed a specific approach which does not directly use the trust information; instead they take into account the number of exchanged messages among the users of the system to construct the trust network (Liu & Lee, 2010). Alahmadi and Zeng presented a framework to apply short texts posted by users friends in microblogs as an additional data source to build the trust network (Alahmadi & Zeng, 2015). Since explicit trust statements are directly specified by the users, they are more accurate and reliable than implicit ones in determining social relationships among users (Cho, Kwon, & Park, 2009; Ingoo, Kyong, & Tae, 2003; Lathia, Hailes, & Capra, 2008; Manolopoulus, Nanopoulus, Papadopoulus, & Symeonidis, 2008).
The research In (Abdul-Rahman & Hailes, 2000) has been shown that a user constructs his/her social connections with someone who has similar tastes. Massa and Avesani showed that adding social network data to traditional collaborative filtering improves the recommendation results (P. Massa & Avesani, 2007). Gharibshah and Jalili studied the relation between RSs and connectedness of users-items bipartite interaction network (Gharibshah & Jalili, 2014). Guo et al. proposed a method which merged the ratings of users trusted neighbors with the other information sources to identify their preferences (G. Guo, J. Zhang, & Thalmann, 2014). Yang et al. proposed a Bayesian inference based recommendation method for online social networks (X. Yang, Y. Guo, & Liu, 2013). In this method, the similarity value between each pair of users is measured using a set of conditional probabilities derived from their mutual ratings. Jiang et al. introduced a framework to incorporate interpersonal influences of users in social network with their individual preferences to improve the accuracy of social recommendation (Jiang, Cui, Wang, Zhu, & Yang, 2014).
Purchase/rating time is one of the most important contextual information that can be used to design RSs with high precision (Xiong, Chen, Huang, Schneider, & Carbonell, 2010). The main motivation for time-aware RS is that in realistic scenarios users tastes might change over time.

Methodology

We propose a time and trust-aware RS using a graph-based community detection method consists of four steps: 1: developing a user-item rating matrix, 2: constructing a time weighted user-user network, 3: performing graph- based community detection, 4: recommending Top-N items. In the first step, the user-item rating matrix is developed by adding some implicit ratings and the quality of the implicit ratings is evaluated using a reliability measurement. In the second step, a time-weighted user-user network is constructed based on the combination of trust relationships and similarity between users. Moreover, the timestamps of user-item ratings are considered to calculate the similarity between users. In the third step, a graph-based community detection method classifies similar users into appropriate communities. Finally, in the fourth step, it predicts the rating for each unobserved item and top-N recommendations is generated for the target user.
We proposed a new community detection method that consists of three phases. First, the initial centers of communities are obtained using a sparsest subgraph of weighted user-user network. It should be noted that the initial centers must have the maximum dissimilarities with each other based on the general concept of clustering and community detection algorithms. Then users can be assigned to their nearest communities. For each user proposed system calculated the fitness function. User has associated to community which has high value of fitness function. Then the centers of communities were updated in order to maximize a fitness function. This process is iteratively repeated until members of communities do not change and steady state is achieved. A set of communities are identified where the users are assigned to their corresponding communities. Some of the communities may have overlap and they can be merged. The final communities were used as the nearest neighbors set of the active user in the same community for the recommendation.

Conclusion

Our proposed algorithm solves the sparsity of rating matrix by adding the implicit rating and solved cold-start problem for new users by considering the trust between the users. We applied the proposed algorithm on extended Epinions dataset and compared its performance with similar algorithms. The experimental results showed that our proposed algorithm outperforms the other algorithms according to the accuracy and recommends the top@N items with high precision. 

کلیدواژه‌ها [English]

• Recommender Systems
• Time
• Trust
• community Detection
• Collaborative Filtering