Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Levene, Mark; Loizou, George (2003)
Publisher: World Scientific Publishing Company
Languages: English
Types: Article
Subjects: csis
Navigation through the web, colloquially known as "surfing", is one of the main activities of users during web interaction. When users follow a navigation trail they often tend to get disoriented in terms of the goals of their original query and thus the discovery of typical user trails could be useful in providing navigation assistance. Herein, we give a theoretical underpinning of user navigation in terms of the entropy of an underlying Markov chain modelling the web topology. We present a novel method for online incremental computation of the entropy and a large deviation result regarding the length of a trail to realize the said entropy. We provide an error analysis for our estimation of the entropy in terms of the divergence between the empirical and actual probabilities. We then indicate applications of our algorithm in the area of web data mining. Finally, we present an extension of our technique to higher-order Markov chains by a suitable reduction of a higher-order Markov chain model to a first-order one.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • P. Billingsley. Statistical methods in Markov chains. The Annals of Mathematical Statistics, 32:12{40, 1961.
    • J. Borges and M. Levene. Data mining of user navigation patterns. In B. Masand and M. Spiliopoulou, editors, Web Usage Analysis and User Pro¯ling, Lecture Notes in Arti¯cial Intelligence (LNAI 1836), pages 92{111. Springer-Verlag, Berlin, 2000.
    • T. Bell and A. Mo®at. A note on the DMC data compression scheme. The Computer Journal, 32:16{20, 1989.
    • V. Bush. As we may think. Atlantic Monthly, 176:101{108, 1945.
    • T. Bell, I.H. Witten, and J.G. Cleary. Modeling for text compression. ACM Computing Surveys, 21:557{591, 1989.
    • [CDK+99] S. Chakrabarti, B. Dom, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, D. Gibson, and J.M. Kleinberg. Mining the web's link structure. IEEE Computer, 32:60{67, 1999.
    • In Proceedings of International World Wide Web Conference, pages 161{172, Brisbane, 1998.
    • G.V. Cormack and R.N.S. Horspool. Data compression using dynamic Markov modelling. The Computer Journal, 30:541{550, 1987.
    • C. Chat¯eld. Statistical inference regarding Markov chain models. Applied Statistics, 22:7{20, 1973.
    • IEEE Transactions on Knowledge and Data Engineering, 10:209{221, 1998.
    • [HHMN99] M.R. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork. Measuring index quality using random walks on the web. In Proceedings of International World Wide Web Conference, pages 1291{1303, Montreal, 1999.
    • R.A. Horn and C.R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge, U.K., 1985.
    • American Statistical Association Journal, 58:13{30, 1963.
    • [HPPL98] B.A. Huberman, P.L.T. Pirolli, J.E. Pitkow, and R.M. Lukose. Strong regularities in world wide web sur¯ng. Science, 280:95{97, 1998.
    • M. Levene and G. Loizou. Kemeny's constant and the random surfer. American Mathematical Monthly, 109:741{745, 2002.
    • M. Levene and G. Loizou. Web interaction and the navigation problem in hypertext. In A. Kent, J.G. Williams, and C.M. Hall, editors, Encyclopedia of Microcomputers, pages 381{398. Marcel Dekker, New York, NY, 2002.
    • C. McDiarmid. On the method of bounded di®erences. In J. Siemons, editor, Surveys in Combinatorics, volume 141 of London Mathematical Society Lecture Note Series, pages 148{188. Cambridge University Press, Cambridge, U.K., 1989.
    • N. Merhav, M. Gutman, and J. Ziv. On the estimation of the order of a Markov chain and universal data compression. IEEE Transactions on Information Theory, 35:1014{1019, 1989.
    • G.A. Miller. Note on the bias of information estimates. In H. Quastler, editor, Information Theory in Psychology: Problems and Methods, pages 95{100. Free Press, Glencoe, Il., 1955.
    • J. Nielsen. Hypertext and Hypermedia. Academic Press, Boston, Ma., 1990.
    • T. Oren. Memex: Getting back on the trail. In J.M. Nyce and P. Kahn, editors, From Memex to Hypertext: Vannevar Bush and the Mind's Machine, pages 319{ 338. Academic Press, San Diego, Ca., 1991.
    • G. Pinski and F. Narin. Citation in°uence for journal aggregates of scienti¯c publications: Theory, with application to the literature of physics. Information Processing & Management, 12:297{312, 1976.
    • P. Pirolli and J.E. Pitkow. Distributions of surfers' paths through the world wide web: Empirical characterizations. World Wide Web, 2:29{45, 1999.
    • J. Rissanen. Complexity of strings in the class of Markov sources. IEEE Transactions on Information Theory, 32:526{532, 1986.
    • J.S. Rosenthal. Convergence rates of Markov chains. SIAM Review, 37:387{405, 1995.
    • C.E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:379{423, 623{656, 1948.
    • S. Schechter, M. Krishnan, and M.D. Smith. Using path pro¯les to predict HTTP requests. Computer Networks and ISDN Systems, 30:457{467, 1998.
    • [TR93] I. Sonin. The state reduction and related algorithms and their applications in the study of Markov chains, graph theory, and the optimal stopping problem.
    • Advances in Mathematics, 145:159{188, 1999.
    • The Computer Journal, 36:607{614, 1993.
    • [WZW98] A.D. Wyner, J. Ziv, and A.J. Wyner. On the role of pattern matching in information theory. IEEE Transactions on Information Theory, 44:2045{2056, 1998.
    • N. Zin and M. Levene. Constructing web views from automated navigation sessions. In Proceedings of ACM Digital Library Workshop on Organizing Web Space (WOWS), pages 54{58, Berkeley, Ca., 1999.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article