HUMAN NAVIGATION OF INFORMATION NETWORKS A . - Stanford University

7d ago
25 Views
0 Downloads
2.74 MB
155 Pages
Last View : 1d ago
Last Download : n/a
Upload by : Abby Duckworth
Transcription

HUMAN NAVIGATION OF INFORMATION NETWORKSA DISSERTATIONSUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCEAND THE COMMITTEE ON GRADUATE STUDIESOF STANFORD UNIVERSITYIN PARTIAL FULFILLMENT OF THE REQUIREMENTSFOR THE DEGREE OFDOCTOR OF PHILOSOPHYRobert WestJune 2016

AbstractNetwork navigation constitutes a fundamental human behavior: in order to make use ofthe information and resources around us, we constantly explore, disentangle, and browsenetworks such as the Web, social networks, academic paper collections, and encyclopedias,among others. Studying the navigation patterns humans employ is important because it letsus better understand how humans reason about complex networks and lets us build moreintuitively navigable and human-friendly information systems.In this dissertation, we study how humans navigate information networks by analyzingtens of thousands of navigation traces harvested from the human-computation game Wikispeedia, where participants are asked to navigate between two given Wikipedia articles inas few clicks as possible. We first shed light on human navigation strategies by describingthe anatomy of typical human navigation traces. We then build on these results to developmodels and tools for predicting the targets of human paths from only the first few clicks,learning to navigate automatically, and recommending the insertion of important missinghyperlinks. These are useful building blocks for designing more intuitively navigable information spaces and tools to help people find information.The navigation traces collected through the Wikispeedia game have the unique propertyof being labeled with users’ explicit navigation targets. In general, however, humans neednot have a precise target in mind when navigating the Web. Records of such navigationtraces are abundant in the logs kept by any web server software. We demonstrate the valueof passively collected web server logs by presenting an algorithm that leverages such rawlogs in order to improve website hyperlink structure. The resulting system is deployed onWikipedia’s full server logs at terabyte scale, producing links that are clicked 12 times asfrequently as the average link added by human Wikipedia editors.iv

Dedicated to my wife Verena. Mnmnm.v

AcknowledgementsI am deeply grateful to my adviser Jure Leskovec for guiding me through my PhD. Hehas been an admirable mentor, sharp, creative, honest, and supportive. Our meetings havealways been a dizzying flurry of ideas that lastingly strengthened my sense of orientationin the world of academia.—‘Super!’I would also like to thank Dan Jurafsky, Chris Potts, Eric Horvitz, and Chris Ré, whohave served on my thesis committee and have provided invaluable advice throughout mytime at Stanford, especially as I was hunting for jobs.Dan Jurafsky welcomed me to Stanford in my first quarter as a rotation mentor. Hisunique, enthusiastic advising style made work a breeze. I also learned from Dan howimportant it is to look for the broader story underneath the bare results, and that shorts andflip flops are the way to go.Some of my most enjoyable collaborations were with Chris Potts, an eloquent, calm,and collegial mentor. Time after time have I been impressed by his poignant and convincingwriting style and by his distinct skill to propose changes to the structure of a technical talkthat seemed obvious after the fact, but that hadn’t been obvious at all before. I also havefond memories of working on our TACL paper together in Chris’s office—an effective wayto write that I will certainly apply with my students in the future.During two internships at Microsoft Research (and beyond), Eric Horvitz has been anever-active quasar of ideas and good humor. I admire how he manages to maintain hisdeeply reflective attitude amidst all this momentum. Eric illuminated to me not only thatwild-eyed ideas are worth pursuing, but also that carefully executing a single crisp ideapays off. Ironically, although one of our projects was health-related, Eric is the only personvi

