Evaluating similarity measures: a large-scale study in the orkut social network

ABSTRACT

Online information services have grown too large for users to navigate without the help of automated tools such as collaborative filtering, which makes recommendations to users based on their collective past behavior. While many similarity measures have been proposed and individually evaluated, they have not been evaluated relative to each other in a large real-world environment. We present an extensive empirical comparison of six distinct measures of similarity for recommending online communities to members of the Orkut social network. We determine the usefulness of the different recommendations by actually measuring users' propensity to visit and join recommended communities. We also examine how the ordering of recommendations influenced user selection, as well as interesting social issues that arise in recommending communities within a real social network.

REFERENCES

• 1: Breese, J.; Heckerman, D.; Kadie, C. Empirical Analysis of Predictive Algorithms for Collaborative Filtering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (Madison, Wisconsin, 1998). Morgan Kaufmann.
• 2: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 3: Mukund Deshpande , George Karypis, Item-based top-N recommendation algorithms, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.143-177, January 2004 [doi>10.1145/963770.963776]
• 4: Pedro Domingos, Prospects and challenges for multi-relational data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959252]
• 5: Susan Dumais , Thorsten Joachims , Krishna Bharat , Andreas Weigend, SIGIR 2003 workshop report: implicit measures of user interests and preferences, ACM SIGIR Forum, v.37 n.2, Fall 2003 [doi>10.1145/959258.959266]
• 6: Donna Harman, Ranking algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 7: Joachims, T. Evaluating Retrieval Performance Using Clickthrough Data. In Proceedings of the SIGIR Workshop on Mathematical/Formal Methods in Information Retrieval (2002). ACM Press, New York, NY.
• 8: Henry Kautz , Bart Selman , Mehul Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM, v.40 n.3, p.63-65, March 1997 [doi>10.1145/245108.245123]
• 9: Brendan Kitts , David Freed , Martin Vrieze, Cross-sell: a fast promotion-tunable customer-item recommendation method based on conditionally independent probabilities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.437-446, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347181]
• 10: Lehmann, E.L. Testing Statistical Hypotheses (second edition). Springer-Verlag, 1986.
• 11: Raghavan, P. Social Networks and the Web (Invited Talk). In Advances in Web Intelligence: Proceedings of the Second International Atlantic Web Intelligence Conference, May 2004. Springer-Verlag, Heidelberg.
• 12: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 13: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 14: Spertus, Ellen. Too Much Information. Orkut Media Selections, January 19, 2005. Available online at "http://media.orkut.com/articles/0078.html".

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Human Factors, Measurement

Keywords:
collaborative filtering, data mining, online communities, recommender system, similarity measure, social networks