skip to main content
10.1145/1772690.1772716acmotherconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Stochastic models for tabbed browsing

Published: 26 April 2010 Publication History

Abstract

We present a model of tabbed browsing that represents a hybrid between a Markov process capturing the graph of hyperlinks, and a branching process capturing the birth and death of tabs. We present a mathematical criterion to characterize whether the process has a steady state independent of initial conditions, and we show how to characterize the limiting behavior in both cases. We perform a series of experiments to compare our tabbed browsing model with pagerank, and show that tabbed browsing is able to explain 15-25% of the deviation between actual measured browsing behavior and the behavior predicted by the simple pagerank model. We find this to be a surprising result, as the tabbed browsing model does not make use of any notion of site popularity, but simply captures deviations in user likelihood to open and close tabs from a particular node in the graph.

References

[1]
N. Alon, C. Avin, M. Koucký, G. Kozma, and Z. Lotker. Many random walks are faster than one. In Proc. 20th SPAA, pages 119--128, 2008.
[2]
K. B. Athreya and P. E. Ney. Branching Processes. Dover Publications, Inc., New York, 2004.
[3]
R. A. Baeza-Yates, P. Boldi, and C. Castillo. Generic damping functions for propagating importance in link-based ranking. Internet Mathematics, 3(4):445--478, 2007.
[4]
Z. Bar-Yossef, A. Z. Broder, R. Kumar, and A. Tomkins. Sic transit gloria telae: Towards and understanding of the web's decay. In Proc. 13th WWW, pages 328--337, 2004.
[5]
A. Benczur, K. Csalogany, T. Sarlos, and M. Uher. Spamrank - fully automatic link spam detection. Proc. 1st AIRWeb, pages 1--14, 2005.
[6]
P. Berkhin. A survey on pagerank computing. Internet Mathematics, 2(1):73--120, 2005.
[7]
P. Boldi, M. Santini, and S. Vigna. A deeper investigation of pagerank as a function of the damping factor. In Web Information Retrieval & Linear Algebra Algorithms, 2007.
[8]
A. Borodin, G. O. Roberts, J. S. Rosenthal, and P. T. P. Link analysis ranking: Algorithms, theory, and experiments. ACM TOIT, 5:231--297, 2005.
[9]
M. Bouklit and F. Mathieu. BackRank: An alternative for PageRank? In Proc. 14th WWW (Special interest tracks and posters), pages 1122--1123, 2005.
[10]
S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1-7):107--117, 1998.
[11]
K. Efremenko and O. Reingold. How well do random walks parallelize? In Proc. 12th APPROX--RANDOM, pages 479--489, 2009.
[12]
R. Elsasser and T. Sauerwald. Tight bounds for the cover time of multiple random walks. In Proc. 36th ICALP, pages 415--426, 2009.
[13]
K. Etessami and M. Yannakakis. Recursive Markov chains: Stochastic grammars, and monotone systems of nonlinear equations. J. ACM, 56(1), 2009.
[14]
R. Fagin, A. R. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins. Random walks with "back buttons". Annals of Applied Probability, 11(3):810--862, 2001.
[15]
W. Feller. An Introduction to Probability Theory and Its Applications, Volume 1. Wiley, 1968.
[16]
B. Gonçalves, M. R. Meiss, J. J. Ramas, A. Flammini, and F. Menczer. Remembering what we like: Toward an agent-based model of web traffic. In Proc. 2nd WSDM (Late Breaking Results), 2009.
[17]
Z. Gyongi, H. Garcia-Molina, and J. Pedersen. Combating web spam with TrustRank. In Proc. 30th VLDB, pages 576--587, 2004.
[18]
T. H. Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. TKDE, 15(4):784--796, 2003.
[19]
A. N. Langville and C. D. Meyer. Deeper inside PageRank. Internet Mathematics, 1(3):335--380, 2005.
[20]
R. Lempel and S. Moran. SALSA: The stochastic approach for link-structure analysis. ACM TOIS, 19(2):131--160, 2001.
[21]
Y. Liu, B. Gao, T.-Y. Liu, Y. Zhang, Z. Ma, S. He, and H. Li. Browserank: Letting web users vote for page importance. In Proc. 31st SIGIR, pages 451--458, 2008.
[22]
M. Meiss, J. Duncan, B. Gonçalves, J. J. Ramasco, and F. Menczer. What's in a session: Tracking individual behavior on the web. In Proc. 20th Hypertext, pages 173--182, 2009.
[23]
L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[24]
E. Seneta. Non-negative Matrices and Markov Chains. Springer, 1973.
[25]
M. Sydow. Randoms surfer with back step. In Proc. 13th WWW (Special interest tracks and posters), pages 352--353, 2004.
[26]
P. Tsaparas. Link Analysis Ranking Algorithms. PhD thesis, University of Toronto, 2003.
[27]
M. Viermetz, C. Stolz, V. Gedov, and M. Skubacz. Relevance and impact of tabbed browsing behavior on web usage mining. In Proc. WI, pages 262--269, 2006.