with whom I’ve ever smoked an entire cigar from start to finish (but I’m not sure if I shouldthank him for that).The final year of my PhD was shaped by my collaboration with the Wikimedia Foundation. I am especially obliged to Leila Zia, who has initiated and steadily nurtured thisfun and fruitful endeavor. I deeply appreciate Leila’s gentle yet purposeful style, whichmakes every meeting start and end with a kind and honest smile, with many others in between. The support and friendship of Dario Taraborelli, Ellery Wulczyn, and many otherWikimedians also played a key role in making my Wikimedia Fellowship a success.Some of the most productive months of my PhD were spent on summer internships,during which I was privileged to work with colleagues and mentors who influenced myresearch in important ways and who taught me lessons I couldn’t have learned in academia.In particular, I would like to thank Ryen White from Microsoft, Evgeniy Gabrilovich andKevin Murphy from Google, and Chato Castillo and Ingmar Weber from Yahoo.I’m also grateful to all the other great people I’ve had the chance to work—and inthe process become friends—with, in particular Ashwin Paranjape, Srijan Kumar, CristianDanescu-Niculescu-Mizil, Aju Scaria, and Rose Philip.I thank Alex Clemesha for granting access to the navigation traces collected throughThe Wiki Game, as well as all players of Wikispeedia and all contributors and readers ofWikipedia, without whom the present research would have been impossible.Being a member of the Stanford Infolab showed me that a cohesive, friendly lab cultureis key in academia. There have been so many kind Infolab members that I must apologizefor not being able to name each of them separately. Suffice it to point to the roots of theforest and trust that my gratitude will percolate down from there: in lieu of all Infolabmembers, let me thank Hector Garcia-Molina, Jennifer Widom, Jeff Ullman, Gio Wiederhold, Rok Sosič, and Andreas Paepcke for the joy- and helpful Infolunch meetings everyFriday, brimming with trip reports, international candy, clean as well as dirty jokes, andsome of the most insightful tech-talk feedback out there. I also owe a special thank-you toour outstanding lab administrators Marianne Siroker and Yesenia Gallegos.Academic progress hinges on the ability to pursue ideas freely. I therefore gratefullyacknowledge the financial support from a Facebook Graduate Fellowship and a HewlettPackard Stanford Graduate Fellowship, which have afforded me that freedom.vii

Getting a PhD is tough work, and keeping the spirits high would be hard without theconsolation of non tibi hoc soli and the support of peers who are going through the sameups and downs. More than the degree being concluded with this thesis, I value the dearfriends I have made over the course of the past six years at Stanford: Thanks to Hristo‘The Wolf’ Paskov, my companion from day zero beyond day two thousand at Stanford,a mathematical Conan, and one of the most generous and loyal people I have ever met.Thanks to Kelley Paskov, an angel of hospitality and the element of reason that has savedus from bears, starvation, and other stupidities. Thanks to Julian McAuley, a top humanbeing and source of Delphic advice about research at the proper and meta levels, who not asingle time said, ‘I’m busy, come back later.’ Thanks to Andrej Krevl, the best sysadmin inthe world and a condicio sine qua non without whose advice and selfless help many of theresults presented here would never have seen the light of day and whose honesty is bound tomake him keep his promise to go on a bike ride with me before I leave California. Thanks toAshton Anderson—roommate, labmate, courtmate, Seoulmate, fond of fonts and a boilingwort of words—, with whom I share so many interests and passions. And thanks to JakeLussier, a rare combination of chaos and reason that is rare to find, especially around theMission District.Many others have contributed to making my Golden State years a blast. Special thanksto Ben Sanders, Anna Druet, Amit Levy, Elliott Engelmann, Amina Bayou, Greg Mesnil, Mònica Vilas, Enrique Fibla, Matthew and Joseph Williams, Kyle Knaggs, Chuck deLannoy, Bobak Shahriari, Fabian Kaelin, and Ryan Faulkner.A big shout goes to all my homies in Bavaria: Andy, Aussi, Colosso, Gbrl, Katha,Klausi, Kulzi, Schieder. Our friendship has remained so steadfast over the decades that noupdate is needed to the acknowledgements I included in my master’s thesis six years ago.More than to anyone else I need to send my gratitude and appreciation to my family.They are the sources, the hubs, and the targets of the paths on which I’ve been navigatinglife. A thousand thanks go to my parents Waltraut and Helmuth, my sister Tina, and mygrandparents Agnetha and Heinrich Fleischer and Barbara and Johann-Anton West.Finally, I dedicate this thesis to my beloved wife Verena, whom I will tell in person howmuch I love her.viii

