Abstract
The need for efficient decentralized recommender systems has been appreciated for some time, both for the intrinsic advantages of decentralization and the necessity of integrating recommender systems into P2P applications. On the other hand, the accuracy of recommender systems is often hurt by data sparsity. In this paper, we compare different decentralized user-based and item-based Collaborative Filtering (CF) algorithms with each other, and propose a new user-based random walk approach customized for decentralized systems, specifically designed to handle sparse data. We show how the application of random walks to decentralized environments is different from the centralized version. We examine the performance of our random walk approach in different settings by varying the sparsity, the similarity measure and the neighborhood size. In addition, we introduce the popularizing disadvantage of the significance weighting term traditionally used to increase the precision of similarity measures, and elaborate how it can affect the performance of the random walk algorithm. The simulations on MovieLens 10,000,000 ratings dataset demonstrate that over a wide range of sparsity, our algorithm outperforms other decentralized CF schemes. Moreover, our results show decentralized user-based approaches perform better than their item-based counterparts in P2P recommender applications.
This work is supported by the ERC Starting Grant GOSSPLE number 204742.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
MovieLens Datasets (2010), http://www.grouplens.org/node/73attachments
Tribler (2010), http://www.tribler.org
Azar, Y., Fiat, A., Karlin, A.R., Mcsherry, F., Saia, J.: Spectral analysis of data. In: ACM Symposium on Theory of Computing, pp. 619–626 (2001)
Biau, G., Cadre, B., Rouviere, L.: A stochastic model for collaborative recommendation. The Annals of Statistics (2009)
Canny, J., Sorkin, S.: Practical large-scale distributed key generation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 138–152. Springer, Heidelberg (2004)
Deshpande, M., Karypis, G.: Item-based top-n recommendation algorithms. ACM Trans. Inf. Syst. 22(1), 143–177 (2004)
Herlocker, J.L., Konstan, J.A., Borchers, A., Riedl, J.: An algorithmic framework for performing collaborative filtering. In: ACM SIGIR, pp. 230–237 (1999)
Jamali, M., Ester, M.: Trustwalker: a random walk model for combining trust-based and item-based recommendation. In: ACM SIGKDD, pp. 397–406 (2009)
Jelasity, M., Montresor, A., Babaoglu, O.: T-man: Gossip-based fast overlay topology construction. IJCNC (2009)
Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.-M., van Steen, M.: Gossip-based peer sampling. ACM Trans. Comput. Syst. 25(3), 8 (2007)
Pazzani, M.J.: A framework for collaborative, content-based and demographic filtering. Artificial Intelligence Review, 393–408 (1999)
Kermarrec, A.-M., Leroy, V., Moin, A., Thraves, C.: Addressing sparsity in decentralized recommender systems through random walks. Technical report, INRIA (2010)
Koren, Y.: Factorization meets the neighborhood: a multifaceted collaborative filtering model. In: Proc. of the 14th ACM SIGKDD, pp. 426–434 (2008)
Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Recommendation systems: A probabilistic analysis. In: Proc. IEEE Symp. on Foundations of Computer Science (1998)
Linden, G., Smith, B., York, J.: Amazon.com recommendations: item-to-item collaborative filtering. IEEE Internet Computing, 76–80 (2003)
Miller, B.N., Konstan, J.A., Riedl, J.: Pocketlens: Toward a personal recommender system. ACM Trans. Inf. Syst. 22(3), 437–476 (2004)
Breeze, J.S., Heckerman, D., Kadie, C.: Empirical analysis of predictive algorithms for collaborative filtering. In: Uncertainty in Artificial Intelligence (1998)
Sarwar, B., Karypis, G., Konstan, J., Reidl, J.: Item-based collaborative filtering recommendation algorithms. In: World Wide Web, pp. 285–295 (2001)
Tsoumakos, D., Roussopoulos, N.: Adaptive probabilistic search for peer-to-peer networks. In: P2P, pp. 102–109 (2003)
Voulgaris, S., Steen, M.V.: Epidemic-style management of semantic overlays for content-based searching. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol. 3648, pp. 1143–1152. Springer, Heidelberg (2005)
Yildirim, H., Krishnamoorthy, M.S.: A random walk method for alleviating the sparsity problem in collaborative filtering. In: Proc. of the ACM Conf. on Recommender Systems, pp. 131–138 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kermarrec, AM., Leroy, V., Moin, A., Thraves, C. (2010). Application of Random Walks to Decentralized Recommender Systems. In: Lu, C., Masuzawa, T., Mosbah, M. (eds) Principles of Distributed Systems. OPODIS 2010. Lecture Notes in Computer Science, vol 6490. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17653-1_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-17653-1_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17652-4
Online ISBN: 978-3-642-17653-1
eBook Packages: Computer ScienceComputer Science (R0)