Cited By

View all
  • (2016)Identifying User Actions from HTTP(S) Traffic2016 IEEE 41st Conference on Local Computer Networks (LCN)10.1109/LCN.2016.91(555-558)Online publication date: Nov-2016
  • (2015)Methods for web revisitation predictionUser Modeling and User-Adapted Interaction10.1007/s11257-015-9161-725:4(331-369)Online publication date: 1-Oct-2015
  • (2015)Conducting a Web Browsing Behaviour Study --- An Educational ScenarioProceedings of the 41st International Conference on SOFSEM 2015: Theory and Practice of Computer Science - Volume 893910.1007/978-3-662-46078-8_44(531-542)Online publication date: 24-Jan-2015
  • Show More Cited By

Index Terms

  1. Stochastic models for tabbed browsing

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    WWW '10: Proceedings of the 19th international conference on World wide web
    April 2010
    1407 pages
    ISBN:9781605587998
    DOI:10.1145/1772690

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 26 April 2010

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. branching process
    2. convergence
    3. random walks
    4. stationary distribution
    5. tabbed browsing

    Qualifiers

    • Research-article

    Conference

    WWW '10
    WWW '10: The 19th International World Wide Web Conference
    April 26 - 30, 2010
    North Carolina, Raleigh, USA

    Acceptance Rates

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

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2016)Identifying User Actions from HTTP(S) Traffic2016 IEEE 41st Conference on Local Computer Networks (LCN)10.1109/LCN.2016.91(555-558)Online publication date: Nov-2016
    • (2015)Methods for web revisitation predictionUser Modeling and User-Adapted Interaction10.1007/s11257-015-9161-725:4(331-369)Online publication date: 1-Oct-2015
    • (2015)Conducting a Web Browsing Behaviour Study --- An Educational ScenarioProceedings of the 41st International Conference on SOFSEM 2015: Theory and Practice of Computer Science - Volume 893910.1007/978-3-662-46078-8_44(531-542)Online publication date: 24-Jan-2015
    • (2013)Online multitasking and user engagementProceedings of the 22nd ACM international conference on Information & Knowledge Management10.1145/2505515.2505543(519-528)Online publication date: 27-Oct-2013
    • (2013)Search behaviour on photo sharing platforms2013 IEEE International Conference on Multimedia and Expo (ICME)10.1109/ICME.2013.6607496(1-6)Online publication date: Jul-2013
    • (2012)Considerations for recruiting contributions to anonymised data setsInternational Journal of Technology Enhanced Learning10.1504/IJTEL.2012.0483154:1/2(85-98)Online publication date: 1-Jul-2012
    • (2012)No search result left behindProceedings of the fifth ACM international conference on Web search and data mining10.1145/2124295.2124322(203-212)Online publication date: 8-Feb-2012
    • (2012)Modeling parallel web browsing behavior for web-based educational systems2012 IEEE 10th International Conference on Emerging eLearning Technologies and Applications (ICETA)10.1109/ICETA.2012.6418330(229-234)Online publication date: Nov-2012
    • (2011)Classification of user interest patterns using a virtual folksonomyProceedings of the 11th annual international ACM/IEEE joint conference on Digital libraries10.1145/1998076.1998095(105-108)Online publication date: 13-Jun-2011
    • (2011)Beyond the usual suspectsProceedings of the 22nd ACM conference on Hypertext and hypermedia10.1145/1995966.1995974(27-36)Online publication date: 6-Jun-2011
    • 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

    EPUB

    View this article in ePub.

    ePub

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media