TrustWalker: a random walk model for combining trust-based and item-based recommendation

ABSTRACT

Collaborative filtering is the most popular approach to build recommender systems and has been successfully employed in many applications. However, it cannot make recommendations for so-called cold start users that have rated only a very small number of items. In addition, these methods do not know how confident they are in their recommendations. Trust-based recommendation methods assume the additional knowledge of a trust network among users and can better deal with cold start users, since users only need to be simply connected to the trust network. On the other hand, the sparsity of the user item ratings forces the trust-based approach to consider ratings of indirect neighbors that are only weakly trusted, which may decrease its precision. In order to find a good trade-off, we propose a random walk model combining the trust-based and the collaborative filtering approach for recommendation. The random walk model allows us to define and to measure the confidence of a recommendation. We performed an evaluation on the Epinions dataset and compared our model with existing trust-based and collaborative filtering methods.

REFERENCES

• 1: Reid Andersen , Christian Borgs , Jennifer Chayes , Uriel Feige , Abraham Flaxman , Adam Kalai , Vahab Mirrokni , Moshe Tennenholtz, Trust-based recommendation systems: an axiomatic approach, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367525]
• 2: Robert Bell , Yehuda Koren , Chris Volinsky, Modeling relationships at multiple scales to improve accuracy of large recommender systems, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281206]
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: David Crandall , Dan Cosley , Daniel Huttenlocher , Jon Kleinberg , Siddharth Suri, Feedback effects between similarity and social influence in online communities, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401914]
• 5: Jennifer Ann Golbeck , James Hendler, Computing and applying trust in web-based social networks, University of Maryland at College Park, College Park, MD, 2005
• 6: David Goldberg , David Nichols , Brian M. Oki , Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, v.35 n.12, p.61-70, Dec. 1992 [doi>10.1145/138859.138867]
• 7: Yehuda Koren, Factorization meets the neighborhood: a multifaceted collaborative filtering model, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401944]
• 8: Levien and Aiken. Advogato's trust metric. online at http://advogato.org/trust-metric.html, 2002.
• 9: Hao Ma , Haixuan Yang , Michael R. Lyu , Irwin King, SoRec: social recommendation using probabilistic matrix factorization, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458205]
• 10: Paolo Massa , Paolo Avesani, Trust-aware recommender systems, Proceedings of the 2007 ACM conference on Recommender systems, October 19-20, 2007, Minneapolis, MN, USA [doi>10.1145/1297231.1297235]
• 11: S. Milgram. The small world problem. Psychology Today, 2, 1967.
• 12: John O'Donovan , Barry Smyth, Trust in recommender systems, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA [doi>10.1145/1040830.1040870]
• 13: Achim Rettinger , Matthias Nickles , Volker Tresp, A statistical relational model for trust learning, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 14: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 15: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 16: S. Wasserman and K. Faust. Social Network Analysis. Cambridge Univ. Press, 1994.
• 17: Hilmi Yildirim , Mukkai S. Krishnamoorthy, A random walk method for alleviating the sparsity problem in collaborative filtering, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454031]
• 18: C. N. Ziegler. Towards Decentralized Recommender Systems. PhD thesis, University of Freiburg, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Experimentation, Measurement

Keywords:
random walk, recommendation, trust