More Web Proxy on the site http://driver.im/

research-article

Exploring the differences and similarities between hierarchical decentralized search and human navigation in information networks

Authors:

Christoph Trattner,

Philipp Singer,

Markus StrohmaierAuthors Info & Claims

i-KNOW '12: Proceedings of the 12th International Conference on Knowledge Management and Knowledge Technologies

Article No.: 14, Pages 1 - 8

https://doi.org/10.1145/2362456.2362474

Published: 05 September 2012 Publication History

Abstract

Decentralized search in networks is an activity that is often performed in online tasks. It refers to situations where a user has no global knowledge of a network's topology, but only local knowledge. On Wikipedia for instance, humans typically have local knowledge of the links emanating from a given Wikipedia article, but no global knowledge of the entire Wikipedia graph. This makes the task of navigation to a target Wikipedia article from a given starting article an interesting problem for both humans and algorithms. As we know from previous studies, people can have very efficient decentralized search procedures that find shortest paths in many cases, using intuitions about a given network. These intuitions can be modeled as hierarchical background knowledge that people access to approximate a networks' topology. In this paper, we explore the differences and similarities between decentralized search that utilizes hierarchical background knowledge and actual human navigation in information networks. For that purpose we perform a large scale study on the Wikipedia information network with over 500,000 users and 1,500,000 click trails. As our results reveal, a decentralized search procedure based on hierarchies created directly from the link structure of the information network simulates human navigational behavior better than simulations based on hierarchies that are created from external knowledge.

References

[1]

L. Adamic and E. Adar. How to search a social network. Social Networks, 27(3):187--203, 2005.

[2]

E. Adar, J. Teevan, and S. T. Dumais. Large scale analysis of web revisitation patterns. In Proceedings of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, CHI "08, pages 1197--1206, New York, NY, USA, 2008. ACM.

Digital Library

[3]

D. Benz, A. Hotho, and G. Stumme. Semantics made by you and me: Self-emerging ontologies can capture the diversity of shared knowledge. In Proc. of the 2nd Web Science Conference (WebSci10), Raleigh, NC, USA, 2010. Web Science Trust.

[4]

D. Benz, C. Körner, A. Hotho, G. Stumme, and M. Strohmaier. One tag to bind them all: Measuring term abstractness in social metadata. In Proceedings of the 8th Extended Semantic Web Conference (ESWC 2011), Heraklion, Crete, May 2011.

Digital Library

[5]

M. Bilenko and R. W. White. Mining the search trails of surfing crowds: identifying relevant websites from user activity. In Proceedings of the 17th international conference on World Wide Web, WWW "08, pages 51--60, New York, NY, USA, 2008. ACM.

Digital Library

[6]

M. Boguñá, D. Krioukov, and K. C. Claffy. Navigability of complex networks. Nature Physics, 5:74--80, Jan. 2009.

[7]

M. Boguñá, F. Papadopoulos, and D. Krioukov. Sustaining the Internet with hyperbolic mapping. Nature Communications, 1:62, Sept. 2010.

[8]

A. Clauset, C. Moore, and M. E. J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191):98--101, 2008.

[9]

D. Helic, C. Körner, M. Granitzer, M. Strohmaier, and C. Trattner. Navigational efficiency of broad vs. narrow folksonomies. In Proceedings of the 23rd ACM Conference on Hypertext and Social Media, HT "12, New York, NY, USA, 2012. ACM.

Digital Library

[10]

D. Helic and M. Strohmaier. Building directories for social tagging systems. In Proceedings of the 20th ACM international conference on Information and knowledge management, CIKM "11, pages 525--534, New York, NY, USA, 2011. ACM.

Digital Library

[11]

D. Helic, M. Strohmaier, C. Trattner, M. Muhr, and K. Lerman. Pragmatic evaluation of folksonomies. In Proceedings of the 20th international conference on World wide web, WWW "11, pages 417--426, New York, NY, USA, 2011. ACM.

Digital Library

[12]

P. Heymann and H. Garcia-Molina. Collaborative creation of communal hierarchical taxonomies in social tagging systems. Technical Report 2006--10, Stanford InfoLab, April 2006.

[13]

J. Kleinberg. The small-world phenomenon: an algorithm perspective. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, STOC "00, pages 163--170, New York, NY, USA, 2000. ACM.

