Reachability is not findability: graphs, trees and the cost of navigating

Sixty-four items can be arranged as six levels of two, three levels of four, two levels of eight, or one level of sixty-four. The count of items is fixed. This unit argues that depth and breadth are properties of a graph while findability is the cost of choosing a labelled edge. Snowberry, Parkinson and Sisson (1983) ran the comparison and found search speed and accuracy improving as the menu grew broader, except in their broadest condition's second version, the same sixty-four items in one menu with the order randomised. That version fell outside the trend: the topology was identical, and only the arrangement had changed.

The choice at a vertex is made from the label, so a route one step shorter can be harder to find than one longer, for a reason outside the graph. Navigation design is a labelling problem as much as a structure problem. Unit 4 counts the state space a design implies, before any of it is built.

The shortest path is a sum of weights you chose

Dijkstra's method (1959) is the cleanest statement of what a graph distance is. It finds the path of least total cost between two vertices of a weighted graph, and a second construction gives a tree of minimum total length. Both need only non-negative edge costs, which makes "least total cost" well defined as a claim about the numbers written on the edges.

A settings application makes the choice concrete. From the home screen, two taps reach Wi-Fi if the tile labelled Settings is recognised as the place Wi-Fi lives. Give that edge a weight above one, because the label does not promise a network setting, and the cheapest route becomes the search field: home, search, type, first result. Four taps in an unweighted count, cheaper in the weighted one.

The algorithm never asks where the weights came from. A weight of one per tap encodes the claim that every level costs the same, which is the assumption behind counting depth. A weight that charges more for an unfamiliar label is a different graph with a different shortest path, so "three taps from home" is true of the unweighted graph and silent about the route a person takes. A minimum-length tree gives one path to each setting and so gives "back" a single meaning, but it is chosen from the same weights, so the tree that minimises taps need not minimise search.

Depth and breadth are structural, and they do not settle the cost

Sixty-four items at breadth two give six levels, at four give three, at eight give two, at sixty-four give one. Snowberry's hierarchies are those numbers, and the trend across them improved steadily with breadth. Kiger (1984) concluded that depth should be minimised by giving each menu eight or nine selections.

Burnett, Lawson, Donkor and Kuriyagawa (2013) tested the trade-off in an in-vehicle touchscreen and found the recommendation depends on something the structural account leaves out. Participants searched menus of 16 by 3, 8 by 4, 4 by 6 and 12 by 2, ordered alphabetically or randomly, under full vision or occlusion goggles allowing 1.5 seconds of viewing. For ordered menus, visual demand grew as a logarithmic function of breadth, and the broadest, shallowest structure, 16 by 3, was least demanding. For randomised menus the relationship was quadratic, and the compromise structures, 4 by 6 and 8 by 4, were least demanding. Four topologies produced two cost equations and two best structures, because the labels were ordered differently.

Jiang and Chen (2021) add a third variable, comparing full, collapsible and cascading menus on phones and watches at three numbers of previews. Menu type significantly affected navigation efficiency, and the suitable preview count differed by device: sixteen for phones, four for watches.

A graph's distances can be short while its neighbourhoods are not

Watts and Strogatz (1998) rewired regular ring lattices with increasing probability and found a range in which networks stayed highly clustered while their characteristic path length fell to that of a random graph. The two properties move independently, so a space can have a small diameter and still present dense, repetitive local choices, as a corporate wiki does when the shortest route between two pages is three links and each link offers thirty near-identical titles.

Barabasi and Albert (1999) give the mechanism by which such spaces acquire their shape: growth by addition of vertices and preferential attachment produce a heavy-tailed degree distribution, so a few nodes are reachable from everywhere and most are not, and an average hides the targets people cannot reach. Kleinberg (1999) makes the same point about importance rather than distance, since hub and authority scores are defined on the subgraph a query induces rather than on any fixed property of a page.

The edge is chosen by its label

