skip to main content
10.1145/1055558.1055569acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

Using non-linear dynamical systems for web searching and ranking

Published: 14 June 2004 Publication History

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]
Y, Azar, A. Fiat, A. Karlin, F. McSherry, and J. Saia. Spectral analysis of data. In Proceedings of the 33rd Symposium on Theory of Computing (STOC 2001), Hersonissos, Crete, Greece, 2001.
[3]
K. Bharat and M. R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment. In Research and Development in Information Retrieval, pages 104--111, 1998.
[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]
A. Borodin, G. O. Roberts, J. S. Rosenthal, and P. Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, In Proceedings of the 10th International World Wide Web Conference, Hong Kong, 2001.
[6]
S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. In Proceedings of the 7th International World Wide Web Conference, Brisbane, Australia, 1998.
[7]
D. Cohn and H. Chang. Learning to probabilistically identify authoritative documents. In Proceedings of the 17th International Conference on Machine Learning, pages 167--174, Stanford University, 2000.
[8]
J. Dean and M. R. Henzinger. Finding related pages in the world wide web. In Proceedings of the Eighth International World-Wide Web Conference (WWW9), 1999.
[9]
R. L. Devaney. An Introduction to Chaotic Dynamical Systems. W. Benjamin, New York, 1986.
[10]
P, Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay. Clustering in large graphs and matrices. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999.
[11]
D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based on dynamical systems. In Proceedings of the 24th Intl. Conference on Very Large Databases (VLDB), 1998.
[12]
D. Gibson, J. Kleinberg, and P. Raghavan. Inferring web' communities from link topology. In Proceedings of 9th ACM Conference on Hypertext and Hypermedia, 1998.
[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]
J. Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 668--677, 1998.
[16]
R. Lempel and S. Moran. The stochastic approach for link-structure analysis (SALSA) and the TKC effect. In Proceedings of the 9th International World Wide Web Conference, May 2000.
[17]
A. Y. Ng, A. X. Zheng, and M. I. Jordan. Stable algorithms for link analysis. In Proceedings of the 24th International Conference on Research and Development in Information Retrieval (SIGIR 2001), New York, 2001.
[18]
D. Rafiei and A. Mendelzon. What is this page known for? Computing web page reputations. In Proceedings of the 9th International World Wide Web Conference, Amsterdam, Netherlands, 2000.
[19]
J. T. Sandefur. Discrete dynamical systems, Oxford: Clarendon Press, 1990.
[20]
P. Tsaparas, Link Analysis Ranking, PhD thesis, University of Toronto, 2004.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
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: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2014)The Design and Implementation of Database on the Full-Text Retrieval System of Multi DocumentApplied Mechanics and Materials10.4028/www.scientific.net/AMM.556-562.5964556-562(5964-5967)Online publication date: May-2014
  • (2014)Ranking Twitter discussion groupsProceedings of the second ACM conference on Online social networks10.1145/2660460.2660473(177-190)Online publication date: 1-Oct-2014
  • (2011)Random Walks in Social Networks and their Applications: A SurveySocial Network Data Analytics10.1007/978-1-4419-8462-3_3(43-77)Online publication date: 17-Mar-2011
  • (2009)Nonlinear static-rank computationProceedings of the 18th ACM conference on Information and knowledge management10.1145/1645953.1646056(807-816)Online publication date: 2-Nov-2009
  • (2009)Less is moreProceedings of the Second ACM International Conference on Web Search and Data Mining10.1145/1498759.1498832(242-251)Online publication date: 9-Feb-2009
  • (2009)Cluster Based Personalized SearchProceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph10.1007/978-3-540-95995-3_14(167-183)Online publication date: 12-Feb-2009
  • (2008)Analysis of Web Link Analysis Algorithms: The Mathematics of RankingInformation Access through Search Engines and Digital Libraries10.1007/978-3-540-75134-2_6(97-111)Online publication date: 2008
  • (2008)Ranking Links on the WebProceedings of the 21st international conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems: New Frontiers in Applied Artificial Intelligence10.1007/978-3-540-69052-8_21(199-208)Online publication date: 18-Jun-2008
  • (2008)Effects of different field weights on search performance in digital libraries: A preliminary studyProceedings of the American Society for Information Science and Technology10.1002/meet.145044023644:1(1-14)Online publication date: 29-Oct-2008
  • (2007)Measuring article quality in wikipediaProceedings of the sixteenth ACM conference on Conference on information and knowledge management10.1145/1321440.1321476(243-252)Online publication date: 6-Nov-2007
  • 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