Philipp Singer
Denis Helic
Markus Strohmaier
ABSTRACT
When users interact with the Web today, they leave sequential digital trails on a massive scale. Examples of such human trails include Web navigation, sequences of online restaurant reviews, or online music play lists. Understanding the factors that drive the production of these trails can be useful for e.g., improving underlying network structures, predicting user clicks or enhancing recommendations. In this work, we present a general approach called HypTrails for comparing a set of hypotheses about human trails on the Web, where hypotheses represent beliefs about transitions between states. Our approach utilizes Markov chain models with Bayesian inference. The main idea is to incorporate hypotheses as informative Dirichlet priors and to leverage the sensitivity of Bayes factors on the prior for comparing hypotheses with each other. For eliciting Dirichlet priors from hypotheses, we present an adaption of the so-called (trial) roulette method. We demonstrate the general mechanics and applicability of HypTrails by performing experiments with (i) synthetic trails for which we control the mechanisms that have produced them and (ii) empirical trails stemming from different domains including website navigation, business reviews and online music played. Our work expands the repertoire of methods available for studying human trails on the Web.
- D. Achlioptas. Database-friendly random projections. In Symposium on Principles of Database Systems, pages 274--281. ACM, 2001. Google Scholar
Digital Library
- J. An, D. Quercia, and J. Crowcroft. Partisan sharing: facebook evidence and societal consequences. In Conference on Online Social Networks, pages 13--24. ACM, 2014. Google ScholarDigital Library
- A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.Google ScholarCross Ref
- T. Berners-Lee and M. Fischetti. Weaving the Web: The original design and ultimate destiny of the World Wide Web by its inventor. Harper Information, 2000. Google ScholarDigital Library
- M. Bilenko and R. W. White. Mining the search trails of surfing crowds: identifying relevant websites from user activity. In International Conference on World Wide Web, pages 51--60. ACM, 2008. Google ScholarDigital Library
- J. Borges and M. Levene. Data mining of user navigation patterns. In Web usage analysis and user profiling, pages 92--112. Springer, 2000. Google ScholarDigital Library
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In International Conference on World Wide Web, pages 107--117. Elsevier Science Publishers B. V., 1998. Google ScholarDigital Library
- D. P. Brumby and A. Howes. Good enough but i'll just check: Web-page search as attentional refocusing. In International Conference on Cognitive Modeling, pages 46--51, 2004.Google Scholar
- V. Bush. As we may think. The Atlantic Monthly, 176(1):101--108, 1945.Google Scholar
- L. D. Catledge and J. E. Pitkow. Characterizing browsing strategies in the world-wide web. Computer Networks and ISDN Systems, 27(6):1065--1073, 1995. Google ScholarDigital Library
- O. Celma. Music Recommendation and Discovery in the Long Tail. Springer, 2010. Google ScholarDigital Library
- M. Chalmers, K. Rodden, and D. Brodbeck. The order of things: activity-centred information access. Computer Networks and ISDN Systems, 30(1):359--367, 1998. Google ScholarDigital Library
- E. H. Chi, P. L. T. Pirolli, K. Chen, and J. Pitkow. Using information scent to model user information needs and actions and the web. In Conference on Human Factors in Computing Systems, pages 490--497. ACM, 2001. Google ScholarDigital Library
- F. Chierichetti, R. Kumar, P. Raghavan, and T. Sarlos. Are web users really markovian? In International Conference on World Wide Web, pages 609--618. ACM, 2012. Google ScholarDigital Library
- S. Dasgupta and A. Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60--65, 2003. Google ScholarDigital Library
- C. Davidson-Pilon. Probablistic Programming & Bayesian Methods for Hackers. 2014.Google Scholar
- M. Deshpande and G. Karypis. Selective markov models for predicting web page accesses. ACM Transactions on Internet Technology, 4(2):163--184, May 2004. Google ScholarDigital Library
- P. H. Garthwaite, J. B. Kadane, and A. O'Hagan. Statistical methods for eliciting probability distributions. Journal of the American Statistical Association, 100(470):680--701, 2005.Google ScholarCross Ref
- S. Gore. Biostatistics and the medical research council. Medical Research Council News, 35:19--20, 1987.Google Scholar
- B. A. Huberman, P. L. T. Pirolli, J. E. Pitkow, and R. M. Lukose. Strong regularities in world wide web surfing. Science, 280(5360):95--97, Mar 1998.Google ScholarCross Ref
- R. E. Kass and A. E. Raftery. Bayes factors. Journal of the American Statistical Association, 90(430):773--795, 1995.Google ScholarCross Ref
- S. Laxman, V. Tankasali, and R. W. White. Stream prediction using a generative model based on frequent episodes in event sequences. In International Conference on Knowledge Discovery and Data Mining, pages 453--461. ACM, 2008. Google ScholarDigital Library
- R. Lempel and S. Moran. The stochastic approach for link-structure analysis (salsa) and the tkc effect. Computer Networks, 33(1):387--401, June 2000. Google ScholarDigital Library
- P. Li, T. J. Hastie, and K. W. Church. Very sparse random projections. In International Conference on Knowledge Discovery and Data Mining, pages 287--296. ACM, 2006. Google ScholarDigital Library
- C. D. Manning, P. Raghavan, and H. Schütze. Introduction to information retrieval, volume 1. Cambridge university press Cambridge, 2008. Google ScholarDigital Library
- Y. Matsubara, Y. Sakurai, C. Faloutsos, T. Iwata, and M. Yoshikawa. Fast mining and forecasting of complex time-stamped events. In International Conference on Knowledge Discovery and Data Mining, pages 271--279. ACM, 2012. Google ScholarDigital Library
- T. H. Nelson. Complex information processing: a file structure for the complex, the changing and the indeterminate. In National Conference, pages 84--100. ACM, 1965. Google ScholarDigital Library
- J. Oakley. Eliciting univariate probability distributions. Rethinking Risk Measurement and Reporting, 1, 2010.Google Scholar
- B. J. Pierce, S. R. Parkinson, and N. Sisson. Effects of semantic similarity, omission probability and number of alternatives in computer menu search. International Journal of Man-Machine Studies, 37(5):653--677, 1992. Google ScholarDigital Library
- P. L. T. Pirolli and S. K. Card. Information foraging. Psychological Review, 106(4):643--675, 1999.Google ScholarCross Ref
- P. L. T. Pirolli and J. E. Pitkow. Distributions of surfers? paths through the world wide web: Empirical characterizations. World Wide Web, 2(1-2):29--45, Jan 1999. Google ScholarDigital Library
- D. d. S. Price. A general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information Science, 27(5):292--306, 1976.Google ScholarCross Ref
- H. Rubenstein and J. B. Goodenough. Contextual correlates of synonymy. Communications of the ACM, 8(10):627--633, 1965. Google ScholarDigital Library
- G. Salton and C. Buckley. Term-weighting approaches in automatic text retrieval. Information Processing & Management, 24(5):513--523, 1988. Google ScholarDigital Library
- P. Singer, D. Helic, B. Taraghi, and M. Strohmaier. Detecting memory and structure in human navigation patterns using markov chain models of varying order. PloS one, 9(7):e102070, 2014.Google ScholarCross Ref
- P. Singer, T. Niebler, M. Strohmaier, and A. Hotho. Computing semantic relatedness from human navigational paths: A case study on wikipedia. International Journal on Semantic Web and Information Systems, 9(4):41--70, 2013. Google ScholarDigital Library
- R. W. Sinnott. Virtues of the haversine. Sky and Telescope, 68(2):158, 1984.Google Scholar
- C. C. Strelioff, J. P. Crutchfield, and A. W. Hübler. Inferring markov chains: Bayesian estimation, model comparison, entropy rate, and out-of-class modeling. Physical Review E, 76(1):011106, Jul 2007.Google ScholarCross Ref
- W. Vanpaemel. Prior sensitivity in theory testing: An apologia for the bayes factor. Journal of Mathematical Psychology, 54(6):491--498, 2010.Google ScholarCross Ref
- W. Vanpaemel. Constructing informative model priors using hierarchical methods. Journal of Mathematical Psychology, 55(1):106--117, 2011.Google ScholarCross Ref
- W. Vanpaemel and M. D. Lee. Using priors to formalize theory: Optimal attention and the generalized context model. Psychonomic Bulletin & Review, 19(6):1047--1056, 2012.Google ScholarCross Ref
- S. Walk, P. Singer, and M. Strohmaier. Sequential action patterns in collaborative ontology-engineering projects: A case-study in the biomedical domain. In International Conference on Conference on Information & Knowledge Management. ACM, 2014. Google ScholarDigital Library
- S. Walk, P. Singer, M. Strohmaier, T. Tudorache, M. A. Musen, and N. F. Noy. Discovering beaten paths in collaborative ontology-engineering projects using markov chains. Journal of Biomedical Informatics, 51:254--271, 2014.Google ScholarDigital Library
- L. Wasserman. Bayesian model selection and model averaging. Journal of Mathematical Psychology, 44(1):92--107, 2000. Google ScholarDigital Library
- R. West and J. Leskovec. Human wayfinding in information networks. In International Conference on World Wide Web, pages 619--628. ACM, 2012. Google ScholarDigital Library
- R. West, J. Pineau, and D. Precup. Wikispeedia: An online game for inferring semantic distances between concepts. In International Joint Conference on Artificial Intelligence, pages 1598--1603. Morgan Kaufmann Publishers Inc., 2009. Google ScholarDigital Library
- R. W. White and J. Huang. Assessing the scenic route: measuring the value of search trails in web logs. In Conference on Research and Development in Information Retrieval, pages 587--594. ACM, 2010. Google ScholarDigital Library
- W. Xie, P. O. Lewis, Y. Fan, L. Kuo, and M.-H. Chen. Improving marginal likelihood estimation for bayesian phylogenetic model selection. Systematic Biology, 60(2):150--160, 2010.Google ScholarCross Ref
- J. Yang, J. McAuley, J. Leskovec, P. LePendu, and N. Shah. Finding progression stages in time-evolving event sequences. In International Conference on World Wide Web, pages 783--794. ACM, 2014. Google ScholarDigital Library
Index Terms
- HypTrails: A Bayesian Approach for Comparing Hypotheses About Human Trails on the Web
Recommendations
SparkTrails: A MapReduce Implementation of HypTrails for Comparing Hypotheses About Human Trails
WWW '16 Companion: Proceedings of the 25th International Conference Companion on World Wide WebHypTrails is a bayesian approach for comparing different hypotheses about human trails on the web. While a standard implementation exists, it exposes performance issues when working with large-scale data. In this paper, we propose a distributed ...
A Bayesian Method for Comparing Hypotheses About Human Trails
When users interact with the Web today, they leave sequential digital trails on a massive scale. Examples of such human trails include Web navigation, sequences of online restaurant reviews, or online music play lists. Understanding the factors that ...
A Bayesian Independence Test for Small Datasets
We propose a Bayesian test for independence among signals where only a small dataset is available. Traditional frequentist approaches often fail in this case due to inaccurate estimation of either the source statistical models or the threshold used by ...
Comments