Social navigation is a form of social computing introduced by Paul Dourish and Matthew Chalmers in 1994, who defined it as when "movement from one item to another is provoked as an artifact of the activity of another or a group of others".^[1] According to later research in 2002, "social navigation exploits the knowledge and experience of peer users of information resources" to guide users in the information space, and that it is becoming more difficult to navigate and search efficiently with all the digital information available from the World Wide Web and other sources.^[2] Studying others' navigational trails and understanding their behavior can help improve one's own search strategy by guiding them to make more informed decisions based on the actions of others.^[3]

Prior to the advancement of Web 2.0 and the Social Web, the World Wide Web had been a solitary space where users were unaware of where anyone else was browsing or navigating.^[4] The scope of social navigation research has been increasing, especially as information visualization improves. Displaying social information in virtual spaces allows user behavior models to make digital systems feel more social and less solitary.^[2]

Supporting theories and techniques

The concept of social navigation is supported by several theories. Information foraging theory studies human behavior when they are seeking, gathering, sharing and consuming information.^[5] It applies optimal foraging theory to human behavior when they navigate to information,^[6] and explains how people benefit from other people based on history-rich digital objects, which explains the idea of used items or paths. For example, a used book that has notes, highlights and underlines is different from a new book. History-rich digital objects help people find the target faster and more efficiently.^[7]

Information foraging is an alternative to food foraging and ant colony optimization,^[6] which state that information human-hunters follow others’ paths to optimally reach their target. Optimal information must maximize the value of the information that is gained per unit cost (like time or effort).^[5] This theory supports collaborative activities,^[8] and is a guide for designers to build good interfaces where users can benefit from others' research.^[7]

The weaknesses of this theory are when people mistrace information; they cannot be redirected unless they figure it out,^[7] and optimization is not always the case for human behavior^[8]

The information patch model studies time spent in navigation in filtered information and clustered information, and works to optimize the overall information as fast as possible;^[5][8] the information scent model determines information value by taking the most useful cues that have been used by other users;^[5][8] and the information diet model (prey selection) explains how people select the target information based on others' selections, which leads to optimal satisfying information.^[5][8]

Webpage design is also important in how a user interacts with the internet in a social manner. There is a correlation between accessibility and popularity:^[9] the more functional a website is, the more traffic it will receive.^[9] A more frequented web service will naturally be a more social experience. There are numerous factors that contribute to accessibility, such as a page's location, properties, number of hyperlinks, and modes of access.^[10][11] As every person has a different approach to surfing the web, internet navigation is defined as "[t]he creation and interpretation of an internal (mental) model, and its component activities are browsing, modelling, interpretation and formulation of browsing strategy."^[10] There is a theory that if a user calibrates their browsing strategy to reflect their interests, pages relevant to their interests will be found more easily.^[10] Uninformed navigation through hyperlinks can be misleading and result in a higher number of unwanted sites being accessed.^[12] Bookmarking is a method to return to sites that appeal to one's interests,^[12] as it creates a hyperlink that is saved for future browsing. When a population bookmarks the same page and visits it frequently, it forms a sense of community. Recently, live updating of other current users adds another dimension to the social aspect of web browsing.^[12]

Collaborative filtering is another technique that is prevalent and utilized in social navigation. It suggests that if users were presented search results based on traffic by others who share similar social interests, it would result in a more rewarding and efficient experience.^[13] For example, Amazon.com has a "Customers Who Bought This Item Also Bought" feature that presents shoppers with other products bought by similar users, which streamlines the flow of web browsing and facilitates access to more relevant pages.^[13]

Social navigation can also be discussed in different types of virtual worlds. Munro shares some original conceptions when considering social navigation. Instead of individual interaction, it can be presented as "a way of moving through an information space and exploiting the activities and orientations of others in that space as a way of managing one's spatial activities". Munro points out that spatial navigation, which mostly depends on the structure itself, like landscape or map, can be contrasted with social navigation. User can not only with the data and objects in a specific space, but also other individuals and their interactions.^[14]

Traces of users' activities

As users navigate through online communities they leave traces of their activities, both intentional and unintentional. Intentional traces include posts, responses to other users’ posts, number of friends, uploaded media, and other activities where users intentionally share information. Unintentional traces include browsing history, times spent on particular pages, bounce rates, and other activities where users’ actions are automatically logged by web servers into server logs.

