Training random walks over absorbing graphs

Details Training random walks over absorbing graphs Training random walks over absorbing graphs

2007-06-26

2010-08-17

Vincent, David R (Department: 2129)

Data processing: artificial intelligence

Adaptive system

Reexamination Certificate

active

07778945

ABSTRACT:
A random walk is performed over a graph, such as an augmented bipartite graph, relating to ownership data with respect to a plurality of users and items owned; the graph can provide social links between the users as well. Items can be recommended to users who do not own the items by randomly walking the graph starting at the user node to which the recommendation will be given. The random walk can step from user to user or from user to item; when an item is reached, the node can be absorbing such that the random walk terminates. The arrived item is recommended to the user. Parameters can also be provided to affect decisions made during the walk about which users to walk to and/or whether to walk to a user or an item.

REFERENCES:
patent: 7548915 (2009-06-01), Ramer et al.
patent: 2006/0093142 (2006-05-01), Schneier et al.
patent: 2006/0122998 (2006-06-01), Bar-Yossef et al.
patent: 2006/0190225 (2006-08-01), Brand
patent: 2008/0032787 (2008-02-01), Low et al.
Fouss, et al., “Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation”, http://www.isys.ucl.ac.be/staff/francois/articles/fouss2006b.pdf, Mar. 2007, vol. 19, No. 3, pp. 355-369, IEE Trans Knowledge and Data Engineering.
Gori, et al., “ItemRank: A Random-Walk Based Scoring Algorithm for Recommender Engines.” IJCAI 2007. http:/
autilus.dii.unisi.it/publications/files/conference/IJCAI-PucciA.pdf, 6 pages, University Of Siena, Italty.
Brand, “A Random Walks Perspective on Maximizing Satisfaction and Profit”, http://www.merl.com/reports/docs/TR2005-050.pdf, Mitsubishi Electric Research Laboratories, 10 pages Dec. 2005.
Adomavicius, et al., “Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions”, IEEE} Trans. Knowledge Data Eng., Jun. 2005, 6 pages, vol. 17, No. 6.
Cohn, et al., “The missing link—a probabilistic model of document content and hypertext connectivity”, Last Accessed on Jun. 25, 2007, 7 pages.
Haveliwala, et al., “Topic-sensitive PageRank: a context-sensitive ranking algorithm for web search”, Last Accessed on Jun. 25, 2007, 22 pages, Stanford University.
Richardson, et al., “The intelligent surfer: Probabilistic combination of link and content information in Page Rank”, 8 pages, Department of Computer Science and Engineering, University of Washington.
Fouss, et al., “A novel way of computing dissimilarities between nodes of a graph”, Workshop on Statistical Approaches to Web Mining, 15th European Conference on Machine Learning (ECML) 8th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD) Pisa, Sep. 20-24, 2004, 12 pages.
Albert, et al., “Statistical Mechanics of Complex Networks”, Department of Physics, University of Notre Dame, Notre Dame, Indiana, vol. 74, Jan. 2002, 51 pages.
Basilico, et al., “Unifying collaborative and content-based filtering”, In Proceedings of the 21st International Conference on Machine Learning, 8 Pages, New York, NY, USA, 2004. ACM Press.
Breese, et al., “Empirical Analysis of Predictive Algorithms for Collaborative Filtering”, Technical Report MSR-TR-98-12, Microsoft Research, 1998, 19 Pages.
Canny, “Collaborative Filtering with Privacy via Factor Analysis”, Proceedings of the 25th Annual International ACM SIGIR Conference, on Research and Development in Information Retrieval ACM, Aug. 2002, 8 pages.
Dhillon, et al., “Co-Clustering Documents and Words Using Bipartite Spectral Graph Partitioning”, Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 269-274, San Francisco, California, 2001, ACM Press.
Goldberg, et al., “Using Collaborative Filtering to Weave an Information Tapestry”, Commun, ACM, 35(12): 61-70, 1992.
Goldberg, et al., “A Constant Time Collaborative Filtering Algorithm”, Inf. Retr., 4(2): 133-151, Mar. 2001.
Hofmann, et al., “Collaborative Filtering via Gaussian Probabilistic Latent Semantic Analysis”, In SIGIR 2003, Proceedings from the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pp. 259-266, NewYork, NY, USA, 2003, ACM Press.
Kautz, et al., “Referral Web: Combining Social Networks and Collaborative Filtering”, Commun. ACM, 40(3):63-65, 1997.
Kleinberg, “Authoritative Sources in a Hyperlinked Environment”, J. ACM, 46(5):604-632, 1999.
Kubica, et al., “Finding underlying connections: A fast graph-based method for link analysis and collaboration queries”, In Proceedings of the International Conference on Machine Learning, Aug. 2003.
Lempel, et al., “SALSA: The Stochastic Approach for Link-Structure Analysis”, ACM Trans. Inf. Syst., 19(2):131-160, 2001.
Linden, et al., “Amazon.com Recommendations: Item-to-Item Collaborative Filtering”, IEEE Internet Computing, 7(1): 76-80, Jan.-Feb. 2003.
Malone, et al., “Intelligent Information -Sharing Systems”, Commun, ACM, 30(5): 390-402, 1987.
Maltz, et al., “Pointing the Way: Active Collaborative Filtering”, In Proc. CHI 95: Human Factors in Computing Systems, 1995.
McJones, http://web.archive.org/web/20040216100752/www.research.compaq.com/SRC/eachmovie/, Last Accessed On Jun. 26, 2007, 3 Pages.
Melville, et al., “Content Boosted Collaborative Filtering for Improved Recommendations”, In Eighteenth National Conference on Artificial Intelligence, pp. 187-192, Menlo Park, CA, USA, 2002. American Association for Artificial Intelligence.
Page, et al., “The PageRank Citation Ranking: Bringing Order to the Web”, Technical Report, Stanford University, 1998.
Rennie, et al., “Fast Maximum Margin Matrix Factorization for Collaborative Prediction”, In Proceedings of the 22nd International Conference on Machine Learning (ICML-05), pp. 713-719, New York, NY, USA, 2005. ACM Press.
Resnick, et al., Grouplens: An Open Architecture for Collaborative Filtering of Netnews:, In CSCW 1994 Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work, pp. 175-186, New York, NY, USA, 1994. ACM Press.
Roweis, www.cs.toronto.edu/roweis/data.html, Last Accessed on Jun. 26, 2007, NIPS Conference Pagers vols. 0-12, Apr. 2002, Data set.
Sarwar, et al., Analysis of Recommendation Algorithms for e-Commerce:, In EC 2000, Proceedings of the 2nd ACM Conference in Electronic Commerce, pp. 158-167, New York, NY, USA, 2000. ACM Press.
Schein, et al., “Methods and Metrics for Cold-Start Recommendations”, In SIGIR 2002, Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 253-260, New York, NY, USA, 2002. ACM Press.

Affiliated with

Also associated with

Rating

Training random walks over absorbing graphs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Training random walks over absorbing graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Training random walks over absorbing graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4150668