1.1Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.2Overview and summary of contributions . . . . . . . . . . . . . . . . . . .51.2.1Analysis of human navigation traces (Chapter 4) . . . . . . . . . .61.2.2Predicting targets of human navigation traces (Chapter 5) . . . . . .71.2.3Automatic versus human navigation (Chapter 6) . . . . . . . . . .81.2.4Improving website hyperlink structure (Chapter 7) . . . . . . . . .923Background and related work112.1Information foraging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2Decentralized search in small-world networks . . . . . . . . . . . . . . . . 132.3Markov modeling of website navigation . . . . . . . . . . . . . . . . . . . 142.4Search trail analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5Link recommendation and prediction . . . . . . . . . . . . . . . . . . . . . 162.6Games with a purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16Obtaining datasets of navigation traces3.118Obtaining navigation traces from raw web server logs . . . . . . . . . . . . 193.1.1From logs to trees. . . . . . . . . . . . . . . . . . . . . . . . . . 193.1.2Wikipedia data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20ix

3.1.33.246Collecting targeted navigation traces via human-computation games . . . . 223.2.1Wikispeedia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2.2The Wiki Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24Analysis of human navigation traces264.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.2Efficiency of human search . . . . . . . . . . . . . . . . . . . . . . . . . . 284.3Elements of human navigation . . . . . . . . . . . . . . . . . . . . . . . . 334.45Simtk data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.3.1Anatomy of typical paths . . . . . . . . . . . . . . . . . . . . . . . 334.3.2Trade-off between similarity and degree . . . . . . . . . . . . . . . 394.3.3Endgame strategies . . . . . . . . . . . . . . . . . . . . . . . . . . 41Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Predicting targets of human navigation traces455.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.2Human Markov model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.3Binomial logistic model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.4Learning-to-rank model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.5Features for learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.6Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.7Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52Automatic versus human navigation546.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546.2The abstract search algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 566.3Implementations of the search algorithm . . . . . . . . . . . . . . . . . . . 586.46.3.1Heuristic agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586.3.2Machine learning agents . . . . . . . . . . . . . . . . . . . . . . . 59Empirical evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.4.1Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . . . 616.4.2Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64x

6.4.36.57Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Improving website hyperlink structure727.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727.2Improving hyperlink structure using targeted navigation traces . . . . . . . 787.37.48Feature analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687.2.1Method for link recommendation . . . . . . . . . . . . . . . . . . 797.2.2Exploratory analysis of link candidates . . . . . . . . . . . . . . . 827.2.3Obtaining ground truth based on Wikipedia evolution . . . . . . . . 837.2.4Evaluation methodology . . . . . . . . . . . . . . . . . . . . . . . 857.2.5Evaluation on The Wiki Game . . . . . . . . . . . . . . . . . . . . 877.2.6Evaluation on Wikispeedia . . . . . . . . . . . . . . . . . . . . . . 947.2.7Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96Improving hyperlink structure using raw server logs . . . . . . . . . . . . . 987.3.1The link placement problem . . . . . . . . . . . . . . . . . . . . . 1007.3.2Estimating clickthrough rates . . . . . . . . . . . . . . . . . . . . 1067.3.3Evaluation: effects of new links . . . . . . . . . . . . . . . . . . . 1087.3.4Evaluation: link placement . . . . . . . . . . . . . . . . . . . . . . 1137.3.5Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122Conclusions1248.1Summary of contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 1248.2Future directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1268.2.1Network structure versus navigability . . . . . . . . . . . . . . . . 1268.2.2Navigation versus keyword search . . . . . . . . . . . . . . . . . . 1268.2.3Further models and tools . . . . . . . . . . . . . . . . . . . . . . . 1278.2.4Navigation in the wild . . . . . . . . . . . . . . . . . . . . . . . . 128A Human-rater instructions on Amazon Mechanical Turk130Bibliography131xi

List of Tables4.1Summary statistics of the distributions of Fig. 4.1. . . . . . . . . . . . . . . 297.1Area under the precision at k curve for no candidate selection vs. path-basedcandidate selection for all ranking measures . . . . . . . . . . . . . . . . . 897.2Area under the precision at k curve for MW ranking, comparing the automated and human evaluations of our method run on data from The WikiGame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 937.3Comparison of clickthrough rate estimation methods on Wikipedia . . . . . 1147.4Top 10 link suggestions of Algorithm 2 using objectives f2 and f3 . . . . . 1197.5Performance of path-proportion clickthrough estimation on Simtk . . . . . 120xii

