Random Surfer with Back Step

• Autorzy: Sydow M.
• Języki publikacji: EN

Abstrakty

EN

The World Wide Web with its billions of hyperlinked documents is a huge and important resource of information. There is a necessity of filtering this information. Link analysis of the Web graph turned out to be a powerful tool for automatically identifying authoritative documents. One of the best examples is the PageRank algorithm used in Google [1] to rank search results. In this paper we extend the model underlying the PageRank algorithm by incorporating "back button'' usage modeling in order to make the model less simplistic. We explain the existence and uniqueness of the ranking induced by the extended model. We also develop and implement an efficient approximation method for computing the novel ranking and present succesful experimental results made on 80- and 50- million page samples of the real Web.

Słowa kluczowe

EN

web information retrieval; link analysis; Page rank; back button modeling

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 68, nr 4
• Strony: 379--398
• Opis fizyczny: Bibliogr. 33 poz., wykr.

Twórcy

autor

Sydow M.

• Polish-Japanese Institute of Information Technology, Koszykowa 86, 02-008 Warsaw, Poland,

Bibliografia

• [1] Google Inc.
• [2] Broder, A., R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener: Graph Structure in the Web., Proceedings of the 9th WWW Conference, 2000.
• [3] Ding, C., X. He, P. Husbands, H. Zha, H. Simon: PageRank, Hits and a Unified Framework for Link Analysis, Lawrence Berkeley National Laboratory Technical Report 49372, 2001.
• [4] Fagin, R., A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, A. Tomkins: RandomWalks with Back Buttons, Annals of Applied Probability, 11(3), 2001.
• [5] Garfield, E.: Citation Analysis as a Tool in Journal Evaluation, Science, 178, 1972.
• [6] Golub, G., van Loan, C.: Matrix Computations, The Johns Hopkins University Press, 1996.
• [7] Greenberg, S., A. Cockburn: Getting Back to Back: Alternate Behaviors for a Web Browser’s Back Button, Proceedings of the 5th Annual Human Factors and the Web Conference, 1999.
• [8] Haveliwala, T.: Efficient Computation of PageRank, Stanford University Technical Report, 1999.
• [9] Haveliwala, T., S. Kamvar: The Second Eigenvalue of the Google Matrix, Stanford University Technical Report, 2003.
• [10] Haveliwala, T., S. Kamvar, D. Klein, C. Manning, G. Golub: Computing PageRank using Power Extrapolation, Stanford University Technical Report, 2003.
• [11] Henzinger, M.: Link analysis in web information retrieval., 23(3), 2000, 3-8.
• [12] Kamvar, S., T. Haveliwala, C. Manning, G. Golub: Exploiting the Block Structure of the Web for Computing PageRank, Stanford University Technical Report, 2003.
• [13] Kamvar, S., T. Haveliwala, G. Golub: Adaptive Methods for the Computation of PageRank, Proceedings of NSMC’03, 2003.
• [14] Katz., L.: A new status index derived from sociometric analysis., Psychometrika, 18, 1953.
• [15] Kessler, M.: Bibliographic Coupling Between Scientific Papers., American Documentation, 14, 1963.
• [16] Kleinberg, J.: Authoritative sources in a hyperlinked environment, Proceedings of the 9th ACM-SIAM Symposium on discrete algorithms, 1998.
• [17] Kleinberg, J., R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins: The Web as a graph: measurements, models and methods, Proceedings of the 5th Annual International Computing and Combinatorics Conference, 1999.
• [18] Klopotek, M., M. Sydow: Uncorrelating PageRank and In-Degree in a Synthetic Web Model, Proceedings of ISCIS’03, number 2869 in Lecture Notes of Computer Science, Springer Verlag, 2003.
• [19] Larson, R.: Bibliometrics of the world wide web: An exploratory analysis of the intellectual structure of cyberspace., Annual Meeting Of The American Society For Information Science, 1996.
• [20] Lempel, R., S. Moran: The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect, Proceedings of the 9th International WWW Conference, 2000.
• [21] Mathieu, F., Bouklit, M.: The Effect of the Back Button in a Random Walk: Application for PageRank, Proceedings of the 13th WWW Conference. Alternate Track. Papers and Posters, ACM Press, 2004.
• [22] Motwani, R., P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995.
• [23] Narin, F., G. Pinski: Citation Influence for Journal Aggregtes of scientific Publication: Theory, with Application to the Literature of Physics., Information Processing and Management, 12, 1976, 297-312.
• [24] Newman., M.: The structure of scientific collaboration networks., Proceedings Of The National Academy Of Sciences, 98(2), 2001.
• [25] Page, L., S. Brin, R. Motwani, T. Winograd: The PageRank citation ranking: Bringing order to the Web, Stanford Digital Library Working Paper, 1998.
• [26] Pandurangan, G., P. Raghavan, E. Upfal: Using PageRank to Characterize Web Structure, Proceedings of the 8th Annual International Computing and Combinatorics Conference, 2002.
• [27] S. Abiteboul, M. Preda, G. C.: Adaptive On-Line Page Importance Computation, Proceedings of the 12th International WWW Conference, 2003.
• [28] S. Chakrabarti, D. G., McCurley, K.: Surfing the web backwards., Computer Networks (Amsterdam, Netherlands), 31, 1999, 1679-1693.
• [29] Small, H.: Co-citation in the Scientific Literature: A New Measure of the Relationship Between Two Documents, J. Amer. Soc. Info. Sci., 24, 1973.
• [30] Sydow, M.: Approximation Quality of the RBS Ranking Algorithm, Intelligent Information Systems, Advances in Soft Computing, Springer-Verlag, 2004.
• [31] Sydow, M.: Link Analysis of the Web Graph. Measurements, Models and Algorithms for Web Information Retrieval, PhD dissertation, Polish Academy of Sciences, Institute of Computer Science, Warsaw, 2004.
• [32] Sydow, M.: Random Surfer with Back Step (poster), Proceedings of the 13th International WWW Conference, (Alternate Track. Papers and Posters), ACM press, 2004.
• [33] Sydow, M.: Can Link Analysis Tell Us about Web Traffic?, (to appear in) Proceedings of the 14th International World Wide Web Conference, (Alternate Track. Papers and Posters), ACM press, 2005.