[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2567948.2579244acmotherconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Random walks in recommender systems: exact computation and simulations

Published: 07 April 2014 Publication History

Abstract

A recommender system uses information about known associations between users and items to compute for a given user an ordered recommendation list of items which this user might be interested in acquiring. We consider ordering rules based on various parameters of random walks on the graph representing associations between users and items. We experimentally compare the quality of recommendations and the required computational resources of two approaches: (i) calculate the exact values of the relevant random walk parameters using matrix algebra; (ii) estimate these values by simulating random walks. In our experiments we include methods proposed by Fouss et al. and Gori and Pucci, method P3, which is based on the distribution of the random walk after three steps, and method P3a, which generalises P3. We show that the simple method P3 can outperform previous methods and method P3a can offer further improvements. We show that the time- and memory-efficiency of direct simulation of random walks allows application of these methods to large datasets. We use in our experiments the three MovieLens datasets.

References

[1]
Anonymous ratings data from the Jester. http://goldberg.berkeley.edu/jester-data.
[2]
Last.fm. http://www.last.fm/.
[3]
Lg u oz store. http://ozstore.uplus.co.kr/.
[4]
Movielens data sets. GroupLens Research Lab, Dept. Computer Science and Engineering, University of Minnesota. http://www.grouplens.org/node/73.
[5]
D. Billsus and M. J. Pazzani. Learning collaborative information filters. In ICML, pp. 46--54, 1998.
[6]
N. Craswell and M. Szummer Random walks on the click graph. In SIGIR, pp. 239--246, 2007.
[7]
F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans. Knowl. Data Eng., 19(3):355--369, 2007.
[8]
F. Fouss, A. Pirotte, and M. Saerens. A novel way of computing similarities between nodes of a graph, with application to collaborative recommendation. In Web Intelligence, pp. 550--556, 2005.
[9]
M. Gori and A. Pucci. Research paper recommender systems: A random-walk based approach. In Web Intelligence, pp. 778--781, 2006.
[10]
M. Gori and A. Pucci. Itemrank: A random-walk based scoring algorithm for recommender engines. In IJCAI, pp. 2766--2771, 2007.
[11]
J. L. Herlocker, J. A. Konstan, L. G. Terveen, John, and T. Riedl. Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems, 22:5--53, 2004.
[12]
J. Kunegis and S. Schmidt. Collaborative filtering using electrical resistance network models. In Industrial Conf. on Data Mining, pp. 269--282, 2007.
[13]
S. Lee,S. Song, M. Kahng, D. Lee, and S. Lee. Random walk based entity ranking on graph for multidimensional recommendation. In RecSys, pp. 93--100, 2011.
[14]
S. Lee, S. Park, M. Kahng, and S. Lee. Pathrank: a novel node ranking measure on a heterogeneous graph for recommender systems. In CIKM, pp. 1637--1641, 2012.
[15]
S. Lee, S. Park, M. Kahng, and S. goo Lee. Pathrank: Ranking nodes on a heterogeneous graph for flexible hybrid recommender systems. Expert Syst. Appl., 40(2):684--697, 2013.
[16]
L. Lovász. Random walks on graphs: A survey. Bolyai Society Mathematical Studies, 2:353--397, 1996.
[17]
P. Sarkar and A. W. Moore. A tractable approach to finding closest truncated-commute-time neighbors in large graphs. In UAI, pp. 335--343. AUAI, 2007.
[18]
A. P. Singh, A. Gunawardana, C. Meek, and A. C. Surendran. Recommendations using absorbing random walks. In NESCAI, 2007.
[19]
L. Zhang, J. Xu, and C. Li. A random-walk based recommendation algorithm considering item categories. Neurocomputing, 120(0):391 -- 396, 2013.
[20]
L. Zhang, K. Zhang, and C. Li. A topical pagerank based algorithm for recommender systems. In SIGIR, pp. 713--714, 2008.

Cited By

View all
  • (2024)Recommendation systems techniques based on generative models and matrix factorization: a surveyMathematical Modeling and Computing10.23939/mmc2024.04.107811:4(1078-1092)Online publication date: 2024
  • (2024)Adapting Job Recommendations to User Preference Drift with Behavioral-Semantic Fusion LearningProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671759(1004-1015)Online publication date: 25-Aug-2024
  • (2024)Hyper-distance oracles in hypergraphsThe VLDB Journal10.1007/s00778-024-00851-233:5(1333-1356)Online publication date: 19-Apr-2024
  • Show More Cited By

Index Terms

  1. Random walks in recommender systems: exact computation and simulations

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    WWW '14 Companion: Proceedings of the 23rd International Conference on World Wide Web
    April 2014
    1396 pages
    ISBN:9781450327459
    DOI:10.1145/2567948
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    • IW3C2: International World Wide Web Conference Committee

    In-Cooperation

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 07 April 2014

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. random walk
    2. recommendation algorithm
    3. recommendation system

    Qualifiers

    • Research-article

    Conference

    WWW '14
    Sponsor:
    • IW3C2

    Acceptance Rates

    Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)39
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 22 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Recommendation systems techniques based on generative models and matrix factorization: a surveyMathematical Modeling and Computing10.23939/mmc2024.04.107811:4(1078-1092)Online publication date: 2024
    • (2024)Adapting Job Recommendations to User Preference Drift with Behavioral-Semantic Fusion LearningProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671759(1004-1015)Online publication date: 25-Aug-2024
    • (2024)Hyper-distance oracles in hypergraphsThe VLDB Journal10.1007/s00778-024-00851-233:5(1333-1356)Online publication date: 19-Apr-2024
    • (2023)Bootstrapped Personalized Popularity for Cold Start Recommender SystemsProceedings of the 17th ACM Conference on Recommender Systems10.1145/3604915.3608820(715-722)Online publication date: 14-Sep-2023
    • (2023)When Newer is Not Better: Does Deep Learning Really Benefit Recommendation From Implicit Feedback?Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3539618.3591785(942-952)Online publication date: 19-Jul-2023
    • (2023)Comparison of Real-Time and Batch Job RecommendationsIEEE Access10.1109/ACCESS.2023.324935611(20553-20559)Online publication date: 2023
    • (2023)Graph-Based Diffusion Method for Top-N RecommendationArtificial Intelligence and Cognitive Science10.1007/978-3-031-26438-2_23(292-304)Online publication date: 23-Feb-2023
    • (2022)On the generalizability and predictability of recommender systemsProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600589(4416-4432)Online publication date: 28-Nov-2022
    • (2022)United We Stand, Divided We Fall: Leveraging Ensembles of Recommenders to Compete with Budget Constrained ResourcesProceedings of the Recommender Systems Challenge 202210.1145/3556702.3556845(34-38)Online publication date: 18-Sep-2022
    • (2022)Phishing URL DetectionProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560615(1769-1782)Online publication date: 7-Nov-2022
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media