List of Figures1.1Wikispeedia example path between the conceptsEINSTEINDIK - DIKandALBERT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43.1Wikipedia dataset statistics . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2Screenshots of the human-computation game Wikispeedia, which we usefor data collection (Sec. 3.2.1). . . . . . . . . . . . . . . . . . . . . . . . . 234.1Distribution of Wikispeedia game length, according to different path-lengthmetrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2Distribution of game length for four specific missions with an optimal solution of 3 clicks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3Drop-out rate in Wikispeedia as a function of path position . . . . . . . . . 314.4Link probability P(r) as a function of rank r . . . . . . . . . . . . . . . . . 324.5The evolution of article properties along Wikispeedia paths, for games ofoptimal length 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.6Hub quality as a function of search time . . . . . . . . . . . . . . . . . . . 364.7Logistic regression weights for classifying human vs. non-human clicks . . 404.8Overhead with respect to optimal solutions . . . . . . . . . . . . . . . . . . 425.1Performance of our target prediction algorithms, for varying prefix lengths k 515.2Sibling precision of our target prediction algorithms . . . . . . . . . . . . . 516.1Results of the task of navigating Wikipedia automatically: mean overheadfactor and percentage of long paths . . . . . . . . . . . . . . . . . . . . . . 65xiii

6.2Results of the task of navigating Wikipedia automatically: precision andCDF of search time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.3Weights learned by logistic regression for navigating Wikipedia automatically 677.1Complementary cumulative distribution function of the number of clicksreceived in March 2015 by links introduced in the English Wikipedia inFebruary 2015. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747.2Source vs. target prediction . . . . . . . . . . . . . . . . . . . . . . . . . . 757.3The final portions of several navigation paths with the same target t IN FLAMMATION7.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78Overview of our approach for mining missing hyperlinks to a given targett from human navigation traces . . . . . . . . . . . . . . . . . . . . . . . . 807.5Exploratory analysis of link candidates . . . . . . . . . . . . . . . . . . . . 847.6Performance in terms of precision at k for different source selection andranking methods on our two datasets . . . . . . . . . . . . . . . . . . . . . 887.7Results of link recommendation . . . . . . . . . . . . . . . . . . . . . . . 917.8Histogram of average human labels for examples labeled as negative by theautomatically obtained ground truth, highlighting the prevalence of falsenegatives in the latter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947.9Clickthrough rate as function of source-page out-degree and relative position of link in wiki markup of source page . . . . . . . . . . . . . . . . . . 1097.10 Across different source pages, structural degree is negatively correlatedwith stopping probability, and positively correlated with navigational degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1127.11 Results of clickthrough prediction on Wikipedia . . . . . . . . . . . . . . . 1147.12 Precision at k on link prediction task . . . . . . . . . . . . . . . . . . . . . 1167.13 Results of budget-constrained link placement for objectives . . . . . . . . . 1187.14 Link placement results on Simtk . . . . . . . . . . . . . . . . . . . . . . . 121xiv

Chapter 1Introduction1.1MotivationThere is more information in the world than a single human being could possibly makesense of, and it has become commonplace to remark that we live in an ‘age of informationoverload’ [30, 97]. As early as 1755, the encyclopedist Denis Diderot anticipated that, “[a]slong as the centuries continue to unfold, the number of books will grow continually, andone can predict that a time will come when it will be almost as difficult to learn anythingfrom books as from the direct study of the whole universe.” [24]Two centuries later, Diderot’s premonition had become a fact that threatened to seriously slow the progress of science. As remarked by Vannevar Bush in his seminal 1945article As We May Think, “[t]here is a growing mountain of research. But there is increasedevidence that we are being bogged down today as specialization extends.” [13] In the samearticle, Bush sketched a remedy: the ‘memex’, a hypothetical information managementdevice that would allow users to not only retrieve documents quickly, but to also easily linkdocuments to each other, such that the subsequent retrieval of one document would alsolet the user effortlessly retrieve those documents linked to it previously. Decades later, thememex was to become a principal inspiration for early hypertext systems and ultimatelythe World Wide Web [9, 14, 29, 71].1