Björneborn categorizes online community users as “trace leavers” (i.e. users who leave actionable items) and "trace finders" (i.e. users who follow traces left by trace leavers). These participatory activities can guide other users’ information seeking behavior and influences features of social search and social navigation.^[15] Combining trace-leaving activities of social browsing with the concept of social searching relies on recording and reusing focused search activities of like-minded searchers to produce search results that are better suited to the needs of a particular online community, as demonstrated by Freyne et al.^[16]

Websites such as Amazon.com analyze user traces, such as history of purchases or product reviews, to generate recommendations for other users (e.g. "Customers Who Bought This Item Also Bought...").^[17] Online platforms for collaborative software development such as GitHub rely on activity traces, such as the number of repositories, history of activity across projects, commits, and personal profiles to determine its users' reputations in the community.^[18]

User activity traces can be used to model users’ behavioral patterns and trends to determine the health of online communities (whether a community would flourish or diminish).^[19] Such models can also be used to predict propagation and future popularity of content,^[20] or predict results before voting occurs.^[21] Activity and traffic patterns can be used to evaluate the performance of existing systems, and improve site usability, architecture, and infrastructure.^[22]

Tag-based social navigation

There are primarily two strategies to explore and discover an information space: the first one is the regular search, where users are aware of what they are searching for. Under this context, users have a target information in mind. They usually need to formulate a search query first before inputting it into a search engine; another search strategy is navigation, where users do not have a target information in mind but rather explore through pieces of information by following certain hyperlinks.

Navigation is considered to have advantages over searching, since recognizing what users are looking for is easier than formulating and describing the information people need, which refers to the "vocabulary problem".^[23] Social tagging serves as a new social way of organizing a set of resources, and approaches the "vocabulary problem" from a new social angle. Social tagging systems allow people to annotate a set of resources according to their own needs with freely chosen words—tags, and share them with other users of the social tagging system. The result of this human-based annotation of resources is called folksonomy. Examples of social tagging systems are BibSonomy, CiteULike, Flickr, and Delicious.

Tag cloud

A tag cloud is a textual representation of the topic or subject collectively seen by the users and it captures the "aboutness" of the resource.

Tag clouds are easy to build, intuitive to understand, and widely used. It can also represent the three types of relationship among users, tags, and resources in the tagging systems. However, there is a size limitation on the tag cloud that can be presented in the screen; selecting the best tags and structuring the information space to present the relationships in the tag cloud is important.^{[citation needed]}

Tag clouds are very simple, and can be applied to support the user. Researchers find that tag cloud is usually more useful for the following four different tasks, as illustrated by Rivadeneira et al.:^[24]

• Search: finding the presence or absence of a given target
• Browsing: exploring the cloud without a particular target in mind
• Gaining visual impression about a topic
• Recognition and matching: recognizing the tag cloud as data describing a specific topic

Researchers also found that different layouts are useful when performing different tasks. They also demonstrated that tag cloud typography (font size/position) matters: font size has a bigger impact on finding a tag than other visual features like color, tag string length, and tag location.^[25][26][27]

Based on previous research, common ways to perform tag cloud evaluation are:^[28][29]

• Using certain evaluation metrics for tag clouds with respect to coverage, overlap, and selectivity
• User navigation model that combines with the evaluation metrics to allow tag cloud evaluation with respect to navigation
• User study to evaluate tag-based information access in image collections
• Examining the navigability assumption (the widely adopted belief that tag clouds are useful for navigation)

Tag clustering

An issue with social tagging data is the lack of structure. Synonymy, polysemy and homonymy or problems regarding tag semantics are additional issues related to tagging data. There are two main categories: flat and hierarchical clustering algorithms.

Flat classification can refer to three methods: content-based method, which is a widely-adopted algorithm for tag cloud selection is TopN algorithm proposed by Venetis et al.;^[29] network-based method, which splits a graph of connected tags into clusters; and machine learning method, where the semantic relationship between tags is considered.

Hierarchical tag clustering refers to the creation of a hierarchical structure out of unstructured tagging data. The structure can be seen as the users’ mental maps of the information space, and can be used as a navigational aid. Hierarchical tag clustering can refer to three methods:

