kNN CF: a temporal social network

ABSTRACT

Recommender systems, based on collaborative filtering, draw their strength from techniques that manipulate a set of user-rating profiles in order to compute predicted ratings of unrated items. There are a wide range of techniques that can be applied to this problem; however, the k-nearest neighbour (kNN) algorithm has become the dominant method used in this context. Much research to date has focused on improving the performance of this algorithm, without considering the properties that emerge from manipulating the user data in this way. In order to understand the effect of kNN on a user-rating dataset, the algorithm can be viewed as a process that generates a graph, where nodes are users and edges connect similar users: the algorithm generates an implicit social network amongst the system subscribers. Temporal updates of the recommender system will impose changes on the graph. In this work we analyse user-user kNN graphs from a temporal perspective, retrieving characteristics such as dataset growth, the evolution of similarity between pairs of users, the volatility of user neighbourhoods over time, and emergent properties of the entire graph as the algorithm parameters change. These insights explain why certain kNN parameters and similarity measures outperform others, and show that there is a surprising degree of structural similarity between these graphs and explicit user social networks.

REFERENCES

• 1: J. Ben Schafer , Joseph Konstan , John Riedi, Recommender systems in e-commerce, Proceedings of the 1st ACM conference on Electronic commerce, p.158-166, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337035]
• 2: M. J. Pazzani and D. Billsus. Content-based recommendation systems. The Adaptive Web, pages 325--341, 2007.
• 3: Neal Lathia , Stephen Hailes , Licia Capra, The effect of correlation coefficients on communities of recommenders, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1364172]
• 4: 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]
• 5: A. Barabasi and R. Albert. Statistical mechanics of complex networks. Reviews of Modern Physics, 74:47--97, 2002.
• 6: Marcelo Maia , Jussara Almeida , Virgílio Almeida, Identifying user behavior in online social networks, Proceedings of the 1st workshop on Social network systems, p.1-6, April 01-01, 2008, Glasgow, Scotland [doi>10.1145/1435497.1435498]
• 7: Jonathan L. Herlocker , Joseph A. Konstan , Al Borchers , John Riedl, An algorithmic framework for performing collaborative filtering, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.230-237, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312682]
• 8: Robert M. Bell , Yehuda Koren, Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.43-52, October 28-31, 2007 [doi>10.1109/ICDM.2007.90]
• 9: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150476]
• 10: Jun Wang , Arjen P. de Vries , Marcel J. T. Reinders, Unifying user-based and item-based collaborative filtering approaches by similarity fusion, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148257]
• 11: A. M. Rashid, G. Karypis, and J. Riedl. Influence in ratings-based recommender systems: An algorithm-independent approach. In Proceedings of SIAM 2005 Data Mining Conference, 2005.
• 12: Gediminas Adomavicius , Ramesh Sankaranarayanan , Shahana Sen , Alexander Tuzhilin, Incorporating contextual information in recommender systems using a multidimensional approach, ACM Transactions on Information Systems (TOIS), v.23 n.1, p.103-145, January 2005 [doi>10.1145/1055709.1055714]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Performance, Theory

Keywords:
graph analysis, power users, recommender systems, similarity, temporal