CHAPTER 1. INTRODUCTION2The idea of interlinking documents was not new. Encyclopedic articles, scientific papers, and other types of document have always pointed to one another by means of references. Bush’s seminal innovation was that links could be created ad hoc, by the readerrather than the writer. The early World Wide Web was still woven together by its writers,rather than its readers; only recently have we achieved Bush’s vision of ad-hoc linking,through techniques such as social bookmarking [43], tagging [62], and wikis [54].Information becomes useful to us only when we interact with it, when we disentangleand navigate the intricate networks in which distinct pieces of information relate to oneanother. Through the ability to fluidly associate items of information with each other andscaffold them into tall buildings of thought, we draw conclusions and are able to make senseof the world. Information becomes knowledge. As Bush put it, “[the human mind] operatesby association. With one item in its grasp, it snaps instantly to the next that is suggestedby the association of thoughts, in accordance with some intricate web of trails carriedby the cells of the brain.” [13] Consequently, he suggested to not only store and publishthe pairwise links established by a user, but to store and publish entire trails emergingwhen users navigate the network formed by the links she or others have previously created:“Wholly new forms of encyclopedias will appear, ready made with a mesh of associativetrails running through them, ready to be dropped into the memex and there amplified.” [13]In this regard, we still have not achieved Bush’s vision yet: while there are projectssuch as Wikipedia, an open encyclopedia where any user can edit articles and connectrelated articles in a pairwise fashion, technology and science are still lagging behind withrespect to creating, and reasoning about, the “mesh of associative trails running throughthem”. Many important questions have yet to be answered. For instance, how do peopleinteract with information networks such as the World Wide Web? What is the nature ofthe “associative trails” they embark on? By what strategies do they find information inthose networks? How can we infer what users are looking for, and how can we help themfind it? How can we optimally guide users through a network to impart on them a deepunderstanding of a topic? How should we optimally structure those “[w]holly new formsof encyclopedias” that Bush anticipated, and how can we extract a meaningful “mesh ofassociative trails” from them? How should those trails be gathered, curated, and presented,in order to render them maximally useful?

CHAPTER 1. INTRODUCTION3These are challenging questions, but answering them would yield significant payoffs:information and knowledge are some of our most valuable resources, and building moreintuitive and human-friendly information systems will make those resources more easilyaccessible and will ultimately change our lives for the better.The goal of this thesis is to make progress toward answering the above questions by1. furthering our scientific understanding of how humans navigate information networks and2. turning these insights into useful models and tools for facilitating and enhancing thenavigability of those networks.We shall proceed in a data-driven approach. With billions of users browsing the Webevery day, and servers logging their every action, we have detailed records of human behavior in information networks. In particular, stringing records of individual page viewstogether into records of entire trails, or traces, of page views presents the opportunity tostudy how humans navigate, and find their way through, networks.The traces extracted from passively collected server logs may be triggered by any ofa large number of information needs, and the logs typically do not explicitly specify theinformation need associated with each trace. This is true even for traces collected within asingle website. For instance, users of an online shopping site may be looking for a specificproduct, or they may be casually browsing the virtual shelves out of boredom. Users ofWikipedia may be consulting the site in order to look up a definition, answer a homeworkquestion, decide whether to buy a certain product, settle an argument with a friend, deeplyimmerse themselves in a topic, or simply explore the encyclopedia by randomly driftingfrom page to page.A coarse dichotomy lets us distinguish between two broad modes of navigation in information networks: targeted and exploratory [61]. In targeted navigation the user has aclear question or topic in mind, whereas in exploratory navigation the user’s informationneed is less well defined, and may even change as the session progresses.Unfortunately, determining the information need addressed by a given trace extractedfrom passively collected server logs, or even just determining whether it is an instance oftargeted or exploratory navigation, is difficult and constitutes itself a challenging research

4CHAPTER 1. IN52621WATER0QUANTUMMECHANICSFigure 1.1: Wikispeedia example path between the concepts DIK - DIK and ALBERT EIN STEIN . Nodes represent Wikipedia articles and edges the hyperlinks clicked by the human.Edge labels indicate the order of clicks, the framed numbers the shortest-path length to thetarget. One of several optimal solutions would be hDIK - DIK, WATER, GERMANY, ALBERTEINSTEIN i.problem. This lack of ground-truth information complicates both the analysis of humaninformation-seeking behavior (item 1 above), as well as the usefulness of traces for buildingmodels and tools (item 2).To circumvent these challenges, prior work in human–computer interaction and information retrieval has tended to focus on small-scale studies and laboratory experiments,often of qualitative nature, where the user is given an explicit Web navigation task and isthen observed solving the task [42, 70, 76, 86, 99]. But even in these controlled settings,it remains difficult to reason about certain aspects of human behavior within the networkof webpages: There are no simple and concise ways of representing the content of generalwebpages and of measuring the level of relatedness of pairs of pages in a robust manner.Moreover, the aforementioned studies typically do not have access to the complete connectivity structure of the network being navigated; as a consequence, the full space of actionsthe users could have taken is unknown, which makes it hard to judge the optimality of theirobserved search strategies.We alleviate these problems by leveraging navigation traces harvested from the human-computation game Wikispeedia [104], which we have designed and implemented inprevious work [109]. Wikispeedia is played within Wikipedia and challenges participants