Digital Library

[14]

J. M. Kleinberg. Navigation in a small world. Nature, 406(6798):845, August 2000.

[15]

J. M. Kleinberg. Small-world phenomena and the dynamics of information. In Advances in Neural Information Processing Systems (NIPS) 14, page 2001, Cambridge, MA, USA, 2001. MIT Press.

Digital Library

[16]

D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82(3):036106, Sep 2010.

[17]

S. Milgram. The small world problem. Psychology Today, 1:60--67, 1967.

[18]

L. Muchnik, R. Itzhack, S. Solomon, and Y. Louzoun. Self-emergence of knowledge trees: Extraction of the wikipedia hierarchies. Phys. Rev. E, 76:016106, Jul 2007.

[19]

M. A. Serrano, D. Krioukov, and M. Boguñá. Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett., 100(7):078701, Feb 2008.

[20]

A. Singla, R. White, and J. Huang. Studying trailfinding algorithms for enhanced web search. In Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval, SIGIR "10, pages 443--450, New York, NY, USA, 2010. ACM.

Digital Library

[21]

M. Strohmaier, D. Helic, D. Benz, C. Körner, and R. Kern. Evaluation of folksonomy induction algorithms. ACM Trans. Intell. Syst. Technol., 2012.

Digital Library

[22]

C. Trattner. Improving the navigability of tagging systems with hierarchically constructed resource lists and tag trails. CIT, 19(3):155--167, 2011.

[23]

C. Trattner, D. Helic, and M. Strohmaier. On the construction of efficiently navigable tag clouds using knowledge from structured web content. j-jucs, 17(4):565--582, 2011.

[24]

C. Trattner, Y.-L. Lin, D. Parra, W. Real, and P. Brusilovsky. Evaluating tag-based information access in image collections. In Proceedings of the 23rd ACM Conference on Hypertext and Social Media, HT "12, New York, NY, USA, 2012. ACM.

Digital Library

[25]

R. West and J. Leskovec. Human wayfinding in information networks. In Proceedings of the 21th international conference companion on World wide web, WWW'12, New York, NY, USA, 2012. ACM.

Digital Library

[26]

R. West and J. Leskovec. Human wayfinding in information networks. In Proceedings of the 6th International AAAI Conference on Weblogs and Social Media, ICWSM'12, Dublin, Ireland, 2012. AAAI.

Digital Library

[27]

A. Zubiaga, C. Körner, and M. Strohmaier. Tags vs shelves: from social tagging to social classification. In Proceedings of the 22nd ACM conference on Hypertext and hypermedia, HT "11, pages 93--102, New York, NY, USA, 2011. ACM.

Digital Library

[28]

A. Zubiaga, R. Martínez, and V. Fresno. Getting the most out of social annotations for web page classification. In Proceedings of the 9th ACM symposium on Document engineering, DocEng "09, pages 74--83, New York, NY, USA, 2009. ACM.

Digital Library

Cited By

Vojíř SKučera J(2021)Towards Re-Decentralized Future of the Web: Privacy, Security and Technology DevelopmentActa Informatica Pragensia10.18267/j.aip.16910:3(349-369)Online publication date: 31-Dec-2021
https://doi.org/10.18267/j.aip.169
Piccardi TRedi MColavizza GWest R(2020)Quantifying Engagement with Citations on WikipediaProceedings of The Web Conference 202010.1145/3366423.3380300(2365-2376)Online publication date: 20-Apr-2020
https://dl.acm.org/doi/10.1145/3366423.3380300
Moro RBielikova M(2020)Navigation leads for exploratory search and navigation in digital librariesKnowledge and Information Systems10.1007/s10115-019-01434-2Online publication date: 31-Jan-2020
https://doi.org/10.1007/s10115-019-01434-2
Show More Cited By

Index Terms

Exploring the differences and similarities between hierarchical decentralized search and human navigation in information networks
1. Applied computing
  1. Document management and text processing
    1. Document preparation
      1. Multi / mixed media creation
2. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction paradigms
      1. Hypertext / hypermedia

Recommendations

Human wayfinding in information networks
WWW '12: Proceedings of the 21st international conference on World Wide Web