If the choice at a vertex is made from the label, then navigation is a theory of labels, and Pirolli and Card (1999) supply one. Information foraging models a person as following cues about where useful material is likely to be, and models the decision to abandon a patch as a forager decides when to leave one. The cue is information scent, computed from what is visible before the click, so the path is predicted from the cues along the way rather than from the distance to the target.

Fu and Pirolli (2007) turned the account into a running model. In SNIF-ACT a spreading activation mechanism scores each link's relevance to the goal. A Bayesian satisficing rule then decides whether to click or go back, and the model predicts link choice and stopping from the link texts. The unit of cost is the label, and the route is an output rather than an input.

If the cost of an edge is read off its label, two interfaces with the same topology and task can differ in cost. A comparison between them then has to control the labels or report them. A cost read off a label varies with the reader: a user in a second language, a reader with limited literacy and a screen-reader user all pay a price the hierarchy does not show, and the ancestry information Ziefle and Bay found helpful tells such a user where in the tree the page sits.

The view or the user must supply what the graph does not

Furnas (1997) states the constraint that discoverability imposes: navigation has to work in a structure too large to display, so the views stay small, the number of steps stays low, and the route to any target is discoverable from the current view. Those requirements pull against one another, and discoverability is the one a graph does not contain. Ziefle and Bay (2006) tested what happens when it is supplied. Sixteen younger adults aged 23 to 28 and sixteen older adults aged 46 to 60 solved nine mobile phone tasks twice, with an aid showing only the current category and its contents or one also showing the parent categories and indenting the hierarchy. The second won for both groups, more so for older adults and participants with lower spatial ability: the topology was identical, and the labels carried the position.

Aula, Jhaveri and Kaki (2005) surveyed 236 experienced web users. Strategies the browser does not support, such as running several windows in parallel, were used often and rated important, while some recommended in earlier work were rated unimportant, and most of those respondents held misconceptions about how their search engine handles a query. A laboratory study of first-visit search measures the designed graph; field use measures that graph plus the user's own.

Contested question: is the cost of a step fixed, or read off the label?

The literature divides on what makes an edge expensive, and not cosmetically. In the structural camp the cost of a level is a parameter: Kiger's eight or nine items per menu, Burnett's logarithmic and quadratic equations, Snowberry's breadth trend. The recommendation is then a number of items per screen, computable before anything exists. Its evidence is a run of laboratory menu studies, most from the 1980s, with small convenience samples and a single search task, so its numbers are comparative rather than absolute. In the scent camp the cost of an edge is a function of its label relative to the goal, so no number of items per screen is optimal in general and the same menu is cheap for one goal and expensive for another. Its evidence is a cognitive model fitted to instrumented protocols, and no experiment varies the labels at fixed topology, the test the account needs.

The structural camp also disagrees with itself. Kiger's optimum is eight or nine items per menu, Snowberry's trend favours breadth without fixing a limit, and Burnett's ordered menus favour 16 by 3 while his randomised menus favour 4 by 6 or 8 by 4. A designer looking for one number will find three, and the disagreement is not noise: the studies differ in task, in display and in whether the labels were ordered.

A second tension sits inside the thesis. Furnas requires views to stay small, while Ziefle and Bay improved navigation by enlarging the view with ancestry information: both can be right, since one constrains the options at a decision and the other adds context rather than options.

What would settle it is a factorial design rather than another single-factor study. Hold the topology fixed and vary the labels, ordered against unordered and familiar against unfamiliar, then measure the path taken against the shortest path in the graph, with time and errors. If label quality moves the chosen path at fixed topology, the scent account wins the mechanism; if the effect disappears once labels are ordered and the task is well practised, the structural account is sufficient. A second condition is needed for transfer: test the same participants on a second structure carrying the same labels.

Meanwhile, use the structural number as a starting point and the labels as the thing to fix: choose a breadth, then test the labels against the tasks the product is actually for, because the studies agree that the same hierarchy performs differently when the labels or their order change. Where the structure cannot be changed, add position information rather than more items.

Where the argument is heading