• Hierarchical clustering is the method that adapted the K-Means algorithms to work with textual data and create a tag hierarchy in a top-down manner
• Affinity propagation characterizes each data sample according to its ”responsibility” and its ”availability” values. The input of the algorithm is a set of similarities between data samples provided in a matrix and the output of the algorithm is a hierarchy, and each node in the hierarchy represent a unique tag
• Generality in the tag similarity graph method includes:
  1. The input of the algorithm is a similarity graph of tags
  2. Setting the most general node as the root of the hierarchy
  3. All other nodes that are added to the hierarchy in descending order of their centrality in the similarity graph based on the following rules:
     1. Calculate the similarity between all currently present nodes in the hierarchy and the candidate node
     2. If their similarity is above a given threshold: the candidate node is added as a child of the most similar node in the hierarchy
     3. Otherwise, the candidate node is added as a child of the root node

Modeling navigation in social tagging systems

Modeling tag-based navigation is used to understand the processes occurring in a social tagging system and how the system is used. There are two factors to understand modeling tag-based navigation in social tagging systems: basic modeling framework for navigation and theories understanding of the ability of folksonomies to guide navigation.

Basic modeling framework for navigation

Markov chain models:

• Navigation on the Web can be seen as the process of following links between web pages
• Markov chain models assign transition probabilities between web pages (also called states)
• First order Markov chains (the transition probability between states depends only on the current state) are more commonly used

Decentralized search:

• Navigation in a network can be modeled by the message-passing algorithm decentralized search
• The message holder passes a message to one of its immediate neighbor nodes until the target node is found
• At each step, the decision of movement is only made by the local knowledge of the network
• Finding a path to a node (already realized in web navigation)

Theoretic suitability for search

Different scholars provided the theoretic support to argue the suitability of folksonomies as a navigational aid. There are four main perspectives:

• Network theoretic perspective has two aspects: the general navigability of a folksonomy as a graph, or the ability of tag hierarchies to guide navigation in such a graph
• Information theoretic perspective suggest to see social tagging as the collective effort of creating a mental map that summarize an information space
• Information foraging perspective to describe the human information seeking in a digital environment
• Tagging vs. library approach. They^[who?] proposed a definition of a controlled vocabulary and compared unrestricted free-form vocabularies emerged in social tagging systems to controlled vocabularies

Pragmatic folksonomy evaluation

The evaluation method introduced in this section is based on the paper by Helic et al.^[30] The author proposed in the paper the general idea that people can leverage on the output produced by folksonomy algorithms (hierarchical structures) as input (background knowledge) for decentralized search for the following reasons:

• The performance of decentralized search highly depends on the quality of the hierarchical clustering results that developed to facilitated navigation.
• The performance of the decentralized search algorithm depends on the suitability of folksonomies.
• The authors proposed the simulation method on decentralized search can be leveraged to evaluate the suitability of folksonomies.

Implementation examples

Educational systems

Various applications of social navigation have been studied in educational system, such as Knowledge Sea II. Compared to traditional approaches (Closed Corpus), it is able to gather online information (named Open Corpus) and feedback from different sources. Group traffic is used as feedback to indicate social navigation information such as "the most important parts of the textbooks". After a classroom study, Knowledge Sea II system shows better performance in visualization of content relevance of the textbook and satisfaction of student users.^[31]

Mertens and his colleagues optimized the pre-existing system, virtPresenter, with the addition of hypermedia navigation concept. bookmarks, footprints and structural elements are integrated to help users to access lecture recordings and support social navigation for future users as well. The new version of virtPresenter shows better performance in social navigation function such as visualization, week-based filtering, and exchangeable bookmarks.^[32]

Farzan and Brusilovsky introduced the AnnotatEd system, which combines functions of web annotation and adaptive navigation support to synergize social navigation application in web-based education. With implementations of web annotation and social navigation support, the system integrated Knowledge Sea II, and has been evaluated for six semesters in School of Information Systems at the University of Pittsburgh, which shows the significantly higher positive user attitude towards the new system because of its social navigation integration.^[33]

Urban mobile information system

A system called CityFlocks was introduced to show social navigation implementation in an urban mobile information system.^[34] The implementation is described by Bilandzic et al. (2008).^[35] To solve the “socially blind” problem based on the influx of mobile phone users, CityFlocks was designed to enable web annotations combined with coordinates upon physical targets in the city directly or indirectly. Focus groups were chosen to collect requirements and problems in social navigation. The system is designed and generated by using appropriate techniques such as Google Maps and information retrieval. User tests of CityFlocks indicated that an indirect approach is more acceptable than a direct one.^{[citation needed]}

Prototypes

Two prototypes of social navigation systems have been introduced: Juggler and Vortex. The Juggler system combines MOO^{[clarification needed]}, a textual virtual environment, and a Web client. The Vortex system uses a simplified desktop to present URLs.^[36]

History-enriched implementation