CHAPTER 1. INTRODUCTION5to navigate from a given start article to a given target article by exclusively clicking Wikipedia’s article-to-article links, using as few clicks as possible. To illustrate the dynamics ofthe Wikispeedia game, Fig. 1.1 gives the example of a human path between the start articleDIK - DIKand the target ALBERT EINSTEIN.This setup has the advantage of producing tens of thousands, rather than dozens orhundreds, of navigation traces that are explicitly labeled with the user’s navigation target.Moreover, every Wikipedia page is about a clearly defined topic, which gives us a handlefor reasoning about the semantic structure of the information space through which users arefinding their way; e.g., we may compute the relatedness of two pages by measuring theirdistance in Wikipedia’s category hierarchy, and we may describe the content of a pagein one concise phrase—its title. Finally, since the navigation environment is restricted toWikipedia, we have access to the full connectivity structure of the underlying network.In this thesis, we first harness the targeted navigation traces collected through Wikispeedia by conducting a detailed analysis of users’ navigation strategies. We then strive toturn our insights into useful models and tools for predicting and supporting user behaviorand improving the navigability of the underlying network. We argue that such tools forsupporting navigation-based search should be rooted in empirically observed user behavior in order to be practically useful, just as the modern web search engines that supportquery-based search depend in critical ways on models learned from interaction logs [60].1.2Overview and summary of contributionsThe purpose of this thesis is twofold. We strive to (1) deepen our scientific understandingof the patterns and strategies by which users navigate information networks and (2) buildmodels and tools for supporting users as they navigate and for making the underlying networks themselves more navigable.The overall structure of the thesis is as follows. We start by providing an overview ofthe most relevant areas of related work in Chapter 2. Then, in Chapter 3, we describe thedatasets of navigation traces we use throughout this research. The main technical contributions are made in Chapters 4–7. In Chapter 4 we perform a detailed analysis of the targetednavigation traces collected through the human-computation game Wikispeedia. We then

CHAPTER 1. INTRODUCTION6build on the results of this analysis to design models and algorithms for predicting theuser’s navigation target after

consolation of non tibi hoc soli and the support of peers who are going through the same ups and downs. More than the degree being concluded with this thesis, I value the dear friends I have made over the course of the past six years at Stanford: Thanks to Hristo 'The Wolf' Paskov, my companion from day zero beyond day two thousand at Stanford,

Related Documents:

Navigation User Manual . 1.Home Menu. First Page . Second Page Third Page . 2. How to use Navigation. Enter the second menu. Click icon “Navigation”,access into Navigation function. Please refer to the instruction manual for navigation software . 1 2 . Common apps Car info . Home. Menu . 1.Player .

Button. See Navigation Audio System on page 3-2 for more information. P. Map DVD Slot. See “Nav (Navigation)” under Configure Menu on page 2-26for information on how to load/unload a map DVD. Q. f (Tune/Sound) knob. See Navigation Audio System on page 3-2for more information. R. AUDIO Key. See Navigation Audio System on page 3-2for more .File Size: 1MB

Chevrolet Equinox and GMC Terrain Navigation System (Include Mex) - 2012 Black plate (4,1) 4 Infotainment System Overview Read this manual thoroughly to become familiar with how the navigation system operates. The navigation system includes navigation and audio functions. Keeping your eyes on the road and your mind on the drive is important for .

PARTS LOCATION ENGINE ROOM RELAY BLOCK, RELAY BLOCK - BK/UP LP RELAY - DOME FUSE . owned by Bluetooth SIG, Inc. I101463E01 Cellular Tower Cellular Phone (Bluetooth type) . MPX DTC is output B Go to MULTIPLEX COMMUNICATION SYSTEM. NS–16 NAVIGATION – NAVIGATION SYSTEM NS

NAVIGATION SYSTEM RNAV2 Precision Navigation System (p/n 4600-101) is an innovative electronic navigation system that can be either mounted in the DPD to enable precision navigation by combat divers, or without divers for Autonomous Unmanned Vehicle (AUV) missions. Additionally, the RNAV2

