A recommender system based on local random walks and spectral methods

ABSTRACT

In this paper, we design recommender systems for weblogs based on the link structure among them. We propose algorithms based on refined random walks and spectral methods. First, we observe the use of the personalized page rank vector to capture the relevance among nodes in a social network. We apply the local partitioning algorithms based on refined random walks to approximate the personalized page rank vector, and extend these ideas from undirected graphs to directed graphs. Moreover, inspired by ideas from spectral clustering, we design a similarity metric among nodes of a social network using the eigenvalues and eigenvectors of a normalized adjacency matrix of the social network graph. In order to evaluate these algorithms, we crawled a set of weblogs and construct a weblog graph. We expect that these algorithms based on the link structure perform very well for weblogs, since the average degree of nodes in the weblog graph is large. Finally, we compare the performance of our algorithms on this data set. In particular, the acceptable performance of our algorithms on this data set justifies the use of a link-based recommender system for social networks with large average degree.

REFERENCES

• 1: http://www.blogpulse.com visited Dec. 2006.
• 2: J. Parsons, P. Ralph, K. Gallagher. Using viewing time to infer user preference in recommender systems. AAAI Workshop in Semantic Web Personalization, San Jose, California, July, 2004.
• 3: Paul Resnick , Hal R. Varian, Recommender systems, Communications of the ACM, v.40 n.3, p.56-58, March 1997 [doi>10.1145/245108.245121]
• 4: Reid Andersen , Fan Chung , Kevin Lang, Local Graph Partitioning using PageRank Vectors, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.475-486, October 21-24, 2006 [doi>10.1109/FOCS.2006.44]
• 5: S. Brin, L. Page,R. Motwani, T. Winograd. The PageRank citation ranking: Bringing order to the web., Technical report, Stanford Digital Library Technologies Project, 1998.
• 6: R. E. Tarjan. Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1(2):146--160, 1972.
• 7: D. Verma, M. Meila. A comparison of spectral clustering algorithms., technical report UW-cse-03-05-01, University of Washington.
• 8: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 9: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 10: A. Ng, I. Jordan, Y. Weiss. On Spectral Clustering: Analysis and an algorithm, Advances in Neural Information Processing Systems, 14, pages 849--856.
• 11: Jonathan L. Herlocker , Joseph A. Konstan , Loren G. Terveen , John T. Riedl, Evaluating collaborative filtering recommender systems, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.5-53, January 2004 [doi>10.1145/963770.963772]
• 12: L. Lovasz. Random walks on graphs: A survey. January 1993.
• 13: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 14: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 15: T.H. Haveliwala.Topic-sensitive PageRank: A context-sensitive ranking algorithm for web search. IEEE Trans. Knowl. Data Eng., 15(4):784--796, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
RandomWalks, personalized PageRank, recommender systems, social network analysis, spectral methods, weblogs