Efficient search ranking in social networks

ABSTRACT

In social networks such as Orkut, www.orkut.com, a large portion of the user queries refer to names of other people. Indeed, more than 50% of the queries in Orkut are about names of other users, with an average of 1.8 terms per query. Further, the users usually search for people with whom they maintain relationships in the network. These relationships can be modelled as edges in a friendship graph, a graph in which the nodes represent the users. In this context, search ranking can be modelled as a function that depends on the distances among users in the graph, more specifically, of shortest paths in the friendship graph. However, application of this idea to ranking is not straightforward because the large size of modern social networks (dozens of millions of users) prevents efficient computation of shortest paths at query time. We overcome this by designing a ranking formula that strikes a balance between producing good results and reducing query processing time. Using data from the Orkut social network, which includes over 40 million users, we show that our ranking, augmented by this new signal, produces high quality results, while maintaining query processing time small.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 3: Timothy M. Chan, All-pairs shortest paths for unweighted undirected graphs in o(mn) time, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.514-523, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109614]
• 4: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 5: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269--271,1959.
• 6: Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
• 7: Andrew V. Goldberg , Chris Harrelson, Computing the shortest path: A search meets graph theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Martin Holzer , Frank Schulz , Dorothea Wagner , Thomas Willhalm, Combining speed-up techniques for shortest-path computations, Journal of Experimental Algorithmics (JEA), 10, 2005 [doi>10.1145/1064546.1180616]
• 9: Jaana Kekäläinen , Kalervo Järvelin, Using graded relevance assessments in IR evaluation, Journal of the American Society for Information Science and Technology, v.53 n.13, p.1120-1129, November 2002 [doi>10.1002/asi.10137]
• 10: Cliff Lampe , Nicole Ellison , Charles Steinfield, A face(book) in the crowd: social Searching vs. social browsing, Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, November 04-08, 2006, Banff, Alberta, Canada [doi>10.1145/1180875.1180901]
• 11: Matthew J. Rattigan , Marc Maier , David Jensen, Using structure indices for efficient approximation of network properties, 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.1150443]
• 12: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 13: Raimund Seidel, On the all-pairs-shortest-path problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.745-749, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129784]
• 14: Ellen Spertus , Mehran Sahami , Orkut Buyukkokten, Evaluating similarity measures: a large-scale study in the orkut social network, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081956]
• 15: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 16: Uri Zwick, Exact and Approximate Distances in Graphs - A Survey, Proceedings of the 9th Annual European Symposium on Algorithms, p.33-48, August 28-31, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
graphs, shortest path, social networks