Navigation System on page 2-2. J. ROUTE Key. See “Hard Keys” under Using the Navigation System on page 2-2. K. MENU Key. See “Hard Keys” under Using the Navigation System on page 2-2. L. TILT Key. See “Hard Keys” under Using the Navigation System on page 2-2. Getting Started Before you begi

Jul 24, 2017 · A. Aids to Navigation Manual. 1-1 B. Short Range Aids to Navigation Systems. 1-2 C. Coast Guard Authority. 1-3 D. Short Range Aids to Navigation Organization. 1-6 CHAPTER 2 - GENERAL ADMINISTRATION OF THE SHORT RANGE AIDS TO NAVIGATION SYSTEM 2-1 A. Management Principles. 2-1 B. Administrative Procedures. 2-2

only inertial navigation system. Objective of the proposal: The objective of the proposal is a combination of the existing inertial navigation system (INS) with global position system (GPS) for more accurate navigation of the launchers. The project's product will be navigation algorithms software package and hardware units.

navigation in rural environments through a novel mapless driving framework that combines sparse topological maps for global navigation with a sensor-based perception system for local navigation. First, a local navigation goal within the sensor view of the vehicle is chosen as a waypoint leading towards the global goal.

the autonomous navigation of these systems. The global positioning system (GPS) is used for external autonomous navigation [1]. Because GPS signals are typically absent or weak indoors, autonomous navigation is difficult [2]. There are various approaches for independent indoor navigation which have been proposed in recent years.

The PBN concept represents a shift from sensor-based to performance-based navigation. Performance requirements are identified in navigation specifications, which also identify the choice of navigation sensors and equipment that may be used to meet the performance requirements. These navigation specifications are defined at

Navigation System The Professional navigation system features a map display in the central information dis-play. The E60 no longer features a separate navigation computer. The navigation comput-er has been integrated in the CCC. Top-HiFi Amplifier with LOGIC7 The E60 offers two different audio systems to choose from: HiFi and Top-HiFi. In the Top-

Cruze Radio with Navigation, Radio without Navigation Similar 1. Preset Buttons (1–6) 2. DEST (Destination) 3. NAV (Navigation) 4. Eight-Way Selector Arrows (Navigates Maps) 5. CONFIG (Configuration Menu) 6. RPT NAV (Repeat Navigation) 7. CLOCK 8. INFO (Information) 9. TONE 10. AS (Autost

Virtual Navigation System Based on Android Junlin Li With the development of GPS and 3G network, mobile navigation systems are widely used in people's daily life. From 2D electronic map to 3D simulation map, the navigation services based on real-scene information is becoming the mainstream. Due

Unified Networks Corporate Data Networks Public Data Networks Corporate Telephony Networks Public Telephony Networks The Unified Network Brings It All Together Unified Network defined: Brings together the world’s disparate telephony and data networks Optimized for both service

Chrome Developer Tools React Native Inspector with react-devtools Installing external libraries with npm. What is navigation? Navigation is a broad term that covers topics related to how you move between screens in your app Web navigation is oriented around URLs

Honda Navigation System Approaches AcuraLink InterNAVI Premium Club Car Navigation System 1981 Honda Electro Gyro-catorHonda Electro Gyro--catorcator Digital map navigation 1990 Interactive communication NAVI US destined navigation Japan . 3/6/2008 7:04:07 PM .

- Systèmes de navigation compatibles : Navigation multimédia Professional ou Navigation multimédia Business (codes option 609, 6UP ou 606, 6UN). - Générations compatibles du hardware de navigation : (CIC-H, CIC-M, Champ2, Entry Nav, NBT, NBTEvo). - Seulement pour les véhicules équipés de la carte SIM BMW ConnectedDrive.

1 A Celestial Navigation Primer by Ron Davidson Introduction The study of celestial navigation, whether for blue water sailing, the taking of a navigation class (like the United States Power Squadron's JN or N classes), or for pure intellectual pursuit, is often considered to be a daunting subject.

2008 Mid-Size Truck Navigation System M. GENERAL MOTORS, GM, CHEVROLET, the CHEVROLET Emblem, GMC, and the GMC TRUCK . you can use it with less effort and take full advantage of its features. Your navigation system includes not only navigation, but also audio functions. While your