Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

As online social networking emerges, there has been increased interest to utilize the underlying social structure as well as the available social information to improve search. In this paper, we focus on improving the performance of information collection from the neighborhood of a user in a dynamic social network. To this end, we introduce sampling based algorithms to quickly approximate quantities of interest from the vicinity of a user's social graph. We then introduce and analyze variants of this basic scheme exploring correlations across our samples. Models of centralized and distributed social networks are considered. We show that our algorithms can be utilized to rank items in the neighborhood of a user, assuming that information for each user in the network is available. Using real and synthetic data sets, we validate the results of our analysis and demonstrate the efficiency of our algorithms in approximating quantities of interest. The methods we describe are general and can probably be easily adopted in a variety of strategies aiming to efficiently collect information from a social graph.

REFERENCES

• 1: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, 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.1148177]
• 2: Eugene Agichtein , Eric Brill , Susan Dumais , Robert Ragno, Learning user interaction models for predicting web search result preferences, 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.1148175]
• 3: R. Albert and I. Barabasi. Statistical Mechanics of Complex Networks. Modern Physics Reviews, pages 47--97, 2002.
• 4: D. Aldous. On the markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probab. Engrg. Inform. Sci., 1(2):33--46, 1987.
• 5: Ziv Bar-Yossef , Alexander Berg , Steve Chien , Jittat Fakcharoenphol , Dror Weitz, Approximating Aggregate Queries about Web Pages via Random Walks, Proceedings of the 26th International Conference on Very Large Data Bases, p.535-544, September 10-14, 2000
• 6: Ziv Bar-Yossef , Maxim Gurevich, Random sampling from a search engine's index, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135833]
• 7: W. G. Cochran. Sampling Techniques, 3rd Edition. John Wiley, 1977.
• 8: C. T. G. Pass, A. Chowdhury. A Picture of Search. InfoScale, 2006.
• 9: Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
• 10: David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
• 11: Christos Gkantsidis , Milena Mihail , Amin Saberi, Random walks in peer-to-peer networks: algorithms and evaluation, Performance Evaluation, v.63 n.3, p.241-263, March 2006 [doi>10.1016/j.peva.2005.01.002]
• 12: W. Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1), 1970.
• 13: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 14: R. Impagliazzo , D. Zuckerman, How to recycle random bits, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.248-253, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63486]
• 15: R. G. Miller. Simultaneous Statistical Inference. Springer Verlag, Heidelberger, Berlin, 1981.
• 16: A. Mislove, K. P. Gummadi, and P. Druschel. Exploiting Social Networks for Internet Search. HotNets, 2006.
• 17: Jian-Tao Sun , Hua-Jun Zeng , Huan Liu , Yuchang Lu , Zheng Chen, CubeSVD: a novel approach to personalized Web search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060803]
• 18: Jaime Teevan , Susan T. Dumais , Eric Horvitz, Personalizing search via automated analysis of interests and activities, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076111]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

General Terms:
Algorithms, Human Factors, Performance

Keywords:
personalization, sampling social networks, social search