research-article

Are web users really Markovian?

Authors:

Flavio Chierichetti,

Prabhakar Raghavan,

Tamas SarlosAuthors Info & Claims

WWW '12: Proceedings of the 21st international conference on World Wide Web

Pages 609 - 618

https://doi.org/10.1145/2187836.2187919

Published: 16 April 2012 Publication History

Abstract

User modeling on the Web has rested on the fundamental assumption of Markovian behavior --- a user's next action depends only on her current state, and not the history leading up to the current state. This forms the underpinning of PageRank web ranking, as well as a number of techniques for _targeting advertising to users. In this work we examine the validity of this assumption, using data from a number of Web settings. Our main result invokes statistical order estimation tests for Markov chains to establish that Web users are not, in fact, Markovian. We study the extent to which the Markovian assumption is invalid, and derive a number of avenues for further research.

References

[1]

P. Boldi, F. Bonchi, C. Castillo, D. Donato, A. Gionis, and S. Vigna. The query-flow graph: Model and applications. In 17th CIKM, 2008.

Digital Library

[2]

J. Borges and M. Levene. Evaluating variable-length Markov chain models for analysis of user web navigation sessions. IEEE TKDE, 2007.

Digital Library

[3]

P. Buhlmann and A. Wyner. Variable length Markov chains. Annals of Statistics, 1999.

[4]

H. Cao, D. Jiang, J. Pei, E. Chen, and H. Li. Towards context-aware search by learning a very large variable length hidden Markov model from search logs. In 18th WWW, 2009.

Digital Library

[5]

N. Craswell and M. Szummer. Random walks on the click graph. In 30th SIGIR, 2007.

Digital Library

[6]

I. Csiszár and P. Shields. The consistency of the BIC Markov order estimator. Annals of Statistics, 2000.

[7]

D. Dalevi, D. Dubhashi, and M. Hermansson. A new order estimator for fixed and variable length Markov models with applications to DNA sequence similarity. Statistical Applications in Genetics and Molecular Biology, 2006.

[8]

B. Davison. Learning web request patterns. Web Dynamics, 2004.

[9]

M. Deshpande and G. Karypis. Selective Markov models for predicting web page accesses. ACM TOIT, 2004.

Digital Library

[10]

I. Holyer. The NP-completeness of some edge-partition problems. SICOMP, 1981.

[11]

J. Kemeny and J. Snell. Finite Markov Chains. van Nostrand, 1960.

[12]

R. Lempel and S. Moran. SALSA: The stochastic approach for link-structure analysis. ACM TOIS, 2001.

Digital Library

[13]

Z. Li and J. Tian. Testing the suitability of Markov chains as web usage models. In COMPSAC 2003, 2003.

Digital Library

[14]

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.

[15]

Y. Peres and P. Shields. Two new Markov order estimators. Arxiv Preprint Math/0506080, 2005.

[16]

P. Pirolli and J. Pitkow. Distributions of surfers' paths through the World Wide Web: Empirical characterizations. WWW, 1999.

Digital Library

[17]

J. Rissanen. A universal data compression system. IEEE Trans. on Inf. Theory, 1983.

[18]

D. Ron, Y. Singer, and N. Tishby. The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning, 1996.

Digital Library

[19]

R. Sarukkai. Link prediction and path analysis using Markov chains. Computer Networks, 2000.

Digital Library

[20]

R. Sen and M. Hansen. Predicting web users' next access based on log data. JCGS, 2003.

[21]

I. Zukerman, D. Albrecht, and A. Nicholson. Predicting users' requests on the WWW. In 7th UM, 1999.

Digital Library

Cited By

Feng ZZhu FWang HHao JYang SZeng WQu H(2024)HoLens: A visual analytics design for higher-order movement modeling and visualizationComputational Visual Media10.1007/s41095-023-0392-y10:6(1079-1100)Online publication date: 21-Sep-2024
https://doi.org/10.1007/s41095-023-0392-y
Danassis PVerma SKillian JTaneja ATambe MElkind E(2023)Limited resource allocation in a non-Markovian worldProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/660(5950-5958)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/660
Piccardi TGerlach MArora AWest R(2023)A Large-Scale Characterization of How Readers Browse WikipediaACM Transactions on the Web10.1145/358031817:2(1-22)Online publication date: 3-Apr-2023
https://dl.acm.org/doi/10.1145/3580318
Show More Cited By

Index Terms

Are web users really Markovian?
1. Mathematics of computing
  1. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Web designers and web users: Influence of the ergonomic quality of the web site on the information search

