Graph-Theoretic Navigation Analysis

Description

Models a site or app as a directed graph and computes path length, centrality and connectivity to find unreachable, overburdened or poorly linked content.

Any navigation structure can be represented as a directed graph: screens or pages are nodes, links are edges. Graph theory then provides precise metrics. Shortest path lengths show how many steps separate users from key content; centrality measures show which pages carry most navigational load; compactness and stratum metrics, proposed by Botafogo and colleagues for hypertext, characterise how interconnected and how linear a structure is. Strongly connected components reveal sections users cannot leave without the back button. The method is rigorous when the graph is extracted automatically from a crawl or app state model, metrics are weighted by actual traffic or task importance, and changes are simulated before implementation. It complements tree testing by covering the full link structure, not just the hierarchy.

Attributes

Loss type
Latent
Effort
Days

Steps

  1. Crawl the site or export the app's screen map to build a directed graph of nodes and links.
  2. Compute shortest path lengths from entry points to key task destinations.
  3. Calculate centrality (degree, betweenness, PageRank) and identify overloaded hubs and orphaned nodes.
  4. Weight metrics by traffic or task priority using analytics data.
  5. Simulate structural changes (new links, merged sections) and recompute metrics.
  6. Validate the preferred structure with tree testing or first-click testing before implementation.

Sources

  • Where Mathematics Comes From
  • Structural analysis of hypertexts (Botafogo, Rivlin & Shneiderman)

Also known as

  • Graph Theory for Navigation
  • Navigation graph analysis
  • Hypertext network metrics

Categories

  • Content
  • Information Architecture & Content