A Recommendation Algorithm Based on Random Walk in Trust Network
Yuan Fuyong, Cai Honglei
College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China
The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province, Qinhuangdao 066004, China
[Objective] The current recommendation algorithm based on trust confronted with these issues: the explicit trust value is not accurate enough, the implicit trust value is hard to measure, the trust propagation path is not easy to determine. For that this paper presents a recommendation algorithm based on random walk in the trust network. [Methods] The algorithm uses the Bipartite network-based projection structure measure trust value between users, then these values are the formation of the transition probability matrix for random-walk with restart in the users projection network, random walk process does not stop until the trust distribution tends to be steady, namely the trust maximum entropy is achieved. The trust distribution at this time is the final trust matrix. [Results] The experiments on MovieLens dataset show that the improved Bipartite recommendation algorithm by adding user preferences significantly improves the Mean Absolute Error (MAE), Mean Reciprocal Rank(MRR) and normalize Discounted Cumulative Gain (nDCG) compared to other algorithms. [Limitations] Due to the cold start problems in the Bipartite network-based projection algorithm, this algorithm suffers from the new user/new item problem also. [Conclusions] That is to say, this algorithm can make the recommendation more accurate and successfully recommended objects rank in the front of the list, so this algorithm has a strong application value.
原福永, 蔡红蕾. 一种在信任网络中随机游走的推荐算法[J]. 现代图书情报技术, 2014, 30(10): 70-75.
Yuan Fuyong, Cai Honglei. A Recommendation Algorithm Based on Random Walk in Trust Network. New Technology of Library and Information Service, DOI：10.11925/infotech.1003-3513.2014.10.11.
 Pazzani M J, Billsus D. Content-Based Recommendation Systems [A]//Brusilovsky P, Kobsa A, Nejdl W. The Adaptive Web [M]. Berlin: Springer, 2007: 325-341.
 Degemmis M, Lops P, Semeraro G. A Content-Collaborative Recommender that Exploits Wordnet-based User Profiles for Neighborhood Formation [J]. User Modeling and User-Adapted Interaction, 2007, 17(3): 217-255.
 Chen Y, Cheng L. A Novel Collaborative Filtering Approach for Recommending Ranked Items [J]. Expert Systems with Applications, 2008, 34(4): 2396-2405.
 Konstan J A, Miller B N, Maltz D, et al. GroupLens: Applying Collaborative Filtering to Usenet News [J]. Communications of the ACM, 1997, 40(3): 77-87.
 Herlocker J L, Konstan J A, Terveen L G, et al. Evaluating Collaborative Filtering Recommender Systems [J]. ACM Transactions on Information System (TOIS), 2004, 22(1): 5-53.
 Guo G. Improving the Performance of Recommender Systems by Alleviating the Data Sparsity and Cold Start Problems[C]. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 2013: 3217-3218.
 Guo G. Resolving Data Sparsity and Cold Start in Recommender Systems [C]. In: Proceedings of the 20th International Conference on User Modeling, Adaptation and Personalization. 2012: 361-364.
 Zhou T, Ren J, Medo M, et al. Bipartite Network Projection and Personal Recommendation [J]. Physical Review E, 2007, 76: Article No. 046155.
 Zhang Y C, Blaitner M, Yu Y. Heat Conduction Process on Community Networks as a Recommendation Model [J]. Physical Review Letters, 2007, 99(15): Article No. 154301．
 Guo G, Zhang J, Thalmann D, et al. From Ratings to Trust: An Empirical Study of Implicit Trust in Recommender Systems [C]. In: Proceedings of the 29th Annual ACM Symposium on Applied Computing, 2014: 248-253.
 Guo G, Erdt M H, Lee B S. A Hybrid Recommender System Based on Material Concepts with Difficulty Levels [C]. In: Proceedings of the 21st International Conference on Computers in Education. 2013.
 Morales J M, Peis E, Herrera-Viedma E. A Filtering and Recommender System for E-Scholars [J]. International Journal of Technology of Enhanced Learning, 2010, 2(2): 227-240.
 Guo G. Integrating Trust and Similarity to Ameliorate the Data Sparsity and Cold Start for Recommender Systems [C]. In: Proceedings of the 7th ACM Conference on Recommender Systems. ACM, 2013: 451-454.
 刘淇, 陈恩红. 结合二部图投影与排序的协同过滤[J]. 小型微型计算机系统, 2010, 31(5): 835-839. (Liu Qi, Chen Enhong. Collaborative Filtering Through Combining Bipartite Graph Projection and Ranking [J]. Journal of Chinese Computer Systems, 2010, 31(5): 835-839.)
 Fouss F, Pirotte A, Renders J M, et al. Random-Walk Computation of Similarities Between Nodes of a Graph with Application to Collaborative Recommendation [J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3): 355-369.
 Moffat A, Zobel J. Rank-based Precision for Measurement of Retrieval Effectiveness [J]. Transactions on Information Systems (TOIS), 2008, 27(1): Article No. 2.