Monique V. Vieira
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.
- R. A. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999. Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269--271,1959.Google ScholarDigital Library
- D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740--1759, 2000. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- M. Holzer, F. Schulz, D. Wagner, and T. Willhalm. Combining speed-up techniques for shortest-path computations. Journal of Experimental Algorithmics, 10, 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 2nd edition, 2003. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
Index Terms
- Efficient search ranking in social networks
Recommendations
To Enhance Web Search Based on Topic Sensitive_Social Relationship Ranking Algorithm in Social Networks
WI-IAT '09: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 03Social Network Services(SNS) such as Facebook, Friendster, MySpace and Orkut have established themselves as very popular and powerful tools for making and finding friends and for identifying other people who share similar interests. Search behavior of ...
Evolving social search based on bookmarks and status messages from social networks
CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge managementSocial search is a variant of information retrieval where a document or website is considered relevant if individuals from the searcher's social network have interacted with it. Our ranking metric Social Relevance Score (SRS) is based on two factors. ...
Social Search: Exploring and Searching Social Architectures in Digital Networks
Content authors are increasingly using the Internet to network, providing each other with advice, collaboratively filtering important information, and creating virtual networks of trust. To adequately understand this social cyberspace, we must be able ...
Comments