The direction of travel is to make the label the unit of measurement rather than the afterthought: Fu and Pirolli's model predicts clicks from link text, and Burnett shows the optimum depends on ordering and on device. The open problem is Furnas's third requirement, discoverability, and no model states how much of a structure a view must show before a route becomes findable. Until that is measured, a shorter route remains a claim about a graph.

The sources this unit rests on

• Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. doi:10.1007/BF01386390 Gives a shortest-path method and a minimum-length tree construction requiring non-negative costs: a distance is a sum of weights the designer supplies.
• Snowberry, K., Parkinson, S. R. and Sisson, N. (1983). Computer display menus. Ergonomics, 26(7), 699-712. doi:10.1080/00140138308963390 Searched four 64-item hierarchies; speed and accuracy improved with breadth, while the randomly arranged broad menu fell outside the trend, so labelling changed performance.
• Kiger, J. I. (1984). The depth/breadth trade-off in the design of menu-driven user interfaces. International Journal of Man-Machine Studies, 20(2), 201-213. doi:10.1016/S0020-7373(84)80018-8 Recommended minimising depth with eight or nine items per menu: the structural recommendation in usable form.
• Furnas, G. W. (1997). Effective view navigation. Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI). doi:10.1145/258549.258800 Derives small views, few steps and discoverable routes as requirements that conflict. Discoverability is what no graph supplies.
• Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393(6684), 440-442. doi:10.1038/30918 Rewiring a ring lattice keeps high clustering while path length falls to a random graph's, so the two vary independently and diameter misleads.
• Barabasi, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512. doi:10.1126/science.286.5439.509 Growth with preferential attachment heavy-tails the degree distribution, so a few hubs are reachable from everywhere.
• Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5), 604-632. doi:10.1145/324133.324140 Defines hub and authority scores over a query-induced subgraph: importance is computed, not inherent.
• Pirolli, P. and Card, S. (1999). Information foraging. Psychological Review, 106(4), 643-675. doi:10.1037/0033-295X.106.4.643 Models seeking as foraging, with scent from visible cues and a rule for leaving a patch: the path is predicted from cues, not distance. It supplies the label-based account of cost.
• Aula, A., Jhaveri, N. and Kaki, M. (2005). Information search and re-access strategies of experienced web users. Proceedings of the 14th International Conference on the World Wide Web (WWW). doi:10.1145/1060745.1060831 Survey of 236 experienced users: unsupported strategies were widespread and valued, while most held misconceptions about search. The navigated graph includes the user's own.
• Ziefle, M. and Bay, S. (2006). How to overcome disorientation in mobile phone menus: a comparison of two different types of navigation aids. Human-Computer Interaction, 21(4), 393-433. doi:10.1207/s15327051hci2104_2 Sixteen younger and sixteen older adults solved nine tasks twice with a category aid or a tree aid; the tree aid won at unchanged topology, especially for older, low-spatial-ability users.
• Fu, W.-T. and Pirolli, P. (2007). SNIF-ACT: a cognitive model of user navigation on the World Wide Web. Human-Computer Interaction, 22(4), 355-412. doi:10.1080/07370020701638806 Spreading activation scores link relevance and a Bayesian satisficing rule decides click or back: link text predicts choice, so label cost is computable.
• Burnett, G., Lawson, G., Donkor, R. and Kuriyagawa, Y. (2013). Menu hierarchies for in-vehicle user-interfaces: modelling the depth vs. breadth trade-off. Displays, 34(4), 241-249. doi:10.1016/j.displa.2013.07.001 Tested four menu shapes, ordered or random, under occlusion: ordered menus gave a logarithmic breadth cost favouring 16 by 3, random ones a quadratic cost favouring 4 by 6 or 8 by 4, so the optimum tracks the labels.
• Jiang, L. and Chen, Y.-H. (2021). Menu design on small display user interfaces: measuring the influence of menu type, number of preview items, and menu breadth. International Journal of Human-Computer Interaction, 38(7), 631-645. doi:10.1080/10447318.2021.1954781 Compared full, collapsible and cascading menus on phones and watches at three preview counts: menu type affected efficiency, and the suitable preview count differed by device, sixteen for phones and four for watches.