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

ABSTRACT

In the recent years there has been a surge of research activity in the area of information retrieval on the World Wide Web, using link analysis of the underlying hypertext graph topology. Most of the algorithms in the literature can be described as dynamical systems, that is, the repetitive application of a function on a set of weights. Algorithms that rely on eigenvector computations, such as HITS and PAGERANK, correspond to linear dynamical systems. In this work we consider two families of link analysis ranking algorithms that no longer enjoy the linearity property of the previous approaches. We study in depth an interesting special case of these two families. We prove that the corresponding non-linear dynamical system converges for any initialization, and we provide a rigorous characterization of the combinatorial properties of the stationary weights. The study of the weights provides a clear and insightful view of the mechanics of the algorithm. We also present extensive experimental results that demonstrate that our algorithm performs well in practice.

REFERENCES

• 1: D. Achlioptas, A. Fiat, A. Karlin, and F. McSherry. Web search through hub synthesis. In Proceedings of the 42nd Foundation of Computer Science (FOCS 2001), Las Vegas, Nevada, 2001.
• 2: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 3: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 4: M. Bianchini, M. Gori, and F. Scarselli. Pagerank: A circuital analysis. In Proceedings of the Eleventh International World Wide Web (WWW) Conference, 2002
• 5: Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, Proceedings of the 10th international conference on World Wide Web, p.415-429, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372096]
• 6: 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
• 7: David Cohn , Huan Chang, Learning to Probabilistically Identify Authoritative Documents, Proceedings of the Seventeenth International Conference on Machine Learning, p.167-174, June 29-July 02, 2000
• 8: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 9: R. L. Devaney. An Introduction to Chaotic Dynamical Systems. W. Benjamin, New York, 1986.
• 10: P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
• 11: David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998
• 12: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 13: T. H. Haveliwala, A. Gionis, D. Klein, and P. Indyk. Similarity search on the Web: Evaluation and scalability considerations. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), 2002.
• 14: Thomas Hofmann. Probabilistic latent semantic analysis. In Proc. of Uncertainty in Artificial Intelligence, UAl'99, Stockholm, 1999.
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 16: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.387-401, June 2000, Amsterdam, The Netherlands
• 17: Andrew Y. Ng , Alice X. Zheng , Michael I. Jordan, Stable algorithms for link analysis, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.258-266, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384003]
• 18: Davood Rafiei , Alberto O. Mendelzon, What is this page known for? Computing Web page reputations, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.823-835, June 2000, Amsterdam, The Netherlands
• 19: James T. Sandefur, Discrete dynamical systems: theory and applications, Clarendon Press, New York, NY, 1990
• 20: Panayiotis Tsaparas , Allan Borodin, Link analysis ranking, 2004