skip to main content
10.1145/1321440.1321520acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Efficient search ranking in social networks

Published: 06 November 2007 Publication History

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]
R. A. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999.
[2]
S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the seventh international conference on World Wide Web, pages 107--117, Amsterdam, The Netherlands, The Netherlands, 1998.
[3]
T. M. Chan. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithms, pages 514--523, New York, NY, USA, 2006.
[4]
J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In Sixth Symposium on Operating System Design and Implementation, pages 137--150, 2004.
[5]
E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269--271,1959.
[6]
D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740--1759, 2000.
[7]
A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 156--165, Philadelphia, PA, USA, 2005.
[8]
M. Holzer, F. Schulz, D. Wagner, and T. Willhalm. Combining speed-up techniques for shortest-path computations. Journal of Experimental Algorithmics, 10, 2005.
[9]
J. Kekäläinen and K. Järvelin. Using graded relevance assessments in ir evaluation. Journal of the American Society for Information Science and Technology, 53(13):1120--1129, 2002.
[10]
C. Lampe, N. Ellison, and C. Steinfield. A face(book) in the crowd: social searching vs. social browsing. In Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, pages 167--170, New York, NY, USA, 2006.
[11]
M. J. Rattigan, M. Maier, and D. Jensen. Using structure indices for efficient approximation of network properties. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 357--366, New York, NY, USA, 2006.
[12]
S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 2nd edition, 2003.
[13]
R. Seidel. On the all-pairs-shortest-path problem. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 745--749, 1992.
[14]
E. Spertus, M. Sahami, and O. Buyukkokten. Evaluating similarity measures: a large-scale study in the orkut social network. In Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 678--684, New York, NY, USA, 2005.
[15]
M. Thorup and U. Zwick. Approximate distance oracles. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 183--192, New York, NY, USA, 2001.
[16]
U. Zwick. Exact and approximate distances in graphs - a survey. In Proceedings of the 9th Annual European Symposium on Algorithms, pages 33--48, London, UK, 2001.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management
November 2007
1048 pages
ISBN:9781595938039
DOI:10.1145/1321440
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. graphs
  2. shortest path
  3. social networks

Qualifiers

  • Research-article

Conference

CIKM07

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)1
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Distributed Landmark Labelling for Social NetworksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2025.105057(105057)Online publication date: Feb-2025
  • (2024)Aiding the resilience of cooperation through the use of network rankingsPLOS ONE10.1371/journal.pone.031319819:11(e0313198)Online publication date: 26-Nov-2024
  • (2024)Path Querying in Graph Databases: A Systematic Mapping StudyIEEE Access10.1109/ACCESS.2024.337197612(33154-33172)Online publication date: 2024
  • (2024)Distance queries over dynamic interval graphsComputational Geometry: Theory and Applications10.1016/j.comgeo.2024.102103122:COnline publication date: 18-Jul-2024
  • (2024)Hyper-distance oracles in hypergraphsThe VLDB Journal10.1007/s00778-024-00851-233:5(1333-1356)Online publication date: 19-Apr-2024
  • (2024)BatchHL: batch dynamic labelling for distance queries on large-scale networksThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00799-933:1(101-129)Online publication date: 1-Jan-2024
  • (2023)Towards Efficient Shortest Path Counting on Billion-Scale Graphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00198(2579-2592)Online publication date: Apr-2023
  • (2023)PSPC: Efficient Parallel Shortest Path Counting on Large-Scale Graphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00074(896-908)Online publication date: Apr-2023
  • (2023)Efficiently Answering Quality Constrained Shortest Distance Queries in Large Graphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00071(856-868)Online publication date: Apr-2023
  • (2023)Efficient maintenance of highway cover labelling for distance queries on large dynamic graphsWorld Wide Web10.1007/s11280-023-01146-226:5(2427-2452)Online publication date: 22-Mar-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media