History-enriched implementation of social navigation is based on the making the traces of behavior of latent users visible to future users. The implementation of the idea can be attributed to Wexelblat and Maes, who introduced an information space enriched with various social navigation mechanisms: document map, navigation paths, and documents' annotations and signposts.^[37] They used six properties: Proxemic versus Distemic, Active versus Passive, Rate of Change, Degree of Permeation, Personal versus Social, and Kind of Information. More examples of history-rich information spaces has been implemented in different context such as educational domain,^[38] location-based networking, and food recipes.

Social Navigation Network (SoNavNet), a location-based social network application devised by Hassan Karimi and his team, is aimed at sharing navigation experience. Other than simply showing the shortest time or distance like Google Maps, users’ specific experience and recommendation are underlined. With both geo-position and message functions, SoNavNet allows users to send requests to their friends while presenting their current location and points of interest, from which they acquire route and venue information oriented to their needs.^[39]

Martin Svensson and his team created a recipe recommendation system, European Food On-Line, which has both direct and indirect navigation approaches. Social Navigator was implemented as a Java servlet to model users' behavior and net-based communication usages.^[40]

Embedded visualization implementation

Social navigation implementation plays a significant role in guiding users to find information they need. Wesley Willett and his team designed Scented Widgets, which improves navigation with embedded visualization. They implemented scent metrics with a standard interface widget and used visual encoding for data. Hue, saturation, opacity, text, icon, bar chart, and line chart are scent encodings to highlight various information, which can display different types of data at the same time. They used Java Swing and the platform's pluggable look and feel to create and change widgets at runtime. In order to design a user-friendly interface, they followed scent encoding, layout, and composition guidelines.^[41]

Implementation in usable security

In a file sharing system, every user can determine which files in their own computer can be shared through the network. Initially, users had to configure these security-related settings by themselves, and about eight out of ten users would unintentionally leak their private information such as credit card information or their address. Based on this problem, Paul DiGIoia and Paul Dourish from University of California, Irvine, introduced a pile metaphor model that used social navigation to solve the issue.

The pile metaphor model focuses on two major parts. First, users can be shown how other users in this system decide which files are shared, and such information is shown directly as folders; different folder appearances indicate different sharing levels. Based on this straightforward design, users can easily know that whether their decision is appropriate or not. Secondly, the pile metaphor model also shows the number of users in the system that have read a file by showing the tidiness of the pile. For example, the more times a file is read, the messier the pile is.

The pile metaphor model has two advantages: introducing this model to a system does not change the fundamental design of the system, as it is like a small plug-in and will have significant influence on the users; and it does not detract users from their work, because every security-related feature is shown directly on the graphical user interface.^[42]

Implementation in human-robot interaction

One of the common methods people used in the field of social navigation is to construct proxemics, which can be connected with human-robot interaction. A study shows interests in different kinds of navigation behaviors humans expect from a robot in a path crossing scenario. The result reveals that spatial relationship actually relates to the behavior, which leads to a possible prediction to the expected action.^[43]

Drawbacks of social navigation

Social navigation can be abused by malicious users who intend to mislead the public or obtain private information about specific person.

Researchers Meital Ben Sinai, Nimrod Partush, Shir Yadid, and Eran Yahav from Israel Technion performed some experiments in 2014 and wrote an article, “Exploiting Social Navigation”, to discuss the results. According to the article, attackers can use multiple machines to fake users’ behavior and fabricate information to mislead other real users. In this case, they attacked a real-time traffic software that allows users to report traffic news, and broadcast these messages to others. The researchers used fake users to fabricate traffic information like obstruction or traffic jams, and successfully let the system mislead real users. Real users could waste time and money to go a different route, or lead them onto unsafe non-existent routes, which cause security related issues. To solve this problem, social navigation systems sometimes verify the users’ identities through verification codes.

The verification technique can lead to another problem of social navigation: information leakage. Sinai et al. discussed that malicious attackers may exploit user information to gain private information, which causes security-related issues, since attackers can use the information to track other people with malicious intent.^[44]

Recent trends and implementation in products

As the popularity of social networks and social web grows, data can be collected through the footprints of users left behind as they interact within different social computing systems. The growth has led to more novel and diverse implementation of social navigation support, including in education, media, news, and tour guide systems. Social navigation implementation in shared 3D environment works similarly, as it allows users to see trail and information of others who were in the same place before in the virtual world.^[45] Bosch improved real navigation systems for driving and used social navigation to reduce driving times.^[46]