Navigating information spaces is an essential part of our everyday lives, and in order to design efficient and user-friendly information systems, it is important to understand how humans navigate and find the information they are looking for. We perform ...
Models of human navigation in information networks based on decentralized search
HT '13: Proceedings of the 24th ACM Conference on Hypertext and Social Media

Models of human navigation play an important role for understanding and facilitating user behavior in hypertext systems. In this paper, we conduct a series of principled experiments with decentralized search - an established model of human navigation in ...
Human navigation in networks
HT '12: Proceedings of the 23rd ACM conference on Hypertext and social media

World around us interconnected in giant networks and we are daily navigating and finding paths through such networks. For example, we browse the Web [2], search for connections among friends in social networks, follow leads in citation networks[6, 3], ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

i-KNOW '12: Proceedings of the 12th International Conference on Knowledge Management and Knowledge Technologies

September 2012

244 pages

ISBN:9781450312424

DOI:10.1145/2362456

Conference Chairs:
Stefanie Lindstaedt
Graz University of Technology, Austria
,
Michael Granitzer
University Passau, 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 September 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

i-Know '12

i-Know '12: 12th International Conference on Knowledge Management and Knowledge Technologies

September 5 - 7, 2012

Graz, Austria

Acceptance Rates

Overall Acceptance Rate 77 of 238 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
276
Total Downloads

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

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vojíř SKučera J(2021)Towards Re-Decentralized Future of the Web: Privacy, Security and Technology DevelopmentActa Informatica Pragensia10.18267/j.aip.16910:3(349-369)Online publication date: 31-Dec-2021
https://doi.org/10.18267/j.aip.169
Piccardi TRedi MColavizza GWest R(2020)Quantifying Engagement with Citations on WikipediaProceedings of The Web Conference 202010.1145/3366423.3380300(2365-2376)Online publication date: 20-Apr-2020
https://dl.acm.org/doi/10.1145/3366423.3380300
Moro RBielikova M(2020)Navigation leads for exploratory search and navigation in digital librariesKnowledge and Information Systems10.1007/s10115-019-01434-2Online publication date: 31-Jan-2020
https://doi.org/10.1007/s10115-019-01434-2
Koopmann TDallmann AHettinger LNiebler THotho AAtzenbeck CRubart JMillard D(2019)On the right track! Analysing and Predicting Navigation Success in WikipediaProceedings of the 30th ACM Conference on Hypertext and Social Media10.1145/3342220.3343650(143-152)Online publication date: 12-Sep-2019
https://dl.acm.org/doi/10.1145/3342220.3343650
Zhao PDing ZWang MCao R(2019)Behavior Analysis for Electronic Commerce Trading Systems: A SurveyIEEE Access10.1109/ACCESS.2019.29332477(108703-108728)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2933247
Lamprecht DStrohmaier MHelic D(2017)A method for evaluating discoverability and navigability of recommendation algorithmsComputational Social Networks10.1186/s40649-017-0045-34:1Online publication date: 11-Oct-2017
https://doi.org/10.1186/s40649-017-0045-3
Lamprecht DDimitrov DHelic DStrohmaier MWasserman A(2016)Evaluating and Improving Navigability of WikipediaProceedings of the 12th International Symposium on Open Collaboration10.1145/2957792.2957813(1-10)Online publication date: 17-Aug-2016
https://dl.acm.org/doi/10.1145/2957792.2957813
Paranjape AWest RZia LLeskovec JBennett PJosifovski VNeville JRadlinski F(2016)Improving Website Hyperlink Structure Using Server LogsProceedings of the Ninth ACM International Conference on Web Search and Data Mining10.1145/2835776.2835832(615-624)Online publication date: 8-Feb-2016
https://dl.acm.org/doi/10.1145/2835776.2835832
Lamprecht DStrohmaier MHelic D(2016)A Method for Evaluating the Navigability of Recommendation AlgorithmsComplex Networks & Their Applications V10.1007/978-3-319-50901-3_20(247-259)Online publication date: 30-Nov-2016
https://doi.org/10.1007/978-3-319-50901-3_20
Lamprecht DStrohmaier MHelic DNyulas CTudorache TNoy NMusen M(2015)Using ontologies to model human navigation behavior in information networks: A study based on WikipediaSemantic Web10.3233/SW-1401436:4(403-422)Online publication date: 7-Aug-2015
https://doi.org/10.3233/SW-140143
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