Despite rapid growth in the number of web sites, there is still a significant number of ergonomic problems which hinder web users. Many studies focus on analysing cognitive processes and difficulties experienced by web users, but very few are interested ...
Web browsing behavior recording system
KES'11: Proceedings of the 15th international conference on Knowledge-based and intelligent information and engineering systems - Volume Part IV

In this paper, we introduce a Web browsing behavior recording system for research. Web browsing behavior data can help us to provide sophisticated services for human activities, because the data must indicate characteristics of Web users. We discuss the ...
Users' conceptions of web security: a comparative study
CHI EA '02: CHI '02 Extended Abstracts on Human Factors in Computing Systems

This study characterizes users' conceptions of web security. Seventy-two individuals, 24 each from a rural community in Maine, a suburban professional community in New Jersey, and a high-technology community in California, participated in an extensive (...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '12: Proceedings of the 21st international conference on World Wide Web

April 2012

1078 pages

ISBN:9781450312295

DOI:10.1145/2187836

General Chairs:
Alain Mille
Université de Lyon, France
,
Fabien Gandon
INRIA, France
,
Jacques Misselis
HP, France
,
Program Chairs:
Michael Rabinovich
Case Western Reserve University, USA
,
Steffen Staab
University of Koblenz-Landau, Germany

Copyright © 2012 ACM.

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

Univ. de Lyon: Universite de Lyon

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 April 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW 2012

Sponsor:

Univ. de Lyon

WWW 2012: 21st World Wide Web Conference 2012

April 16 - 20, 2012

Lyon, France

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
903
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)2

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Feng ZZhu FWang HHao JYang SZeng WQu H(2024)HoLens: A visual analytics design for higher-order movement modeling and visualizationComputational Visual Media10.1007/s41095-023-0392-y10:6(1079-1100)Online publication date: 21-Sep-2024
https://doi.org/10.1007/s41095-023-0392-y
Danassis PVerma SKillian JTaneja ATambe MElkind E(2023)Limited resource allocation in a non-Markovian worldProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/660(5950-5958)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/660
Piccardi TGerlach MArora AWest R(2023)A Large-Scale Characterization of How Readers Browse WikipediaACM Transactions on the Web10.1145/358031817:2(1-22)Online publication date: 3-Apr-2023
https://dl.acm.org/doi/10.1145/3580318
Spaeh FTsourakakis C(2023)Learning Mixtures of Markov Chains with Quality GuaranteesProceedings of the ACM Web Conference 202310.1145/3543507.3583524(662-672)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583524
Gote CCasiraghi GSchweitzer FScholtes I(2023)Predicting variable-length paths in networked systems using multi-order generative modelsApplied Network Science10.1007/s41109-023-00596-x8:1Online publication date: 22-Sep-2023
https://doi.org/10.1007/s41109-023-00596-x
Ling XBui ABrooks P(2023)Kernel $$\ell ^1$$-norm principal component analysis for denoisingOptimization Letters10.1007/s11590-023-02051-318:9(2133-2148)Online publication date: 25-Sep-2023
https://doi.org/10.1007/s11590-023-02051-3
ELMASTAŞ GÜLTEKİN ÖKILIÇ AÖZÇELİK KAYSERİ G(2022)Stochastic Modelling of Pilling Degree Changes During the Pilling Process of Wool FabricsTekstil ve Konfeksiyon10.32710/tekstilvekonfeksiyon.97402632:1(65-76)Online publication date: 29-Mar-2022
https://doi.org/10.32710/tekstilvekonfeksiyon.974026
Arora AGerlach MPiccardi TGarcía-Durán AWest RSelcuk Candan KLiu HAkoglu LLuna Dong XTang J(2022)Wikipedia Reader NavigationProceedings of the Fifteenth ACM International Conference on Web Search and Data Mining10.1145/3488560.3498496(16-26)Online publication date: 11-Feb-2022
https://dl.acm.org/doi/10.1145/3488560.3498496
Petrovic LScholtes I(2022)Learning the Markov Order of Paths in GraphsProceedings of the ACM Web Conference 202210.1145/3485447.3512091(1559-1569)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1145/3485447.3512091
Cifci EGokturk M(2022)Predictivity of Category Based Human Navigation and the Effect of Navigation Path Length on the Prediction Accuracy in Knowledge Networks2022 International Conference on Communications, Information, Electronic and Energy Systems (CIEES)10.1109/CIEES55704.2022.9990641(1-6)Online publication date: 24-Nov-2022
https://doi.org/10.1109/CIEES55704.2022.9990641
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents

NODES